Line Search Failing?
Abzinger opened this issue · 1 comments
I'm using ECOS (Python) as a subroutine to solve Exponential Cone Programs. I have used it for two different projects and in both, I noticed that up 3% of the instances fail to be solved and the reason is
Combined backtracking failed 0 0 90 0 sigma 1
As a far as I understood from "Ecos" Thesis that problem lies in the line search.
The question is there something which I can do within ECOS to tune the line searching method?
ECOS output for the instance reported is
ECOS 2.0.4 - (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 +1e+03 1e+00 6e-01 1e+00 1e+00 --- --- 0 0 - | - -
1 -9.287e+00 -8.384e+00 +3e+01 1e+00 3e-02 1e+00 3e-02 0.9791 9e-03 1 1 1 | 1 0
2 -7.483e+00 -7.294e+00 +7e+00 3e-01 7e-03 2e-01 7e-03 0.7833 3e-02 1 1 1 | 1 1
3 -4.653e+00 -4.576e+00 +3e+00 2e-01 4e-03 8e-02 3e-03 0.6266 2e-01 1 1 1 | 3 2
4 -2.609e+00 -2.590e+00 +1e+00 7e-02 2e-03 2e-02 1e-03 0.9791 5e-01 1 1 1 | 6 0
5 -2.087e+00 -2.076e+00 +5e-01 2e-02 6e-04 1e-02 5e-04 0.6266 1e-01 1 1 1 | 1 2
6 -1.769e+00 -1.765e+00 +2e-01 8e-03 2e-04 4e-03 2e-04 0.7833 2e-01 1 1 1 | 3 1
7 -1.632e+00 -1.631e+00 +5e-02 2e-03 5e-05 6e-04 5e-05 0.9791 3e-01 1 1 1 | 4 0
8 -1.604e+00 -1.604e+00 +2e-02 9e-04 2e-05 2e-04 2e-05 0.6266 8e-02 1 1 1 | 2 2
9 -1.590e+00 -1.590e+00 +6e-03 3e-04 6e-06 6e-05 6e-06 0.7315 4e-02 1 1 1 | 1 1
10 -1.588e+00 -1.588e+00 +3e-03 1e-04 4e-06 3e-05 3e-06 0.4936 8e-02 1 1 1 | 1 3
11 -1.588e+00 -1.588e+00 +3e-03 1e-04 3e-06 3e-05 3e-06 0.1643 9e-01 2 1 1 | 12 8
12 -1.588e+00 -1.588e+00 +3e-03 1e-04 3e-06 3e-05 3e-06 0.0538 1e+00 2 1 0 | 22 13
13 -1.588e+00 -1.588e+00 +3e-03 1e-04 3e-06 3e-05 3e-06 0.0090 1e+00 1 1 0 | 32 21
14 -1.588e+00 -1.588e+00 +3e-03 1e-04 3e-06 3e-05 3e-06 0.0015 1e+00 1 1 0 | 41 29
15 -1.588e+00 -1.588e+00 +3e-03 1e-04 3e-06 3e-05 3e-06 0.0001 1e+00 2 1 0 | 55 43
16 -1.588e+00 -1.588e+00 +3e-03 1e-04 3e-06 3e-05 3e-06 0.0000 1e+00 1 1 0 | 64 53
17 -1.588e+00 -1.588e+00 +3e-03 1e-04 3e-06 3e-05 3e-06 0.0000 1e+00 2 1 0 | 71 60
18 -1.588e+00 -1.588e+00 +3e-03 1e-04 3e-06 3e-05 3e-06 0.0000 1e+00 2 1 0 | 79 67
19 -1.588e+00 -1.588e+00 +3e-03 1e-04 3e-06 3e-05 3e-06 0.0000 1e+00 2 1 1 | 90 80
Combined backtracking failed 0 0 90 0 sigma 1
Combined line search failed, recovering best iterate (11) and stopping.
NUMERICAL PROBLEMS (reached feastol=1.4e-04, reltol=1.9e-03, abstol=3.0e-03).
Runtime: 0.022761 seconds.
P.S. I have other similar instances. If anyone needs to test the instances, I can share the GitHub repository and explain how to use it.
P.P.S I opened the same issue in ecos-python repository.
Cheers
I see this issue often in my work. I think it might be related to how ECOS defines search directions with different types of cones. Specifically, I believe ECOS employs a Mehrotra corrector (or Mehrotra-like corrector) for LP and SOCP constraints but employs no such corrector for exponential cones. The thesis you cite relates to the original ECOS implementation. For the exponential cone, you should refer to Santiago's thesis: https://web.stanford.edu/group/SOL/dissertations/ThesisAkleAdobe-augmented.pdf. The concept of Mehrotra correctors for non-symmetric cones was not understood at the time of Santiago's thesis. Quoting from Chapter 10:
In this section we explore our variant of the Mehrotra predictor-corrector.
This variant has two important differences with respect to the original MPC.
It restricts the iterates to a region close to the central path, and since, for the
variables corresponding to the exponential cones no second-order information
is available, it only approximates the direction of the central path with respect
to the variables in the exponential cone to first order.
If ECOS were to be enhanced with a proper Mehrotra-corrector for the exponential cone (see https://docs.mosek.com/whitepapers/expcone.pdf), then I believe these issues would largely go away.