search

cvxpy / cvxpy

A Python-embedded modeling language for convex optimization problems.
https://www.cvxpy.org
Apache License 2.0
5.37k stars 1.05k forks source link

Inequality constraints unsatisfied when using SCS solver #304

Closed cvfish closed 8 years ago

cvfish commented 8 years ago

Tested on Ubuntu 14.04 and Python 2.7

In my example, I have an convex objective and some inequality constraints, shown as follows: constraints[i] = max_entries(bg_idepths) <= min_entries(fg_idepths) where bg_idepths and fg_idepths are some linear functions of optimization variables.

When I use SCS solver to solve this problem, the returned solution doesn't statisfy all these constraints. I check the .value of these constraints, some are statified, but some not.

I am wondering is there anything wrong ?

The output of the solver is attached here:

SCS v1.2.6 - Splitting Conic Solver
(c) Brendan O'Donoghue, Stanford University, 2012-2016

Lin-sys: sparse-indirect, nnz in A = 258121, CG tol ~ 1/iter^(2.00) eps = 1.00e-03, alpha = 1.50, max_iters = 2500, normalize = 1, scale = 1.00 Variables n = 14399, constraints m = 59017 Cones: primal zero / dual free vars: 1 linear vars: 25268 soc vars: 33748, soc blks: 2

Setup time: 8.01e-03s

Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)

 0|      inf       inf      -nan      -inf       inf       inf  3.35e-01

100| inf inf -nan -inf inf inf 1.61e+00 200| inf inf -nan -inf inf inf 4.34e+00 300| 2.87e+01 2.68e-02 8.20e-04 1.82e-03 1.00e-03 5.10e-16 7.95e+00 400| 7.49e+01 2.23e-02 2.30e-03 -2.18e-03 1.25e-04 5.08e-16 1.25e+01 500| 1.37e+02 1.26e-02 4.14e-03 -4.46e-03 -3.03e-04 5.04e-16 1.74e+01 600| 1.48e+02 1.67e-03 4.46e-03 -4.67e-03 -1.86e-04 4.99e-16 2.61e+01 700| 1.17e+02 7.69e-03 3.52e-03 -3.13e-03 4.00e-04 4.95e-16 3.26e+01 800| 6.11e+01 1.29e-02 1.83e-03 -5.61e-04 1.27e-03 4.93e-16 3.94e+01 900| 2.48e-01 1.36e-02 2.35e-05 2.23e-03 2.20e-03 4.93e-16 4.69e+01 1000| 4.93e+01 1.05e-02 1.50e-03 4.52e-03 3.01e-03 4.94e-16 5.39e+01 1100| 7.57e+01 5.15e-03 2.28e-03 5.86e-03 3.56e-03 4.96e-16 6.28e+01 1200| 7.66e+01 7.44e-04 2.29e-03 6.14e-03 3.82e-03 4.99e-16 6.96e+01 1300| 5.64e+01 5.07e-03 1.68e-03 5.54e-03 3.84e-03 5.01e-16 7.70e+01 1400| 2.46e+01 7.29e-03 7.27e-04 4.45e-03 3.72e-03 5.01e-16 8.37e+01 1500| 7.64e+00 7.08e-03 2.42e-04 3.33e-03 3.57e-03 5.01e-16 9.13e+01 1600| 3.14e+01 5.00e-03 9.54e-04 2.55e-03 3.51e-03 5.00e-16 1.02e+02 1700| 4.19e+01 1.98e-03 1.26e-03 2.32e-03 3.59e-03 4.99e-16 1.12e+02 1800| 3.89e+01 1.05e-03 1.17e-03 2.65e-03 3.82e-03 4.98e-16 1.20e+02 1900| 2.59e+01 3.10e-03 7.74e-04 3.39e-03 4.17e-03 4.97e-16 1.29e+02 2000| 8.52e+00 3.94e-03 2.50e-04 4.32e-03 4.57e-03 4.97e-16 1.41e+02 2100| 7.75e+00 3.55e-03 2.37e-04 5.20e-03 4.96e-03 4.97e-16 1.53e+02 2200| 1.87e+01 2.28e-03 5.64e-04 5.88e-03 5.31e-03 4.97e-16 1.64e+02 2300| 2.25e+01 6.91e-04 6.73e-04 6.25e-03 5.57e-03 4.98e-16 1.75e+02 2400| 1.94e+01 9.17e-04 5.78e-04 6.34e-03 5.76e-03 4.99e-16 1.84e+02

2500| 1.08e+01 1.94e-03 3.19e-04 6.20e-03 5.88e-03 4.99e-16 1.97e+02

Status: Solved/Inaccurate Hit max_iters, solution may be inaccurate Timing: Solve time: 1.97e+02s Lin-sys: avg # CG iterations: 104.41, avg solve time: 7.74e-02s

Cones: avg projection time: 8.57e-05s

Error metrics: dist(s, K) = 1.3784e-11, dist(y, K*) = 0.0000e+00, s'y/|s||y| = -6.4316e-13 |Ax + s - b|_2 / (1 + |b|_2) = 1.0788e+01 |A'y + c|_2 / (1 + |c|_2) = 1.9371e-03

|c'x + b'y| / (1 + |c'x| + |b'y|) = 3.1867e-04

c'x = 0.0062, -b'y = 0.0059

SteveDiamond commented 8 years ago

If you look at the SCS output, it says "Solved/Inaccurate". That means the solution isn't necessarily optimal. Try increasing the iteration limit (prob.solve(solver=SCS, max_iters=XXX)).

bodono commented 8 years ago

The primal residual at the end is huge, greater than 10. My guess is that the data are very poorly conditioned for your problem, you could try whitening the data before feeding the problem to cvxpy. You could also try increasing the 'scale' parameter that gets passed to scs.