search

embotech / ecos

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

Line Search Failing? #177

Open Abzinger opened 5 years ago

Abzinger commented 5 years ago

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

rileyjmurray commented 3 years ago

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.