search

embotech / ecos

A lightweight conic solver for second-order cone programming.
GNU General Public License v3.0
479 stars 123 forks source link

ECOS solver fails to converge on well-conditioned problem #187

Open junwei88 opened 4 years ago

junwei88 commented 4 years ago

The ECOS solver failed to converge on a fairly simple problem. As far as I can tell, the problem is well-conditioned and well-scaled, with coefficients, variables and objective function value between -10 and 10. The issue may be reproduced below:

import numpy as np
import cvxpy as cvx

np.random.seed(2)
n = 3000
alpha = np.random.normal(size=n)
sigma = np.ones(n) * 10

w = cvx.Variable(n)
objective = cvx.Maximize(w.T @ alpha - 0.5 * cvx.norm(cvx.multiply(sigma, w), 2))
constraints = [
    cvx.norm(w, 1) <= 1,
    w <= 1,
    w >= -1
]

# this problem fails
problem = cvx.Problem(objective, constraints)
problem.solve(solver=cvx.ECOS, verbose=True)

# however this equivalent problem with rescaled objective works
objective_2 = cvx.Maximize(w.T @ (alpha / 2) - 0.5 * cvx.norm(cvx.multiply(sigma / 2, w), 2))
problem_2 = cvx.Problem(objective_2, constraints)
problem_2.solve(solver=cvx.ECOS, verbose=True)

I understand that the -1 <= w <= 1 constraints are redundant in this case, but these box constraints are part of my more general problem. In other cases that I have tested with some of these binding, I have also occasionally encountered similar failures.

I am using CVXPY 1.1.1 with ECOS solver 2.0.7 and Numpy 1.16.5, on Python 3.7.4.

Shown below is the verbose output from the first and second problems:

ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +0.000e+00  -2.004e+04  +4e+04  3e-01  4e-02  1e+00  4e+00    ---    ---    2  1  - |  -  - 
 1  +1.164e+01  -2.993e+03  +9e+03  5e-02  5e-03  6e-01  7e-01  0.9188  1e-01   3  2  2 |  0  0
 2  -3.805e+00  -3.652e+02  +1e+03  6e-03  6e-04  7e-02  9e-02  0.9166  4e-02   3  3  3 |  0  0
 3  -3.262e+00  -1.095e+02  +3e+02  2e-03  2e-04  2e-02  3e-02  0.7148  1e-02   4  4  4 |  0  0
 4  -2.538e+00  -8.060e+01  +2e+02  1e-03  1e-04  2e-02  2e-02  0.3963  3e-01   5  5  5 |  0  0
 5  -2.378e+00  -3.121e+01  +9e+01  5e-04  5e-05  5e-03  7e-03  0.7804  2e-01   6  6  6 |  0  0
 6  -2.865e+00  -3.047e+01  +8e+01  5e-04  4e-05  5e-03  7e-03  0.3156  8e-01   9  9  9 |  0  0
 7  -2.437e+00  -2.170e+01  +6e+01  3e-04  3e-05  3e-03  5e-03  0.3446  2e-01   8  8  7 |  0  0
 8  -3.181e+00  -2.248e+01  +6e+01  3e-04  3e-05  3e-03  5e-03  0.5370  9e-01   1  1  1 |  0  0
 9  -2.114e+00  -1.138e+01  +3e+01  2e-04  1e-05  1e-03  2e-03  0.4852  1e-02   1  1  1 |  0  0
10  -2.159e+00  -7.614e+00  +2e+01  9e-05  6e-06  9e-04  1e-03  0.6587  4e-01   1  1  1 |  0  0
11  -2.189e+00  -6.880e+00  +2e+01  8e-05  5e-06  7e-04  1e-03  0.4153  7e-01   2  2  3 |  0  0
12  -2.199e+00  -6.060e+00  +1e+01  6e-05  5e-06  6e-04  1e-03  0.2944  5e-01   1  1  1 |  0  0
13  -2.175e+00  -3.300e+00  +4e+00  2e-05  1e-06  2e-04  3e-04  0.7723  7e-02   1  1  1 |  0  0
14  -2.126e+00  -2.591e+00  +1e+00  8e-06  5e-07  6e-05  1e-04  0.9053  4e-01   3  3  3 |  0  0
15  -2.167e+00  -2.472e+00  +9e-01  5e-06  3e-07  4e-05  8e-05  0.4346  3e-01   1  1  1 |  0  0
16  -2.268e+00  -2.497e+00  +9e-01  3e-06  2e-07  2e-05  8e-05  0.2453  6e-01   1  1  1 |  0  0
17  -2.343e+00  -2.442e+00  +1e+00  1e-06  8e-08  2e-06  8e-05  0.7877  4e-01   1  1  1 |  0  0
18  -2.321e+00  -2.339e+00  +1e+00  2e-07  1e-08  1e-06  1e-04  0.9263  1e-01   1  1  1 |  0  0
19  -2.345e+00  -2.348e+00  +2e+00  2e-07  1e-09  7e-07  1e-04  0.8785  1e-01   1  1  1 |  0  0
20  -2.384e+00  -2.384e+00  +4e+00  2e-07  1e-10  1e-06  3e-04  0.9890  2e-01   1  1  1 |  0  0
21  -2.464e+00  -2.464e+00  +1e+01  2e-07  1e-11  5e-07  9e-04  0.8400  2e-01   1  1  1 |  0  0
22  -2.371e+00  -2.371e+00  +2e+01  5e-08  4e-12  3e-06  2e-03  0.9890  4e-01   1  1  1 |  0  0
23  -2.482e+00  -2.482e+00  +1e+01  1e-07  9e-13  5e-07  1e-03  0.3478  3e-01   1  1  1 |  0  0
24  -2.314e+00  -2.314e+00  +1e+01  1e-07  8e-13  1e-06  1e-03  0.6785  3e-01   1  1  1 |  0  0
25  -2.366e+00  -2.366e+00  +2e+01  1e-07  6e-13  1e-06  2e-03  0.1050  8e-01   1  1  1 |  0  0
26  -2.480e+00  -2.480e+00  +1e+02  5e-08  2e-13  2e-06  1e-02  0.9890  9e-01   1  1  1 |  0  0
27  -2.375e+00  -2.375e+00  +2e+02  2e-08  8e-14  4e-06  2e-02  0.9890  4e-01   1  1  1 |  0  0
28  -2.426e+00  -2.426e+00  +3e+02  3e-08  8e-14  8e-07  2e-02  0.5278  2e-01   1  1  1 |  0  0
29  -2.357e+00  -2.357e+00  +4e+02  1e-08  3e-14  2e-06  4e-02  0.7551  2e-01   1  1  1 |  0  0
30  -2.472e+00  -2.472e+00  +3e+02  3e-08  5e-14  5e-07  2e-02  0.2992  3e-01   1  1  1 |  0  0
31  -2.305e+00  -2.305e+00  +4e+02  2e-08  2e-14  1e-06  3e-02  0.7517  4e-01   1  1  1 |  0  0
32  -2.447e+00  -2.447e+00  +1e+03  2e-08  3e-14  9e-07  1e-01  0.2539  1e+00   1  1  1 |  0  0
33  -2.366e+00  -2.366e+00  +2e+03  1e-08  1e-14  3e-06  1e-01  0.8188  6e-01   1  1  1 |  0  0
34  -2.481e+00  -2.481e+00  +6e+03  9e-09  2e-14  3e-06  5e-01  0.9584  9e-01   1  1  1 |  0  0
35  -2.358e+00  -2.358e+00  +7e+03  3e-09  7e-15  5e-06  6e-01  0.9890  4e-01   1  1  1 |  0  0
36  -2.475e+00  -2.475e+00  +9e+03  7e-09  1e-14  2e-06  8e-01  0.6557  6e-01   1  1  1 |  0  0
37  -2.261e+00  -2.261e+00  +7e+03  4e-09  8e-15  3e-06  6e-01  0.9890  4e-01   1  1  1 |  0  0
38  -2.327e+00  -2.327e+00  +5e+03  7e-09  3e-15  2e-06  4e-01  0.0305  7e-01   1  1  1 |  0  0
39  -2.276e+00  -2.276e+00  +9e+03  3e-09  2e-15  1e-06  7e-01  0.9890  5e-01   1  1  1 |  0  0
40  -2.374e+00  -2.374e+00  +7e+03  6e-09  5e-15  8e-07  5e-01  0.0791  6e-01   1  1  1 |  0  0
41  -2.215e+00  -2.215e+00  +5e+03  4e-09  4e-15  1e-06  4e-01  0.7626  3e-01   1  1  1 |  0  0
42  -2.251e+00  -2.251e+00  +4e+03  6e-09  2e-15  8e-07  3e-01  0.0070  1e+00   1  1  1 |  0  0
43  -2.409e+00  -2.409e+00  +4e+04  3e-09  5e-15  3e-07  3e+00  0.3366  7e-01   1  1  1 |  0  0
44  -2.387e+00  -2.387e+00  +1e+05  1e-09  3e-15  3e-06  9e+00  0.9890  5e-01   1  1  1 |  0  0
45  -2.485e+00  -2.485e+00  +3e+05  1e-09  3e-15  6e-07  2e+01  0.9171  4e-01   1  1  1 |  0  0
46  -2.388e+00  -2.388e+00  +5e+05  6e-10  1e-15  4e-06  4e+01  0.9890  5e-01   1  1  1 |  0  0
47  -2.500e+00  -2.500e+00  +1e+06  6e-10  2e-15  1e-06  9e+01  0.6802  5e-01   1  1  1 |  0  0
48  -2.309e+00  -2.309e+00  +9e+05  3e-10  6e-16  3e-06  8e+01  0.9051  4e-01   1  1  1 |  0  0
49  -2.415e+00  -2.415e+00  +8e+05  6e-10  6e-16  2e-06  6e+01  0.1300  1e+00   1  1  1 |  0  0
50  -2.254e+00  -2.254e+00  +5e+05  6e-10  5e-16  2e-06  4e+01  0.5786  3e-01   1  1  1 |  0  0
51  -2.349e+00  -2.349e+00  +6e+05  6e-10  3e-16  1e-06  5e+01  0.0489  1e+00   1  1  1 |  0  0
52  -2.220e+00  -2.220e+00  +5e+05  3e-10  3e-16  1e-06  5e+01  0.9435  4e-01   1  1  1 |  0  0
53  -2.269e+00  -2.269e+00  +3e+05  7e-10  1e-16  1e-06  2e+01  0.0119  1e+00   1  1  1 |  0  0
54  -2.186e+00  -2.186e+00  +3e+05  7e-10  4e-16  1e-06  2e+01  0.6015  6e-01   1  1  1 |  0  0
55  -2.195e+00  -2.195e+00  +3e+05  7e-10  3e-16  1e-06  2e+01  0.0005  9e-01   1  1  1 |  0  0
56  -2.253e+00  -2.253e+00  +3e+05  7e-10  9e-17  8e-07  3e+01  0.0099  1e+00   1  1  1 |  0  0
57  -2.405e+00  -2.405e+00  +6e+06  2e-10  6e-16  2e-07  5e+02  0.7214  6e-01   1  1  1 |  0  0
58  -2.464e+00  -2.464e+00  +2e+07  1e-10  4e-16  3e-06  2e+03  0.9890  5e-01   1  1  1 |  0  0
59  -2.396e+00  -2.396e+00  +4e+07  5e-11  2e-16  4e-06  3e+03  0.9890  4e-01   1  1  1 |  0  0
60  -2.450e+00  -2.450e+00  +6e+07  8e-11  2e-16  4e-07  5e+03  0.6402  2e-01   1  1  1 |  0  0
61  -2.350e+00  -2.350e+00  +9e+07  2e-11  5e-17  3e-06  8e+03  0.9890  3e-01   1  1  1 |  0  0
62  -2.463e+00  -2.463e+00  +4e+07  7e-11  1e-16  5e-07  4e+03  0.3473  3e-01   1  1  1 |  0  0
63  -2.217e+00  -2.217e+00  +4e+07  6e-11  1e-16  1e-06  3e+03  0.8556  3e-01   1  1  1 |  0  0
64  -2.234e+00  -2.234e+00  +4e+07  7e-11  9e-17  1e-06  3e+03  0.0020  9e-01   1  1  1 |  0  0
65  -2.384e+00  -2.384e+00  +5e+07  6e-11  4e-17  4e-07  5e+03  0.0746  9e-01   1  1  1 |  0  0
66  -2.183e+00  -2.183e+00  +2e+07  5e-11  8e-17  7e-07  2e+03  0.6559  2e-01   1  1  1 |  0  0
67  -2.191e+00  -2.191e+00  +2e+07  7e-11  7e-17  7e-07  2e+03  0.0036  8e-01   1  1  1 |  0  0
68  -2.219e+00  -2.219e+00  +2e+07  7e-11  5e-17  6e-07  2e+03  0.0019  9e-01   1  1  1 |  0  0
69  -2.180e+00  -2.180e+00  +3e+07  7e-11  6e-17  1e-06  2e+03  0.6182  8e-01   1  1  1 |  0  0
70  -2.181e+00  -2.181e+00  +3e+07  8e-11  6e-17  1e-06  2e+03  0.0001  1e+00   1  1  1 |  0  0
71  -2.199e+00  -2.199e+00  +3e+07  7e-11  5e-17  9e-07  2e+03  0.0011  1e+00   1  1  1 |  0  0
72  -2.276e+00  -2.276e+00  +4e+07  6e-11  1e-17  6e-07  4e+03  0.0206  9e-01   1  1  1 |  0  0
73  -2.410e+00  -2.410e+00  +6e+08  2e-11  6e-17  3e-07  5e+04  0.6718  5e-01   1  1  1 |  0  0
74  -2.473e+00  -2.473e+00  +2e+09  1e-11  4e-17  4e-06  2e+05  0.9890  7e-01   1  1  1 |  0  0
75  -2.378e+00  -2.378e+00  +3e+09  4e-12  2e-17  4e-06  3e+05  0.9890  4e-01   1  1  1 |  0  0
76  -2.437e+00  -2.437e+00  +4e+09  9e-12  2e-17  7e-07  4e+05  0.5470  2e-01   1  1  1 |  0  0
77  -2.347e+00  -2.347e+00  +8e+09  2e-12  5e-18  2e-06  6e+05  0.9890  3e-01   1  1  1 |  0  0
78  -2.459e+00  -2.459e+00  +5e+09  7e-12  1e-17  4e-07  5e+05  0.4477  2e-01   1  1  1 |  0  0
79  -2.312e+00  -2.312e+00  +6e+09  6e-12  3e-18  1e-06  5e+05  0.6890  4e-01   1  1  1 |  0  0
80  -2.443e+00  -2.443e+00  +3e+10  4e-12  7e-18  1e-06  2e+06  0.3337  1e+00   1  1  1 |  0  0
81  -2.339e+00  -2.339e+00  +3e+10  2e-12  2e-18  4e-06  3e+06  0.9886  5e-01   1  1  1 |  0  0
82  -2.446e+00  -2.446e+00  +8e+10  2e-12  5e-18  4e-06  7e+06  0.9368  9e-01   1  1  1 |  0  0
83  -2.421e+00  -2.421e+00  +2e+11  1e-12  3e-18  5e-06  1e+07  0.9890  6e-01   1  1  1 |  0  0
84  -2.405e+00  -2.405e+00  +3e+11  7e-13  2e-18  2e-06  3e+07  0.9890  4e-01   1  1  1 |  0  0
85  -2.361e+00  -2.361e+00  +5e+11  3e-13  1e-18  2e-06  4e+07  0.9890  2e-01   1  1  1 |  0  0
86  -2.454e+00  -2.454e+00  +6e+11  8e-13  2e-18  4e-07  5e+07  0.6078  2e-01   1  1  1 |  0  0
87  -2.309e+00  -2.309e+00  +9e+11  3e-13  6e-19  2e-06  7e+07  0.9890  4e-01   1  1  1 |  0  0
88  -2.426e+00  -2.426e+00  +5e+11  7e-13  7e-19  1e-06  5e+07  0.1460  9e-01   1  1  1 |  0  0
89  -2.294e+00  -2.294e+00  +4e+11  8e-13  3e-19  2e-06  3e+07  0.5459  4e-01   1  1  1 |  0  0
90  -2.287e+00  -2.287e+00  +8e+11  5e-13  2e-19  2e-06  7e+07  0.9890  7e-01   1  1  1 |  0  0
91  -2.358e+00  -2.358e+00  +1e+12  5e-13  5e-19  1e-06  1e+08  0.1590  4e-01   1  1  1 |  0  0
92  -2.401e+00  -2.401e+00  +5e+12  4e-13  7e-19  2e-06  4e+08  0.2571  1e+00   1  1  1 |  0  0
93  -2.444e+00  -2.444e+00  +1e+13  2e-13  5e-19  6e-06  1e+09  0.9890  6e-01   1  1  1 |  0  0
94  -2.258e+00  -2.258e+00  +5e+12  6e-14  2e-19  5e-06  5e+08  0.9825  3e-01   1  1  1 |  0  0
95  -2.315e+00  -2.315e+00  +3e+12  3e-13  1e-19  3e-06  3e+08  0.0642  4e-01   1  1  1 |  0  0
96  -2.192e+00  -2.192e+00  +2e+12  3e-13  3e-19  3e-06  2e+08  0.7883  5e-01   1  1  1 |  0  0
97  -2.197e+00  -2.197e+00  +2e+12  4e-13  2e-19  3e-06  2e+08  0.0019  9e-01   1  1  1 |  0  0
98  -2.334e+00  -2.334e+00  +6e+12  2e-13  2e-19  1e-06  5e+08  0.1242  9e-01   1  1  1 |  0  0
99  -2.416e+00  -2.416e+00  +3e+13  9e-14  3e-19  6e-07  3e+09  0.7886  3e-01   1  1  1 |  0  0
100  -2.445e+00  -2.445e+00  +1e+14  5e-14  2e-19  3e-06  8e+09  0.9890  5e-01   1  1  1 |  0  0
Maximum number of iterations reached, recovering best iterate (16) and stopping.

RAN OUT OF ITERATIONS (reached feastol=3.4e-06, reltol=4.1e-01, abstol=9.2e-01).
Runtime: 0.439599 seconds.

ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +0.000e+00  -1.323e+04  +3e+04  3e-01  5e-02  1e+00  3e+00    ---    ---    2  1  - |  -  - 
 1  +1.752e+02  -1.338e+03  +5e+03  4e-02  4e-03  5e-01  4e-01  0.9566  1e-01   3  2  2 |  0  0
 2  +1.223e+01  -9.891e+01  +4e+02  3e-03  3e-04  4e-02  3e-02  0.9248  2e-03   3  2  2 |  0  0
 3  -4.540e-01  -4.515e+00  +2e+01  1e-04  1e-05  9e-04  1e-03  0.9632  8e-04   4  3  3 |  0  0
 4  -6.547e-01  -3.226e+00  +1e+01  7e-05  6e-06  5e-04  9e-04  0.4580  3e-01   1  1  1 |  0  0
 5  -9.887e-01  -2.287e+00  +5e+00  3e-05  2e-06  2e-04  5e-04  0.9309  5e-01   1  1  1 |  0  0
 6  -1.036e+00  -1.868e+00  +3e+00  2e-05  2e-06  1e-04  3e-04  0.5075  3e-01   1  1  1 |  0  0
 7  -1.075e+00  -1.301e+00  +9e-01  6e-06  4e-07  3e-05  8e-05  0.8014  8e-02   1  1  1 |  0  0
 8  -1.083e+00  -1.100e+00  +7e-02  5e-07  3e-08  3e-06  6e-06  0.9323  5e-03   4  4  5 |  0  0
 9  -1.083e+00  -1.085e+00  +5e-03  4e-08  2e-09  2e-07  4e-07  0.9618  4e-02   3  3  2 |  0  0
10  -1.083e+00  -1.083e+00  +4e-04  3e-09  1e-10  1e-08  3e-08  0.9432  1e-02   2  2  2 |  0  0
11  -1.083e+00  -1.083e+00  +4e-05  1e-09  2e-11  1e-09  3e-09  0.9361  4e-02   2  2  2 |  0  0
12  -1.083e+00  -1.083e+00  +9e-06  4e-10  4e-12  3e-10  8e-10  0.8450  1e-01   2  2  2 |  0  0
13  -1.083e+00  -1.083e+00  +2e-06  2e-10  9e-13  7e-11  2e-10  0.9025  2e-01   1  1  1 |  0  0
14  -1.083e+00  -1.083e+00  +2e-07  5e-11  8e-14  7e-12  2e-11  0.9678  6e-02   2  2  2 |  0  0
15  -1.083e+00  -1.083e+00  +4e-09  2e-11  2e-15  1e-13  4e-13  0.9841  6e-03   2  2  2 |  0  0

OPTIMAL (within feastol=1.8e-11, reltol=4.1e-09, abstol=4.5e-09).
Runtime: 0.086484 seconds.

1.0833402080372803
abdullamuhammad commented 9 months ago

Were you able to figure out why? I'm having similar difficulty solving linear problems when the number of parameters gets to around 10,000. I can solve them with a manual gradient descent method, but CVXPY (specifically ECOS) breaks down. Any tips?