convergence issues on a small problem
Opened this issue · 13 comments
On a pretty small, seemingly well conditioned problem, ECOS is having trouble converging to an optimal solution. There are 17 variables, 13 equality constraints, 1 3-dim SOC cone, and 1 exponential cone. All coefficients are between 1 and 30 in magnitude. Is this behavior expected?
Here's the code:
import ECOS
import MathProgBase
I = [1,2,4,7,2,3,4,12,2,5,6,9,11,12,1,2,3,4,5,6,7,8,9,10,11,12,13]
J = [1,1,1,1,2,2,2,2,3,4,4,4,5,5,6,7,8,9,10,11,12,13,14,15,16,17,2]
V = [-1.0,1.0,2.0,-2.0,3.0,-1.0,3.0,1.0,1.0,-1.0,1.0,-1.0,-1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]
A = sparse(I,J,V)
b = [0.0,0.0,-1.0,30.0,1.0,1.0,0.0,1.0,0.0,1.0,0.0,7.0,6.0]
c = [0.0,0.0,1.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
var_cones = [(:Free,1:5),(:NonNeg,6:6),(:Zero,7:7),(:NonNeg,8:8),(:NonNeg,9:9),(:SOC,10:12),(:NonNeg,13:13),(:ExpPrimal,14:16),(:NonNeg,17:17)]
constr_cones = [(:Zero, 1:length(b))]
m = MathProgBase.ConicModel(ECOS.ECOSSolver(verbose=1))
MathProgBase.loadproblem!(m, c, A, b, constr_cones, var_cones)
MathProgBase.optimize!(m)
@show MathProgBase.status(m)
and the output:
ECOS 2.0.2 - (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 -0.000e+00 +9e+00 1e+00 7e-01 1e+00 1e+00 --- --- 0 0 - | - -
1 -6.411e+00 -5.568e+00 +3e+00 6e-01 4e-01 2e+00 3e-01 0.7603 1e-01 1 1 1 | 0 0
2 -1.390e+01 -1.327e+01 +7e-01 2e-01 1e-01 9e-01 8e-02 0.8315 9e-02 1 1 1 | 0 0
3 -1.746e+01 -1.736e+01 +1e-01 3e-02 2e-02 1e-01 1e-02 0.8853 4e-02 1 1 1 | 1 0
4 -1.783e+01 -1.778e+01 +4e-02 1e-02 9e-03 6e-02 5e-03 0.7188 2e-01 1 1 1 | 1 0
5 -1.790e+01 -1.784e+01 +2e-02 1e-02 6e-03 7e-02 3e-03 0.7593 5e-01 1 1 1 | 1 1
6 -1.804e+01 -1.803e+01 +3e-03 1e-03 6e-04 7e-03 3e-04 0.9438 5e-02 1 1 1 | 0 0
7 -1.803e+01 -1.802e+01 +5e-04 6e-04 3e-04 6e-03 5e-05 0.8786 1e-01 1 1 1 | 0 0
8 -1.802e+01 -1.802e+01 +3e-04 5e-04 2e-04 6e-03 3e-05 0.7370 4e-01 2 2 2 | 0 0
9 -1.802e+01 -1.802e+01 +9e-05 1e-04 5e-05 1e-03 1e-05 0.9021 2e-01 1 1 1 | 1 0
10 -1.802e+01 -1.801e+01 +6e-05 3e-04 7e-05 3e-03 6e-06 0.7798 5e-01 2 1 2 | 1 0
11 -1.801e+01 -1.801e+01 +7e-06 4e-05 8e-06 4e-04 8e-07 0.9698 1e-01 2 1 1 | 0 0
12 -1.801e+01 -1.801e+01 +2e-06 3e-05 4e-06 5e-04 2e-07 0.9629 3e-01 2 1 1 | 1 0
13 -1.800e+01 -1.800e+01 +5e-07 9e-06 1e-06 2e-04 6e-08 0.7647 4e-02 2 2 1 | 0 0
14 -1.800e+01 -1.800e+01 +3e-07 1e-05 2e-06 4e-04 3e-08 0.7915 4e-01 1 1 1 | 0 0
15 -1.800e+01 -1.800e+01 +5e-08 2e-06 2e-07 7e-05 5e-09 0.9773 1e-01 1 1 1 | 1 0
16 -1.800e+01 -1.800e+01 +2e-08 2e-06 2e-07 1e-04 2e-09 0.9227 3e-01 2 1 1 | 1 0
17 -1.800e+01 -1.800e+01 +4e-09 4e-07 4e-08 3e-05 4e-10 0.9293 1e-01 1 1 1 | 1 0
18 -1.800e+01 -1.800e+01 +2e-09 3e-07 2e-07 5e-05 2e-10 0.9471 3e-01 2 2 2 | 1 0
19 -1.800e+01 -1.800e+01 +3e-10 7e-08 4e-08 1e-05 3e-11 0.8567 4e-02 2 1 1 | 0 0
20 -1.800e+01 -1.800e+01 +2e-10 2e-07 2e-07 3e-05 2e-11 0.8921 5e-01 2 1 1 | 1 0
21 -1.800e+01 -1.800e+01 +3e-11 4e-08 4e-08 7e-06 4e-12 0.9791 2e-01 3 1 1 | 1 0
22 -1.800e+01 -1.800e+01 +8e-12 8e-08 1e-07 5e-06 8e-13 0.9388 1e-01 2 1 1 | 0 0
23 -1.800e+01 -1.800e+01 +2e-12 5e-08 6e-08 2e-06 3e-13 0.8282 2e-01 2 1 1 | 1 0
24 -1.800e+01 -1.800e+01 +2e-12 1e-07 1e-07 3e-06 2e-13 0.7535 4e-01 1 1 1 | 1 1
25 -1.800e+01 -1.800e+01 +3e-13 4e-08 5e-08 5e-07 3e-14 0.9791 8e-02 2 1 1 | 0 0
26 -1.800e+01 -1.800e+01 +1e-13 5e-08 7e-08 4e-07 1e-14 0.7833 2e-01 2 1 1 | 1 1
27 -1.800e+01 -1.800e+01 +4e-14 4e-08 5e-08 1e-07 4e-15 0.9791 1e-01 1 1 1 | 1 0
Combined backtracking failed 90 0 0 0 sigma 0.139985
Combined line search failed, recovering best iterate (17) and stopping.
Close to OPTIMAL (within feastol=3.9e-07, reltol=2.1e-10, abstol=3.8e-09).
Runtime: 0.001175 seconds.
cc @tiagoakle
@madeleineudell @mlubin I've looked a little into the issue. With the default parameters, the linear solver in ecos cannot achieve enough precision. It is not desired behavior but can happen. The final solution will require a better linear solver for ECOS. However, if you are confortable modifying the ECOS source, reduce the DELTASTAT constant defined in ecos.h from 10-7 to 10-8 and recompile the library.
#define DELTASTAT (1E-8) /* regularization parameter */
#define DELTA (2E-7) /* dyn. regularization parameter */
This problem will be solved to the desired precision.
Adding support for a flexible Krylov subspace method around the current IR and/or employing quad-precision residual evaluations would at least moderately improve the robustness. But determining when to activate said features is challenging (and a bad idea to always employ if trying to compete on wall-time).
I think the important boolean decision to be made is whether or not to solve the regularized or unregularized problem at each iteration (and different problems seem to lead to different answers as to which is faster in terms of wall-time, with always solving the regularized system sometimes preventing convergence).
My view here is that convergence has to take precedence over speed. Unless the linear solver issues can be rectified, ECOS' parameters like DELTASTAT should be changed. Perhaps DELTASTAT should be set smaller by default just for problems with nonsymmetric cones until heuristics for adaptively responding to convergence issues can be employed.
I agree that a comprehensive test suite is really the only way to proceed.
For example, the performance test for the main ECOS paper seems to be
non-representative in at least two ways:
-
The factorized KKT system is nearly diagonal.
-
The problem is 'easy' in the sense that there is no convergence
penalty in resolving the regularization within each IPM iteration. This issue is closely tied to the robustness of the linear solver and I believe that having a more extensive performance/robustness test suite would help soothe concerns about performance degradation in some "easy" problems.
On this subject, it would be very helpful (from a performance
perspective) to have the number of iterations reported in addition to
just the runtime.
And, as an aside, why not let DELTASTAT et al. be modifiable at
run-time? Surely there would not be a performance penalty.
EDIT: I meant to respond to jump-dev/Convex.jl#104, but I'll just leave this here since it isn't too out of place I suppose.
I'm happy to keep providing test instances that don't converge.
An ETH student, @liwidmer, has bulit a normal form equation solver for the SOCP case that, on synthetic tests, performs much better in terms of robustness than the current LDL based solver. We just need to find time to merge the code in. It's based on CHOLMOD. We could then switch to that solver whenever unreliable search directions are detected, so only a few times at the end of the IPM iterations. The code is in the sa_liwidmer branch, but needs to be heavily refactored first. If anybody is up for helping with the integration just shoot me an email.
@adomahidi, that's good news! How much of that is directly applicable to exponential cones?
@liwidmer @adomahidi Neat! Is it normal form for the sparse embedding or are the SOC barrier Hessians left dense?
It's using low rank updates to deal with the sparse+low rank structure of the NT scalings for the second order cones. @mlubin Not sure how much of it is directly applicable to exponential cones. When we stared this work Ecos was in 1.x without exp cone support. Need to discuss with @tiagoakle.
Have there been any updates on this issue? @mlubin has a mixed-integer exponential cone program solver that would benefit tremendously from a more robust exponential cone solver in ECOS.
At jump-dev/Convex.jl#104 (comment) I've provided another exponential cone problem in cvxpy format where ECOS fails to converge.