Line Search Failing?

[Abzinger]

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]

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.