Python cvxopt ignores constraints

Question

I am using CVXOPT for linear programming according to the following example: http://abel.ee.ucla.edu/cvxopt/examples/tutorial/lp.html I am pretty sure I express a constraint that

X1 >= 0

But get a negative value for it. How come? I get the "optimal solution found" message

A = matrix( [ [0.0, 0.0, 1.0, 1.0, -0.0, -0.0, -1.0, -1.0, -1.0, 0.0, 0.0], 
              [0.0, 1.0, 1.0, 0.0, -0.0, -1.0, -1.0, -0.0, 0.0, -1.0, 0.0], 
              [1.0, 0.0, 0.0, 1.0, -1.0, -0.0, -0.0, -1.0, 0.0, 0.0, -1.0]
              ]
            )

Constraint values (right hand side)

b = matrix( [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0] )

Minimizing function:

c = matrix( [-1.0, -1.0, -1.0] )

Calling:

 sol=solvers.lp(c,A,b)

But:

print (sol['x']): 
[-4.83e-09]
[ 1.00e+00]
[ 1.00e+00]

-4.83e-09>=0 
False

Thanks

Anders Gustafsson · Accepted Answer · 2012-09-23 17:28:16Z

6

The default feasibility tolerance in CVXOPT is 1.0e-7, according to the user guide. Therefore you should expect that your constraints are only fulfilled to this level of accuracy.

EDIT Thus, to ensure that your "hard" constraint is fulfilled for certain, you need to set your lower variable bounds to equal your "hard" constraint (i.e. 0 in your case) plus the feasibility tolerance:

X1 >= 1.0e-7

edited Sep 23, 2012 at 17:28

answered Sep 9, 2012 at 20:13

Anders Gustafsson

16k8 gold badges61 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Anders Gustafsson Over a year ago

Not sure what you mean by "this did not work", but please see my update for further clarification. I hope it explains more clearly what I am trying to express.

Zahy Over a year ago

I've set the feasibility tolerance to 0 and still got the same result. Clearly, I did something wrong. However, I've found a different solution so this question is not relevant (to me) anymore. Thank you

covariance Over a year ago

Perhaps this is an aside, but this seems like a very critical point to me. I was testing out optimization with very simple equations just to see if CVXOPT was working, and for some reason I got those weird e-7, e-10, etc. answers. Then thanks to Anders' point, I somehow realized that for <= you have to include all four matrices for both Gx<h, Ax=b as if the <= were broken up into two separate equations. See the CVXOPT documentation for details.

Collectives™ on Stack Overflow

Python cvxopt ignores constraints

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related