Why am I getting a Terminated (singular KKT matrix)." error ??

[Ronald L. Rivest]

I am trying to use CVXOPT qp to find nice solutions to two-person zero-
sum games.
But I am getting the "singular KKT matrix" error. I believe that my
inputs satisfy the
necessary conditions (A has full row rank and G;A has full column
rank). The program and its
output are attached...

Any help would be appreciated; thanks!
Ron Rivest

Output:
python game_cvxopt_qp_post.py
P
[ 1.00e+00 0.00e+00 0.00e+00 0.00e+00]
[ 0.00e+00 1.00e+00 0.00e+00 0.00e+00]
[ 0.00e+00 0.00e+00 1.00e+00 0.00e+00]
[ 0.00e+00 0.00e+00 0.00e+00 1.00e+00]

G
[-1.00e+02 -1.00e+02 -8.00e+01 -1.50e+02]
[-1.00e+02 -1.00e+02 -1.00e+02 -1.00e+02]
[-1.20e+02 -1.00e+02 -1.00e+02 -7.00e+01]
[-5.00e+01 -1.00e+02 -1.30e+02 -1.00e+02]
[-1.00e+00 -0.00e+00 -0.00e+00 -0.00e+00]
[-0.00e+00 -1.00e+00 -0.00e+00 -0.00e+00]
[-0.00e+00 -0.00e+00 -1.00e+00 -0.00e+00]
[-0.00e+00 -0.00e+00 -0.00e+00 -1.00e+00]

A
[ 1.00e+00 1.00e+00 1.00e+00 1.00e+00]

Terminated (singular KKT matrix).
[ 2.17e-01]
[ 2.75e-01]
[ 3.62e-01]
[ 1.45e-01]

Input program:
# game_cvxopt_qp_post.py
# Ronald L. Rivest and Emily Shen

from cvxopt import matrix, solvers

def identity(n):
"""
Return identity matrix of size n
"""
I = matrix(0.0, (n, n))
I[::n+1] = 1.0
return I

def solver(payoff):
"""
Solve zero-sum two-person symmetric game M of payoffs.
Returned value x is an optimal mixed strategy that minimizes
sum of squares of x_i.
Uses function qp from cvxopt library
Input matrix M is m x m.
"""
m = len(payoff)

# convert payoff matrix to cvxopt matrix object M and negate
M = matrix(payoff).trans()
M = -M

# make M all positive by adding large constant v
v = max(1.0, -2.0 * min(M))
M = M + v

# set up P, q so that minimizing sum of squares of p_i is
# equivalent to minimizing 1/2 x^T P x + q^T x
P = identity(m) # P is m x m
print "P"
print P
q = matrix([0.0]*m) # q is m x 1

# set up G, h so that M x >= 1 and x >= 0 are equivalent to G x <=
h
G = matrix([-M, -identity(m)]) # G is 2m x m
print "G"
print G
h = matrix([-1.0]*m + [0.0]*m) # h is 2m x 1

# set up A, b so that sum_i x_i = 1.0/v is equivalent to A x = b
A = matrix(1.0, (1, m)) # A is 1 x m
print "A"
print A
b = matrix(1.0/v) # b is 1 x 1

# The following requirement on G and A should also be met,
# according to the CVXOPT documentation
# (1) rank(A) = p (where p = # rows of A)
# (2) rank(matrix([P,G,A]) = n (where n = # columns in G and
in A)
# (this last has P stacked on top of G on top of A)
# otherwise, the routine terminates with a "singular KKT matrix"
error
# but actually gives fairly good results even when terminating
this way.
# These properties should be met by this code,... ???

# solve constrained least squares problem
solvers.options['feastol']=1e-9
solvers.options['show_progress']=False
x = solvers.qp(P, q, G, h, A, b)['x'];

# if any were even slightly negative, round up to zero.
for i in range(m):
x[i] = max(0.0,x[i])

#return optimal mixed strategy that minimizes sum of squares
x = x * v
return x

def test():
"""
One test example that produces a singular KKT error.
(Example x4_3b)
"""
M = [ [ 0, 0, 20, -50 ],
[ 0, 0, 0, 0 ],
[ -20, 0, 0, 30 ],
[ 50, 0, -30, 0 ]]
print solver(M)

if __name__== "__main__":
test()

[Jeffery Kline]

You may have set 'feastol' too low. Try commenting out the line
solvers.options['feastol']=1e-9

With the default feastol(=1e-7) and 'show_progress'==True, I have the following output:

pcost dcost gap pres dres
0: 1.3767e-05 -9.9949e-03 8e+00 1e+00 8e+02
1: 2.0744e-05 -1.4674e-02 5e-01 8e-02 4e+01
2: 1.3797e-05 -9.1490e-03 1e-02 8e-04 5e-01
3: 1.3772e-05 -4.4127e-04 5e-04 1e-05 6e-03
4: 1.3771e-05 8.5595e-06 6e-06 1e-07 7e-05
5: 1.3768e-05 1.3701e-05 7e-08 2e-09 9e-07
6: 1.3768e-05 1.3767e-05 7e-10 2e-11 2e-08
Optimal solution found.
[ 2.17e-01]
[ 2.75e-01]
[ 3.62e-01]
[ 1.45e-01]

--Jeff

> --
> You received this message because you are subscribed to the Google Groups "CVXOPT" group.
> To post to this group, send email to cvx...@googlegroups.com.
> To unsubscribe from this group, send email to cvxopt+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/cvxopt?hl=en.
>

[Ronald L. Rivest]

Thanks. This was helpful, but didn't quite solve my problem.
I am trying to get six-digit precision for relatively simple problems.
Your suggestion helped but not always.
Here is a different example where the optimal solution is
(0,1/2,1/2,0)
but I only get three digits of accuracy. Is it too much to ask for
to get six-digit precision on a simple 4x4 problem??

Any assistance you can provide is greatly appreciated, thanks!

I give the output first and then the program.

output:

12:55:12 code $ python game_cvxopt_qp_post.py

P
[ 1.00e+00 0.00e+00 0.00e+00 0.00e+00]
[ 0.00e+00 1.00e+00 0.00e+00 0.00e+00]
[ 0.00e+00 0.00e+00 1.00e+00 0.00e+00]
[ 0.00e+00 0.00e+00 0.00e+00 1.00e+00]

G
[-2.00e+01 -3.00e+01 -1.00e+01 -3.00e+01]
[-1.00e+01 -2.00e+01 -2.00e+01 -2.00e+01]
[-3.00e+01 -2.00e+01 -2.00e+01 -1.00e+01]
[-1.00e+01 -2.00e+01 -3.00e+01 -2.00e+01]

[-1.00e+00 -0.00e+00 -0.00e+00 -0.00e+00]
[-0.00e+00 -1.00e+00 -0.00e+00 -0.00e+00]
[-0.00e+00 -0.00e+00 -1.00e+00 -0.00e+00]
[-0.00e+00 -0.00e+00 -0.00e+00 -1.00e+00]

A
[ 1.00e+00 1.00e+00 1.00e+00 1.00e+00]

pcost dcost gap pres dres
0: 3.3142e-04 -3.4699e-02 9e+00 2e+00 2e+02
1: 4.5601e-02 -5.9305e-01 1e+00 2e-01 3e+01
2: 2.6881e-03 -1.1966e-01 5e-01 6e-02 7e+00
3: 7.3638e-04 -5.0491e-02 9e-02 8e-03 9e-01
4: 7.7218e-04 -6.0950e-03 1e-02 7e-04 7e-02
5: 7.2458e-04 3.9307e-04 5e-04 3e-05 3e-03
6: 6.4027e-04 5.9486e-04 5e-05 1e-06 1e-04
7: 6.2727e-04 6.2222e-04 5e-06 2e-08 2e-06
8: 6.2550e-04 6.2440e-04 1e-06 3e-09 3e-07
9: 6.2510e-04 6.2488e-04 2e-07 3e-10 1e-07
10: 6.2503e-04 6.2497e-04 6e-08 8e-11 3e-08
11: 6.2501e-04 6.2499e-04 1e-08 8e-12 4e-07
12: 6.2500e-04 6.2500e-04 4e-09 2e-12 4e-07
13: 6.2500e-04 6.2500e-04 7e-10 2e-13 1e-05
14: 6.2500e-04 6.2500e-04 2e-10 7e-14 1e-05
Terminated (singular KKT matrix).
0.000000
0.500222
0.499778
0.000000

input python program:

solvers.options['feastol']=1e-6
solvers.options['abstol']=1e-9
solvers.options['show_progress']=True

x = solvers.qp(P, q, G, h, A, b)['x'];

# if any were even slightly negative, round up to zero.
for i in range(m):
x[i] = max(0.0,x[i])

#return optimal mixed strategy that minimizes sum of squares
x = x * v
return x

def test():
"""
A test example that produces a singular KKT error.
(Example x4_4a)
"""
M = [ [ 0, -10, 10, -10 ],
[ 10, 0, 0, 0 ],
[ -10, 0, 0, 10 ],
[ 10, 0, -10, 0 ] ]

for xi in solver(M): print "%9.6f"%xi

if __name__== "__main__":
test()

[Joachim Dahl]

It looks like you're using the QP solver. You might try to

use the conic SOCP solver instead, which uses a more

robust algorithm.

if __name__== "__main__":
   test()

[Ronald L. Rivest]

Joachim --

Thanks. I'm not sure I understand your suggestion. The routine
cvxopt.solvers.socp
optimizes a linear function, not a quadratic one. The routine
cvxopt.solvers.coneqp
gives the same output as qp (i.e. only three digits of precision).

Which "conic SOCP solver" did you mean?

Thanks!

Cheers,
Ron Rivest

On Mar 18, 1:13 pm, Joachim Dahl <dahl.joac...@gmail.com> wrote:
> It looks like you're using the QP solver. You might try to
> use the conic SOCP solver instead, which uses a more
> robust algorithm.
>

> > cvxopt+un...@googlegroups.com<cvxopt%2Bunsu...@googlegroups.com>

> > .
> > For more options, visit this group at
> >http://groups.google.com/group/cvxopt?hl=en.

On Mar 18, 1:13 pm, Joachim Dahl <dahl.joac...@gmail.com> wrote:
> It looks like you're using the QP solver. You might try to
> use the conic SOCP solver instead, which uses a more
> robust algorithm.
>

> > cvxopt+un...@googlegroups.com<cvxopt%2Bunsu...@googlegroups.com>

[Joachim Dahl]

You can solve

min. t

s.t.   ||Gx-h||_2 < t

instead of 

min. 1/2 x'*G'*G*x - h'*Gx.

In most cases the default tolerance levels are sufficient, but you can try

to change the number of iterative refinement steps to see if you can reach

a higher precision, but otherwise there's not much else you can do.  There is

another package SDPA, which implements an SDP solver in unlimited precision.

To unsubscribe from this group, send email to cvxopt+un...@googlegroups.com.