[Ipopt] About the rate of convergence for particular LP problem

[Илья Палачев]

Re-sending in plain-text form...
===

Hi,

Is possible to prove the rate of convergence of Ipopt solver for a given particular lP problem?

There are several papers mentioned in Ipopt documentation, that prove the convergence of the algorithm in a general case, e.g. papers [1,2]. I have a particular LP problem:

minimize eps
subject to
(u_i, x_i - x_j) >= 0 for each (i, j) in the fixed subset I of the set {1, ...., n}^2
| h_i - (u_i, x_i) | <= eps for each i = 1, ..., n

where:
eps is unknown scalar,
x_i are unknown 3D vectors,
u_i are fixed normalized 3D vectors,
h_i are fixed positive scalars,
i = 1, ..., n

I'm not a specialist in NLP optimization, so I'd be very grateful if anybody could direct me to any additional literature, theorems (in case if those mentioned are out-dated), or even whether this problem is worth to be tried to solve.

For my input data Ipopt runs ~300 seconds on Intel i5 CPU with 4 cores. From the Ipopt log it can be seen that it runs through the restoration phase, and memory reallocation in MA57. In [2] the Theorem 4.7 says that the algorithm has super-linear convergence rate if "Assumptions L" hold, which include that the algorithm doesn't fall into the restoration phase.

So my questions are:

(1) Am I right that if the algorithm has once fallen into restoration phase, then we cannot say anything about its rates of convergence, since the paper [1] proves only the convergence but not its rate?

(2) Is it possible to prove that the algorithm will *always* fall into the restoration phase for a given particular problem, or to obtain necessary/sufficient conditions for that?

(3) Is it possible that some Ipopt options can be tuned so that to work around the restoration phase (for my particular problem)?

[1] A. Wächter and L. T. Biegler. Line search filter methods for nonlinear programming: Motivation and global convergence.
SIAM Journal on Optimization, 16(1):1–31, 2005.
[2] A. Wächter and L. T. Biegler. Line search filter methods for nonlinear programming: Local convergence. SIAM Journal on Optimization, 16(1):32–48, 2005

————————
Best regards,
Ilya Palachev