Problems with the solvers.conelp standard solver

[JensM1983]

Hello everyone,

I am trying to solve a linear program (see below) with the
cvxopt.solvers.conelp routine.

The standard solver says the problem is infeasable - even though there
are valid solutions and the problem is bounded through the last line.

Changing the accuracy of the solver to e-12 did not help.

Solving the lp with the glpk solver works just fine, so I think there
might be a problem inside the conelp routine.

I would really appreciate some help on this problem,
thanks
Jens


#KKT G
G= matrix(
[[ -1.0 , 0.0 , 0.0 , 1.0 , 0.0 , 0.0 ],
[ 0.0 , 0.0 , 0.0 , -1.0 , 0.0 , 0.0 ],
[ -0.278682443725 , 0.527903820525 , -1.0 , 0.0 , 0.0 , 0.0 ],
[ -0.629908785553 , 0.793667931539 , -1.0 , 0.0 , 0.0 , 0.0 ],
[ -0.0432155557167 , 0.207883514779 , -1.0 , 0.0 , 0.0 , 0.0 ],
[ -0.476176535661 , 0.690055458395 , -1.0 , 0.0 , 0.0 , 0.0 ],
[ -0.751636649095 , 0.866969808641 , -1.0 , 0.0 , 0.0 , 0.0 ],
[ 0.0 , 0.0 , 0.0 , 0.278682443725 , -0.527903820525 , 1.0 ],
[ 0.0 , 0.0 , 0.0 , 0.629908785553 , -0.793667931539 , 1.0 ],
[ 0.0 , 0.0 , 0.0 , 0.0432155557167 , -0.207883514779 , 1.0 ],
[ 0.0 , 0.0 , 0.0 , 0.476176535661 , -0.690055458395 , 1.0 ],
[ 0.0 , 0.0 , 0.0 , 0.751636649095 , -0.866969808641 , 1.0 ],
[ -11.6202697633 , 18.7959477155 , -32.612823776 , 1.16202697633 ,
-1.87959477155 , 3.2612823776 ]])
#aim min c*x
c = matrix([11.6202697633 , -18.7959477155 , 32.612823776 ,
-1.16202697633 , 1.87959477155 , -3.2612823776] )
#constraints h
h = matrix([-1e-07 , 0.0 , 1.49717290861 , -0.460428075304 ,
0.875609571921 , -0.171607719008 , -0.744622917015 , -1.49717290861 ,
0.460428075304 , -0.875609571921 , 0.171607719008 , 0.744622917015 ,
0.9999999 ])

sol = solvers.lp(c, G.T, h )

[Lieven Vandenberghe]

Jens,

What is the output generated by the solver?

When I run your code, I get

pcost dcost gap pres dres k/t
0: -1.0379e+00 -2.0431e+00 3e+01 2e+00 1e+00 1e+00
1: -1.0088e+00 -9.5846e-01 2e+00 3e-01 1e-01 3e-01
2: -1.0050e+00 -9.9347e-01 5e-01 7e-02 4e-02 7e-02
3: -1.0023e+00 -1.0034e+00 4e-02 6e-03 3e-03 4e-03
4: -1.0000e+00 -1.0000e+00 5e-04 6e-05 3e-05 4e-05
5: -1.0000e+00 -1.0000e+00 5e-06 6e-07 3e-07 4e-07
6: -1.0000e+00 -1.0000e+00 5e-08 6e-09 3e-09 4e-09

with status 'optimal' and
x:
[ 8.79e+00]
[ 6.00e+00]
[ 1.47e-01]
[ 4.94e+00]
[ 2.44e+00]
[-1.81e+00]

Lieven

[JensM1983]

Hello Lieven,
I have run the problem under two different machines and sadly do not
derive this result.
My output always looks like this:

>>> sol = solvers.lp(c, G.T, h )

pcost dcost gap pres dres k/t
0: -1.0379e+00 -2.0431e+00 3e+01 2e+00 1e+00 1e+00
1: -1.0088e+00 -9.5846e-01 2e+00 3e-01 1e-01 3e-01
2: -1.0050e+00 -9.9347e-01 5e-01 7e-02 4e-02 7e-02
3: -1.0023e+00 -1.0034e+00 4e-02 6e-03 3e-03 4e-03
4: -1.0000e+00 -1.0000e+00 5e-04 6e-05 3e-05 4e-05
5: -1.0000e+00 -1.0000e+00 5e-06 6e-07 3e-07 4e-07

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/local/lib64/python2.5/site-packages/cvxopt/coneprog.py",
line 2210, in lp
dualstart )
File "/usr/local/lib64/python2.5/site-packages/cvxopt/coneprog.py",
line 807, in conelp
raise ArithmeticError, "singular KKT matrix"
ArithmeticError: singular KKT matrix

Jens

On 6 Sep., 02:04, Lieven Vandenberghe <lieven.vandenber...@gmail.com>
wrote:

[Joachim Dahl]

Jens,

then the problem is not infeasible (as you mentioned in your original message),  but
the KKT system is singular to machine precision during the last iteration.

Relaxing the tolerance levels:
http://abel.ee.ucla.edu/cvxopt/documentation/users-guide/node52.html

should help.  In the next version of CVXOPT we will offer a partial solution
to this recurring problem by returning the current solution together with
the status 'unknown',  in which case the user must decide whether or not
to trust the solution.

Best regards
joachim

[JensM1983]

Joachim,

thanks for the correction. Unfortunately the problem persist. Am I
using the dictionary for the options the right way? It looks like
this:

>>> solvers.options
{'reltol': 9.9999999999999998e-13, 'abstol': 9.9999999999999998e-13,
'feastol': 9.9999999999999995e-21}

But the output still has only values up to 4e-7:

>>> sol = solvers.lp(c, G.T, h )
pcost dcost gap pres dres k/t
0: -1.0379e+00 -2.0431e+00 3e+01 2e+00 1e+00 1e+00
1: -1.0088e+00 -9.5846e-01 2e+00 3e-01 1e-01 3e-01
2: -1.0050e+00 -9.9347e-01 5e-01 7e-02 4e-02 7e-02
3: -1.0023e+00 -1.0034e+00 4e-02 6e-03 3e-03 4e-03
4: -1.0000e+00 -1.0000e+00 5e-04 6e-05 3e-05 4e-05
5: -1.0000e+00 -1.0000e+00 5e-06 6e-07 3e-07 4e-07
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/local/lib64/python2.5/site-packages/cvxopt/coneprog.py",
line 2210, in lp
dualstart )
File "/usr/local/lib64/python2.5/site-packages/cvxopt/coneprog.py",
line 807, in conelp
raise ArithmeticError, "singular KKT matrix"
ArithmeticError: singular KKT matrix

Kind regards,
Jens

On 8 Sep., 14:30, "Joachim Dahl" <dahl.joac...@gmail.com> wrote:
> Jens,
>
> then the problem is not infeasible (as you mentioned in your original
> message),  but
> the KKT system is singular to machine precision during the last iteration.
>
> Relaxing the tolerance levels:http://abel.ee.ucla.edu/cvxopt/documentation/users-guide/node52.html
>
> should help.  In the next version of CVXOPT we will offer a partial solution
> to this recurring problem by returning the current solution together with
> the status 'unknown',  in which case the user must decide whether or not
> to trust the solution.
>
> Best regards
> joachim
>

[Joachim Dahl]

If you set the tolerances higher than the default values, e.g.,
solvers.options['feastol'] = 1e-5
solvers.options['abstol'] = 1e-5
solvers.options['reltol'] = 1e-5

then the solver terminates successfully after the 5th iteration on my computer.

Joachim

[JensM1983]

Joachim,

I had an error in reasoning - instead of raising the tolerances, I was
lowering them. Now I get the right results.

Thanks to you and Lieven for your active support,

Best regards,
Jens

On 8 Sep., 17:39, "Joachim Dahl" <dahl.joac...@gmail.com> wrote:
> If you set the tolerances higher than the default values, e.g.,
> solvers.options['feastol'] = 1e-5
> solvers.options['abstol'] = 1e-5
> solvers.options['reltol'] = 1e-5
>
> then the solver terminates successfully after the 5th iteration on my
> computer.
>
> Joachim
>