search

cvxopt / smcp

Solver for sparse matrix cone programs
GNU General Public License v3.0
14 stars 3 forks source link

Solution of simple LP with redundant constraints fails. #8

Open Viech opened 6 years ago

Viech commented 6 years ago

A test case of mine solves the LP

max. x - y
s.t. x ≤  5
     y ≤  5
     x ≤ 10
     y ≤ 10
     x ≥  0
     y ≥  0

which contains redundant constraints but is strictly feasible and has a unique optimum solution.

So I'm calling smcp.solvers.conelp(c, G, h, dims) with

c:
[-1.00e+00]
[ 1.00e+00]

G:
[ 1.00e+00     0    ]
[    0      1.00e+00]
[ 1.00e+00     0    ]
[    0      1.00e+00]
[-1.00e+00     0    ]
[    0     -1.00e+00]

h:
[ 5.00e+00]
[ 5.00e+00]
[ 1.00e+01]
[ 1.00e+01]
[-0.00e+00]
[-0.00e+00]

dims:
{'l': 6, 'q': [], 's': []}

and smcp.solvers.options set to

{'abstol': 1e-08,
 'alpha': 0.1,
 'beta': 0.7,
 'cholmod': False,
 'debug': False,
 'delta': 0.9,
 'dimacs': True,
 'equalsteps': True,
 'eta': None,
 'feastol': 1e-08,
 'kktreg': 1e-06,
 'lifting': True,
 'maxiters': 1000000,
 'minstep': 1e-08,
 'order': 'AMD',
 'prediction': True,
 'refinement': 2,
 'reltol': 1e-07,
 'show_progress': True,
 'step': 0.98,
 't0': 0.1,
 'tnzcols': 0.1}

which gives the following output. Note that the primal-dual gap becomes as small as 2.0e-10 but the solver does not terminate. Instead, the dual solution goes wild in the following iterations. Note further that the values for pcost, dcost, and gap are inconsistent by a factor of 1e7 in the last line.

0.4.6                Extended self-dual embedding, primal scaling (Cholesky)
----------------------------------------------------------------------------
SDP var. size:       6 
Constraints:         2 (2|0)
Aggregate sparsity:  Chordal        NNZ(tril(V)) =       6
----------------------------------------------------------------------------
 it  pcost       dcost      gap     pres    dres    k/t     step    cputime
  0  3.0000e+01  0.0000e+00 6.0e+00 1.4e+00 8.9e-01 1.0e+00             0.0
  1  2.2126e+01  1.5824e-01 8.5e+00 1.1e+00 6.8e-01 1.7e+00 7.0e-01     0.0
  2  1.0729e+01  6.7340e-01 5.9e+00 5.3e-01 3.3e-01 1.6e+00 7.0e-01     0.0
  3  7.5665e+00  2.8146e+00 3.6e+00 2.6e-01 1.6e-01 9.0e-01 7.0e-01     0.0
  4  5.8614e+00  4.2363e+00 1.4e+00 9.0e-02 5.7e-02 3.5e-01 7.0e-01     0.0
  5  5.3186e+00  4.7896e+00 4.6e-01 2.9e-02 1.8e-02 1.0e-01 7.0e-01     0.0
  6  5.1051e+00  4.9322e+00 1.5e-01 9.4e-03 5.9e-03 3.3e-02 7.0e-01     0.0
  7  5.0344e+00  4.9780e+00 5.0e-02 3.1e-03 1.9e-03 1.1e-02 7.0e-01     0.0
  8  5.0112e+00  4.9928e+00 1.6e-02 1.0e-03 6.2e-04 3.4e-03 7.0e-01     0.0
  9  5.0037e+00  4.9976e+00 5.3e-03 3.2e-04 2.0e-04 1.1e-03 7.0e-01     0.0
 10  5.0012e+00  4.9992e+00 1.7e-03 1.1e-04 6.6e-05 3.6e-04 7.0e-01     0.0
 11  5.0004e+00  4.9997e+00 5.7e-04 3.4e-05 2.2e-05 1.2e-04 7.0e-01     0.0
 12  5.0001e+00  4.9999e+00 1.9e-04 1.1e-05 7.0e-06 3.7e-05 7.0e-01     0.0
 13  5.0000e+00  5.0000e+00 6.0e-05 3.7e-06 2.3e-06 1.2e-05 7.0e-01     0.0
 14  5.0000e+00  5.0000e+00 2.0e-05 1.2e-06 7.5e-07 3.9e-06 7.0e-01     0.0
 15  5.0000e+00  5.0000e+00 6.4e-06 3.9e-07 2.4e-07 1.3e-06 7.0e-01     0.0
 16  5.0000e+00  5.0000e+00 2.1e-06 1.3e-07 7.9e-08 4.1e-07 7.0e-01     0.0
 17  5.0000e+00  5.0000e+00 6.8e-07 4.1e-08 2.6e-08 1.3e-07 7.0e-01     0.0
 18  5.0000e+00  5.0000e+00 2.2e-07 1.3e-08 8.4e-09 4.3e-08 7.0e-01     0.0
 19  5.0000e+00  5.0000e+00 3.5e-08 2.0e-08 2.3e-08 8.6e-09 2.4e-01     0.1
 20  5.0000e+00  5.0000e+00 1.6e-08 1.6e-08 1.9e-08 4.7e-09 4.7e-03     0.1
 21  5.0000e+00  5.0000e+00 2.7e-08 2.0e-08 2.3e-08 4.6e-09 1.0e+00     0.1
 22  5.0000e+00  5.0000e+00 2.6e-09 1.3e-08 1.5e-08 4.6e-10 1.4e-02     0.1
 23  5.0000e+00  5.0000e+00 3.3e-08 8.5e-08 1.0e-07 5.7e-09 6.8e-03     0.1
 24  5.0000e+00  5.0000e+00 8.9e-09 5.6e-08 6.7e-08 1.7e-09 4.0e-02     0.1
 25  5.0000e+00  5.0000e+00 5.4e-08 2.0e-07 2.4e-07 1.0e-08 6.8e-03     0.1
 26  5.0000e+00  5.0000e+00 1.2e-08 1.2e-07 1.5e-07 2.6e-09 1.9e-04     0.1
 27  5.0000e+00  5.0000e+00 1.5e-09 6.6e-08 7.9e-08 3.9e-10 8.0e-04     0.1
 28  5.0000e+00  5.0000e+00 2.0e-10 3.5e-08 4.2e-08 8.1e-11 9.4e-05     0.1
 29  5.0000e+00  5.0000e+00 2.0e-09 2.0e-07 2.4e-07 6.4e-10 5.8e-02     0.1
 30  5.0000e+00  5.0000e+00 9.5e-10 1.4e-07 1.7e-07 3.5e-10 1.1e-03     0.1
 31  5.0000e+00  5.0000e+00 1.0e-08 8.9e-07 1.1e-06 3.2e-09 2.3e-05     0.1
 32  5.0000e+00  5.0000e+00 3.8e-09 5.9e-07 7.1e-07 1.4e-09 1.3e-04     0.1
 33  5.0000e+00  5.0000e+00 2.3e-08 2.2e-06 2.6e-06 7.3e-09 1.6e-03     0.1
 34  5.0000e+00  4.9999e+00 2.9e-07 1.6e-05 1.9e-05 8.1e-08 7.7e-06     0.1
 35  5.0000e+00  5.0000e+00 8.1e-08 7.7e-06 9.3e-06 2.4e-08 3.4e-01     0.1
 36  5.0000e+00  4.9998e+00 5.6e-07 3.1e-05 3.7e-05 1.4e-07 2.0e-02     0.1
 37  5.0000e+00  4.9994e+00 2.9e-06 9.6e-05 1.2e-04 6.7e-07 8.2e-02     0.1
 38  5.0000e+00  4.9998e+00 9.4e-07 3.0e-05 3.6e-05 1.8e-07 7.0e-01     0.1
 39  5.0000e+00  4.9999e+00 2.9e-07 9.2e-06 1.1e-05 5.7e-08 7.0e-01     0.1
 40  5.0000e+00  5.0000e+00 6.4e-08 4.8e-06 5.8e-06 1.4e-08 3.4e-01     0.1
 41  5.0000e+00  5.0000e+00 2.0e-08 3.2e-06 3.8e-06 5.7e-09 2.3e-03     0.1
 42  5.0000e+00  5.0000e+00 1.8e-08 3.0e-06 3.7e-06 5.3e-09 1.1e-03     0.1
 43  5.0000e+00  5.0000e+00 5.3e-08 5.6e-06 6.7e-06 9.0e-09 1.0e+00     0.1
 44  5.0000e+00  5.0000e+00 1.7e-09 2.9e-06 3.5e-06 3.0e-10 4.6e-05     0.1
 45  5.0000e+00  5.0000e+00 3.6e-10 1.8e-06 2.1e-06 7.4e-11 1.9e-06     0.1
 46  5.0000e+00  4.9999e+00 3.4e-09 8.9e-06 1.1e-05 6.3e-10 3.1e-07     0.1
 47  5.0000e+00  4.9998e+00 2.4e-08 3.6e-05 4.4e-05 4.3e-09 7.7e-06     0.1
 48  5.0000e+00  4.9999e+00 5.1e-09 2.2e-05 2.7e-05 1.0e-09 1.6e-05     0.1
 49  5.0000e+00  4.9999e+00 8.7e-10 1.3e-05 1.6e-05 2.4e-10 1.3e-06     0.1
 50  5.0000e+00  4.9996e+00 9.7e-09 7.6e-05 9.2e-05 2.2e-09 2.7e-06     0.1
 51  5.0000e+00  4.9975e+00 1.0e-07 4.3e-04 5.2e-04 2.0e-08 6.2e-09     0.1
 52  5.0000e+00  4.9436e+00 4.5e-06 9.8e-03 1.2e-02 8.4e-07 3.8e-06     0.1
 53  5.0000e+00  4.9815e+00 1.5e-06 3.2e-03 3.9e-03 2.8e-07 7.0e-01     0.1
 54  5.0000e+00  4.9941e+00 4.6e-07 1.0e-03 1.2e-03 8.5e-08 7.0e-01     0.1
 55  5.0000e+00  4.9966e+00 7.8e-08 5.9e-04 7.2e-04 1.8e-08 2.8e-02     0.1
 56  5.0000e+00  4.9976e+00 2.8e-08 4.1e-04 4.9e-04 8.2e-09 5.4e-06     0.2
 57  5.0000e+00  4.9979e+00 2.3e-08 3.7e-04 4.5e-04 6.9e-09 7.7e-06     0.2
 58  5.0000e+00  4.9561e+00 9.5e-07 7.6e-03 9.2e-03 2.3e-07 2.3e-03     0.2
 59  5.0000e+00  4.9986e+00 3.4e-07 2.4e-04 2.8e-04 5.7e-08 1.0e+00     0.2
 60  5.0000e+00  4.9993e+00 1.2e-08 1.2e-04 1.5e-04 2.4e-09 2.8e-02     0.2
 61  5.0000e+00  4.9995e+00 4.3e-09 8.7e-05 1.1e-04 1.2e-09 1.3e-06     0.2
 62  5.0000e+00  4.9995e+00 3.7e-09 8.2e-05 9.9e-05 1.1e-09 1.9e-06     0.2
 63  5.0000e+00  4.9995e+00 3.7e-09 8.2e-05 9.8e-05 1.1e-09 1.1e-05     0.2
 64  5.0000e+00  4.9995e+00 3.7e-09 8.2e-05 9.8e-05 1.1e-09 6.6e-05     0.2
 65  5.0000e+00  4.9995e+00 3.7e-09 8.2e-05 9.8e-05 1.1e-09 2.7e-04     0.2
 66  5.0000e+00  4.9995e+00 3.7e-09 8.2e-05 9.8e-05 1.1e-09 2.9e-11     0.2
 67  5.0000e+00  4.9992e+00 8.7e-09 1.3e-04 1.6e-04 1.5e-09 1.0e+00     0.2
 68  5.0000e+00  4.9996e+00 7.9e-10 7.1e-05 8.6e-05 1.5e-10 3.8e-06     0.2
 69  5.0000e+00  4.9997e+00 2.1e-10 4.6e-05 5.5e-05 5.1e-11 2.2e-07     0.2
 70  5.0000e+00  4.9999e+00 2.3e-11 2.4e-05 2.9e-05 8.6e-12 1.1e-07     0.2
 71  5.0000e+00  4.9999e+00 4.5e-12 1.2e-05 1.5e-05 2.1e-12 1.5e-07     0.2
 72  5.0000e+00  4.9995e+00 4.8e-11 8.3e-05 1.0e-04 2.0e-11 3.7e-08     0.2
 73  5.0000e+00  4.9981e+00 2.7e-10 3.2e-04 3.9e-04 1.1e-10 1.3e-08     0.2
 74  5.0000e+00  4.9990e+00 6.4e-11 1.7e-04 2.0e-04 2.9e-11 2.6e-08     0.2
 75  5.0000e+00  4.9900e+00 1.1e-09 1.7e-03 2.1e-03 4.2e-10 5.2e-08     0.2
 76  5.0000e+00  4.9941e+00 3.4e-10 1.0e-03 1.2e-03 1.6e-10 1.1e-07     0.2
 77  5.0000e+00  4.9732e+00 2.4e-09 4.7e-03 5.6e-03 9.8e-10 4.5e-07     0.2
 78  5.0000e+00  4.8614e+00 1.8e-08 2.4e-02 2.9e-02 7.1e-09 1.9e-06     0.2
 79  5.0000e+00  4.9242e+00 4.8e-09 1.3e-02 1.6e-02 2.2e-09 1.1e-07     0.2
 80  5.0000e+00  4.2792e+00 6.9e-08 1.2e-01 1.5e-01 3.0e-08 7.5e-08     0.2
 81  5.0000e+00  2.2975e+00 2.7e-07 4.7e-01 5.6e-01 1.5e-07 1.0e-09     0.2
 82  5.0000e+00  1.3138e+00 3.3e-07 6.4e-01 7.7e-01 2.3e-07 6.6e-05     0.2
 83  5.0000e+00  1.4608e+00 2.9e-07 6.1e-01 7.4e-01 2.1e-07 5.8e-02     0.2
 84  5.0000e+00  1.4663e+00 2.8e-07 6.1e-01 7.4e-01 2.1e-07 4.7e-03     0.2
 85  5.0000e+00  1.4670e+00 2.8e-07 6.1e-01 7.4e-01 2.1e-07 3.2e-05     0.2
 86  5.0000e+00  1.1034e+00 3.2e-07 6.8e-01 8.1e-01 2.3e-07 3.9e-04     0.2
 87  5.0000e+00  1.2552e+00 3.0e-07 6.5e-01 7.8e-01 9.4e-08 1.0e+00     0.2
 88  5.0000e+00  1.9198e+00 6.9e-07 5.3e-01 6.4e-01 1.6e-07 7.0e-01     0.2
 89  5.0000e+00  2.2421e+00 1.3e-06 4.8e-01 5.8e-01 2.1e-07 1.0e+00     0.2
 90  5.0000e+00  3.1052e+00 9.8e-07 3.3e-01 4.0e-01 2.0e-07 4.9e-01     0.2
 91  5.0000e+00  1.8335e+00 1.7e-06 5.5e-01 6.6e-01 4.7e-07 8.2e-02     0.2
 92  5.0000e+00  2.7154e+00 1.8e-06 4.0e-01 4.8e-01 4.4e-07 7.0e-01     0.2
 93  5.0000e+00  2.9712e+00 1.6e-06 3.5e-01 4.2e-01 2.8e-07 1.0e+00     0.3
 94  5.0000e+00  4.1374e+00 8.7e-07 1.5e-01 1.8e-01 2.1e-07 7.0e-01     0.3
 95  5.0000e+00  2.8009e+00 2.7e-06 3.8e-01 4.6e-01 7.9e-07 9.7e-03     0.3
 96  5.0000e+00  3.8443e+00 2.0e-06 2.0e-01 2.4e-01 5.2e-07 7.0e-01     0.3
 97  5.0000e+00  4.8105e+00 3.7e-07 3.3e-02 4.0e-02 1.3e-07 1.0e+00     0.3
 98  5.0000e+00  4.4020e+00 1.8e-06 1.0e-01 1.3e-01 5.5e-07 3.3e-03     0.3
 99  5.0000e+00  4.7966e+00 7.1e-07 3.5e-02 4.3e-02 1.9e-07 7.0e-01     0.3
100  5.0000e+00  4.8504e+00 3.8e-07 2.6e-02 3.1e-02 1.1e-07 1.7e-01     0.3
101  5.0000e+00  3.0188e+00 7.0e-06 3.4e-01 4.1e-01 2.3e-06 5.8e-02     0.3
102  5.0000e+00  3.7048e+00 5.3e-06 2.2e-01 2.7e-01 1.6e-06 4.9e-01     0.3
103  5.0000e+00  4.5751e+00 2.1e-06 7.4e-02 8.9e-02 4.5e-07 1.0e+00     0.3
104  5.0000e+00  4.8541e+00 7.3e-07 2.5e-02 3.1e-02 1.7e-07 7.0e-01     0.3
105  5.0000e+00  4.4101e+00 4.9e-06 1.0e-01 1.2e-01 1.1e-06 1.6e-03     0.3
106  5.0000e+00  4.7982e+00 1.8e-06 3.5e-02 4.2e-02 4.1e-07 7.0e-01     0.3
107  5.0000e+00  4.9056e+00 6.4e-07 1.6e-02 2.0e-02 1.6e-07 4.9e-01     0.3
108  5.0000e+00  4.9457e+00 2.8e-07 9.4e-03 1.1e-02 7.7e-08 3.4e-01     0.3
109  5.0000e+00  4.4578e+00 5.1e-06 9.4e-02 1.1e-01 1.2e-06 1.3e-04     0.3
110  5.0000e+00  4.8161e+00 1.8e-06 3.2e-02 3.8e-02 4.4e-07 7.0e-01     0.3
111  5.0000e+00  4.9435e+00 4.6e-07 9.8e-03 1.2e-02 1.2e-07 7.0e-01     0.3
112  5.0000e+00  4.9507e+00 3.4e-07 8.5e-03 1.0e-02 9.3e-08 9.7e-03     0.3
113  5.0000e+00  4.6616e+00 4.3e-06 5.9e-02 7.1e-02 1.0e-06 2.3e-03     0.3
114  5.0000e+00  4.8870e+00 1.5e-06 2.0e-02 2.4e-02 3.5e-07 7.0e-01     0.3
115  5.0000e+00  4.9644e+00 4.2e-07 6.2e-03 7.4e-03 1.0e-07 7.0e-01     0.3
116  5.0000e+00  4.8110e+00 4.2e-06 3.3e-02 4.0e-02 8.8e-07 5.8e-02     0.3
117  5.0000e+00  4.9929e+00 1.5e-07 1.2e-03 1.5e-03 4.3e-08 1.0e+00     0.3
118  5.0000e+00  4.9939e+00 1.1e-07 1.1e-03 1.3e-03 3.3e-08 2.7e-04     0.3
119  5.0000e+00  4.9940e+00 1.0e-07 1.0e-03 1.2e-03 3.1e-08 1.4e-02     0.3
120  5.0000e+00  4.9391e+00 2.0e-06 1.1e-02 1.3e-02 5.0e-07 2.7e-06     0.3
121  5.0000e+00  4.9804e+00 5.9e-07 3.4e-03 4.1e-03 1.6e-07 7.0e-01     0.3
122  5.0000e+00  4.8841e+00 7.0e-06 2.0e-02 2.4e-02 1.6e-06 1.7e-01     0.3
123  5.0000e+00  4.9600e+00 2.4e-06 6.9e-03 8.4e-03 6.3e-07 7.0e-01     0.3
124  5.0000e+00  4.9874e+00 7.8e-07 2.2e-03 2.6e-03 1.7e-07 7.0e-01     0.3
125  5.0000e+00  4.8603e+00 1.6e-05 2.4e-02 2.9e-02 3.4e-06 4.0e-02     0.3
126  5.0000e+00  4.9539e+00 5.4e-06 8.0e-03 9.6e-03 1.1e-06 7.0e-01     0.3
127  5.0000e+00  4.9853e+00 1.8e-06 2.6e-03 3.1e-03 3.4e-07 7.0e-01     0.3
128  5.0000e+00  4.9952e+00 5.9e-07 8.4e-04 1.0e-03 1.1e-07 7.0e-01     0.3
129  5.0000e+00  4.9795e+00 4.9e-06 3.6e-03 4.3e-03 8.8e-07 1.7e-01     0.3
130  5.0000e+00  4.9933e+00 1.6e-06 1.2e-03 1.4e-03 2.9e-07 7.0e-01     0.4
131  5.0000e+00  4.9977e+00 6.0e-07 4.0e-04 4.8e-04 1.1e-07 7.0e-01     0.4
132  5.0000e+00  4.9998e+00 4.7e-06 3.7e-05 4.5e-05 7.9e-07 1.0e+00     0.4
133  5.0000e+00  4.9999e+00 1.5e-06 1.2e-05 1.5e-05 2.6e-07 7.0e-01     0.4
134  5.0000e+00  5.0000e+00 5.0e-07 3.9e-06 4.7e-06 8.4e-08 7.0e-01     0.4
135  5.0000e+00  5.0000e+00 5.3e-08 1.9e-07 2.3e-07 8.9e-09 1.0e+00     0.4
136  5.0000e+00  5.0000e+00 1.0e-08 1.3e-07 1.5e-07 2.7e-09 1.4e-02     0.4
137  5.0000e+00  5.0000e+00 3.3e-09 8.1e-08 9.7e-08 1.0e-09 1.1e-03     0.4
138  5.0000e+00  5.0000e+00 3.1e-10 3.6e-08 4.3e-08 9.4e-11 3.9e-04     0.4
139  5.0000e+00  5.0000e+00 5.4e-11 1.8e-08 2.1e-08 1.8e-11 3.9e-04     0.4
140  5.0000e+00  5.0000e+00 9.7e-10 2.1e-07 2.5e-07 3.2e-10 1.6e-05     0.4
141  5.0000e+00  5.0000e+00 1.1e-08 1.6e-06 1.9e-06 3.7e-09 1.3e-04     0.4
142  5.0000e+00  5.0000e+00 1.3e-09 7.0e-07 8.5e-07 4.4e-10 8.0e-04     0.4
143  5.0000e+00  5.0000e+00 2.5e-10 3.4e-07 4.1e-07 8.4e-11 6.6e-05     0.4
144  5.0000e+00  5.0000e+00 3.4e-11 1.5e-07 1.8e-07 1.0e-11 3.2e-05     0.4
145  5.0000e+00  5.0000e+00 3.3e-12 6.7e-08 8.0e-08 9.9e-13 7.7e-06     0.4
146  5.0000e+00  5.0000e+00 1.5e-10 1.7e-06 2.1e-06 4.1e-11 1.3e-06     0.4
147  5.0000e+00  5.0000e+00 3.4e-11 9.7e-07 1.2e-06 1.1e-11 1.3e-06     0.4
148  5.0000e+00  4.9999e+00 1.4e-09 2.4e-05 2.9e-05 4.2e-10 1.3e-04     0.4
149  5.0000e+00  4.9999e+00 3.3e-10 1.3e-05 1.6e-05 1.2e-10 7.7e-06     0.4
150  5.0000e+00  4.9999e+00 1.4e-10 9.0e-06 1.1e-05 6.0e-11 3.8e-06     0.4
151  5.0000e+00  4.9996e+00 1.9e-09 7.1e-05 8.6e-05 6.8e-10 2.3e-05     0.4
152  5.0000e+00  4.9997e+00 9.1e-10 5.0e-05 6.0e-05 3.6e-10 6.6e-05     0.4
153  5.0000e+00  4.9990e+00 4.7e-09 1.7e-04 2.0e-04 1.6e-09 2.6e-08     0.4
154  5.0000e+00  4.9994e+00 2.0e-09 1.1e-04 1.4e-04 8.2e-10 6.6e-05     0.4
155  5.0000e+00  4.9994e+00 1.5e-09 9.6e-05 1.2e-04 6.4e-10 1.3e-06     0.4
156  5.0000e+00  4.9970e+00 1.4e-08 5.2e-04 6.3e-04 4.8e-09 1.6e-05     0.4
157  5.0000e+00  4.9979e+00 6.1e-09 3.6e-04 4.3e-04 2.5e-09 9.4e-05     0.4
158  5.0000e+00  4.9981e+00 5.0e-09 3.2e-04 3.9e-04 2.1e-09 5.2e-08     0.4
159  5.0000e+00  4.9119e+00 4.2e-07 1.5e-02 1.8e-02 1.5e-07 7.7e-06     0.4
160  5.0000e+00  4.9386e+00 2.0e-07 1.1e-02 1.3e-02 7.7e-08 2.8e-02     0.4
161  5.0000e+00  4.9491e+00 1.4e-07 8.8e-03 1.1e-02 5.7e-08 1.1e-03     0.4
162  5.0000e+00  4.4160e+00 2.5e-06 1.0e-01 1.2e-01 9.5e-07 2.3e-03     0.4
163  5.0000e+00  4.7698e+00 1.1e-06 4.0e-02 4.8e-02 3.0e-07 7.0e-01     0.4
164  5.0000e+00  4.7262e+00 2.0e-06 4.7e-02 5.7e-02 3.4e-07 1.0e+00     0.4
165  5.0000e+00  4.9087e+00 6.8e-07 1.6e-02 1.9e-02 1.2e-07 7.0e-01     0.4
166  5.0000e+00  4.9481e+00 1.0e-07 9.0e-03 1.1e-02 2.2e-08 2.8e-02     0.4
167  5.0000e+00  4.9671e+00 2.8e-08 5.7e-03 6.9e-03 7.1e-09 1.5e-09     0.4
168  5.0000e+00  4.9754e+00 1.4e-08 4.3e-03 5.1e-03 4.0e-09 5.2e-08     0.5
169  5.0000e+00  4.9761e+00 1.3e-08 4.1e-03 5.0e-03 3.8e-09 1.0e-09     0.5
170  5.0000e+00  4.9762e+00 1.3e-08 4.1e-03 5.0e-03 3.8e-09 1.1e-07     0.5
171  5.0000e+00  4.8240e+00 1.8e-07 3.1e-02 3.7e-02 4.4e-08 8.0e-04     0.5
172  5.0000e+00  4.8682e+00 8.8e-08 2.3e-02 2.8e-02 2.5e-08 1.9e-06     0.5
173  5.0000e+00  4.8828e+00 6.8e-08 2.0e-02 2.4e-02 2.0e-08 6.4e-07     0.5
174  5.0000e+00  3.1905e+00 1.5e-06 3.1e-01 3.8e-01 4.9e-07 6.6e-05     0.5
175  5.0000e+00  3.6597e+00 9.3e-07 2.3e-01 2.8e-01 3.0e-07 3.4e-01     0.5
176  5.0000e+00  3.8241e+00 8.0e-07 2.0e-01 2.5e-01 1.3e-07 1.0e+00     0.5
177  5.0000e+00  4.2787e+00 1.6e-07 1.3e-01 1.5e-01 4.0e-08 1.2e-01     0.5
178  5.0000e+00  4.5081e+00 5.7e-08 8.5e-02 1.0e-01 1.8e-08 1.5e-07     0.5
179  5.0000e+00  3.5286e+00 2.4e-07 2.6e-01 3.1e-01 7.6e-08 2.7e-06     0.5
180  5.0000e+00  2.3287e+00 4.8e-07 4.6e-01 5.6e-01 1.7e-07 2.3e-05     0.5
181  5.0000e+00  2.7376e+00 3.3e-07 3.9e-01 4.7e-01 1.3e-07 9.7e-03     0.5
182  5.0000e+00  1.4477e+00 5.0e-07 6.2e-01 7.4e-01 2.5e-07 8.0e-04     0.5
183  5.0000e+00  1.6690e+00 4.9e-07 5.8e-01 7.0e-01 2.1e-07 3.4e-01     0.5
184  5.0000e+00  1.1460e+00 5.6e-07 6.7e-01 8.1e-01 2.6e-07 4.7e-03     0.5
185  5.0000e+00  1.2635e+00 6.5e-07 6.5e-01 7.8e-01 2.6e-07 3.4e-01     0.5
186  5.0000e+00  1.6767e+00 8.6e-07 5.8e-01 6.9e-01 1.7e-07 1.0e+00     0.5
187  5.0000e+00  2.6173e+00 1.1e-06 4.1e-01 5.0e-01 2.2e-07 1.0e+00     0.5
188  5.0000e+00  3.6822e+00 7.8e-07 2.3e-01 2.8e-01 1.9e-07 7.0e-01     0.5
189  5.0000e+00  4.0791e+00 3.0e-07 1.6e-01 1.9e-01 8.5e-08 4.9e-01     0.5
190  5.0000e+00  2.2080e+00 1.0e-06 4.8e-01 5.8e-01 3.7e-07 1.6e-05     0.5
191  5.0000e+00  2.8380e+00 9.9e-07 3.7e-01 4.5e-01 3.0e-07 4.9e-01     0.5
192  5.0000e+00  3.1928e+00 9.3e-07 3.1e-01 3.8e-01 1.6e-07 1.0e+00     0.5
193  5.0000e+00  1.6066e+00 1.7e-06 5.9e-01 7.1e-01 4.6e-07 8.2e-02     0.5
194  5.0000e+00  2.0913e+00 1.9e-06 5.0e-01 6.1e-01 4.7e-07 4.9e-01     0.5
195  5.0000e+00  2.9872e+00 1.8e-06 3.5e-01 4.2e-01 4.4e-07 7.0e-01     0.5
196  5.0000e+00  3.9353e+00 1.1e-06 1.8e-01 2.2e-01 2.6e-07 1.0e+00     0.5
197  5.0000e+00  4.5649e+00 5.2e-07 7.5e-02 9.1e-02 1.2e-07 7.0e-01     0.5
198  5.0000e+00  3.8294e+00 2.0e-06 2.0e-01 2.4e-01 4.8e-07 9.7e-03     0.5
199  5.0000e+00  4.5575e+00 1.1e-06 7.7e-02 9.3e-02 2.5e-07 7.0e-01     0.5
200  5.0000e+00  4.8499e+00 3.9e-07 2.6e-02 3.1e-02 9.2e-08 7.0e-01     0.5
201  5.0000e+00  4.8845e+00 2.1e-07 2.0e-02 2.4e-02 5.5e-08 2.7e-04     0.5
202  5.0000e+00  4.4747e+00 1.6e-06 9.1e-02 1.1e-01 3.8e-07 6.4e-07     0.5
203  5.0000e+00  4.8109e+00 4.9e-07 3.3e-02 4.0e-02 1.2e-07 7.0e-01     0.5
204  5.0000e+00  4.8962e+00 1.0e-07 1.8e-02 2.2e-02 1.7e-08 1.0e+00     0.5
205  5.0000e+00  4.9427e+00 7.4e-09 9.9e-03 1.2e-02 1.7e-09 8.8e-09     0.5
206  5.0000e+00  4.8170e+00 4.2e-08 3.2e-02 3.8e-02 8.3e-09 4.5e-07     0.6
207  5.0000e+00  3.5801e+00 5.1e-07 2.5e-01 3.0e-01 1.1e-07 1.0e-11     0.6
208  5.0000e+00  3.9016e+00 2.3e-07 1.9e-01 2.3e-01 6.7e-08 2.3e-03     0.6
209  5.0000e+00  1.8470e+00 6.6e-07 5.5e-01 6.6e-01 2.7e-07 2.3e-03     0.6
210  5.0000e+00  2.2710e+00 6.5e-07 4.7e-01 5.7e-01 2.4e-07 3.4e-01     0.6
211  5.0000e+00  2.5755e+00 6.1e-07 4.2e-01 5.1e-01 1.0e-07 1.0e+00     0.6
212  5.0000e+00  3.1344e+00 2.3e-07 3.2e-01 3.9e-01 5.7e-08 4.7e-03     0.6
213  5.0000e+00  3.4040e+00 1.5e-07 2.8e-01 3.3e-01 4.3e-08 2.7e-04     0.6
214  5.0000e+00  3.4846e+00 1.4e-07 2.6e-01 3.2e-01 3.9e-08 9.4e-05     0.6
215  5.0000e+00  3.4978e+00 1.3e-07 2.6e-01 3.1e-01 3.9e-08 2.4e-12     0.6
216  5.0000e+00  3.4986e+00 1.3e-07 2.6e-01 3.1e-01 3.9e-08 2.3e-05     0.6
Terminated (small step size detected).
   Primal objective:                 5.00000011e+00
   Dual objective:                   3.49857298e+00
   Gap:                              1.33311954e-07
   Relative gap:                     3.81046657e-08
   Primal infeasibility:             2.60280205e-01
   Dual infeasibility:               3.13882550e-01
   Iterations:                       216
   CPU time:                         0.58
   CPU time per iteration:           0.00
   Real time:                        0.58
   Real time per iteration:          0.00

   DIMACS:  1.84e-01 0.00e+00 4.51e-01 0.00e+00 1.58e-01 1.40e-08

Another potentially related issue is that if I set the option debug to True, the solver raises an exception in or after the first iteration:

Traceback (most recent call last):
  […]
  File "/usr/lib/python3.7/site-packages/smcp/solvers.py", line 2368, in conelp
    sol = P.solve_esd(kktsolver=kktsolver)
  File "/usr/lib/python3.7/site-packages/smcp/base.py", line 263, in solve_esd
    dualstart=dualstart,p=p)
  File "/usr/lib/python3.7/site-packages/smcp/solvers.py", line 2231, in chordalsolver_esd
    dy,dX,dtau,dS,dkappa = newton(sigma)
  File "/usr/lib/python3.7/site-packages/smcp/solvers.py", line 1920, in newton
    u1,u2 = f(rtx,rty)
  File "/usr/lib/python3.7/site-packages/smcp/solvers.py", line 1864, in solve_
    r2 = blas.nrm2(rr)/blas.nrm2(by)
ZeroDivisionError: float division by zero

My version of blas is 3.8.0.

martinandersen commented 6 years ago

A few quick comments:

  1. The conelp routine in SMCP is a very basic wrapper that calls solver_esd which is not as robust as solver_feas. If you want to solve LPs, QPs, or SOCPs, I would not recommend SMCP since it maps everything to a sparse SDP—you're better of with conelp in CVXOPT. SMCP only has something to offer if you have one or more sparse psd cones.
  2. You'll notice that you almost have the desired accuracy (not the default accuracy) after 22 iterations, and then the rest is junk (numerical instability). You would probably be able to solve this problem to the desired accuracy with a more robust KKT-solver: solvers.conelp(c, G, h, dims, kktsolver='qr')
  3. The debug exception is a bug: this should probably be r2 = blas.nrm2(rr)/max(1.0,blas.nrm2(by)).
Viech commented 6 years ago

Helllo @martinandersen, thanks for your response! I understand that SMCP is primarily an SDP solver, but for integrating it into PICOS, I have to make the decision whether it is also available for solving conic problems with no LMIs (if the user chooses to do so), which means that it will have to pass the respective testbenches.

Unfortunately, while kktsolver = 'qr' does work around both #8 and #9, it gives me a subpar primal/dual solution for a different LP while it fails even harder for a variant of the problem above with a third pair of redundant constraints x, y ≤ 4 (this is part of a re-solving after modifications test, which for SMCP means solving the modified problem from scratch).

Should I disable SMCP for any problem without LMIs? Or would it be best to only solve pure SDPs with it, if I want the given accuracy? Are there any other options I can try?

martinandersen commented 6 years ago

I would recommend disabling SMCP for problems without LMIs — there is really no compelling reason to use it for such problems. SMCP's conelp routine is basically a proof-of-concept wrapper that allows you to solve conic problems using a sparse SDP solver. For sparse SDPs it is better to use solver_feas whenever possible.