10
$\begingroup$

I often encounter the general adage that interior point methods are difficult to warm start. Is there an intuitive explanation behind this advice? Are there situations in which one can expect benefits from warm starting in an interior point method? Can anyone recommend some helpful references on the topic?

$\endgroup$
11
$\begingroup$

Interior point methods work by following the central path to an optimal solution. When you change the objective function, the optimal solution from the previous version of the problem is far from the central path for the new problem, so it takes several iterations to get back to the central path and furthermore has to return to a fairly well centered solution. Then you have to work you way down the path to a new optimal solution. You might as well just start the interior point method from an arbitrary point.

In comparison, the simplex method (primal or dual) moves from vertex to vertex of the feasible set. In the typical case, a reasonably small change in the objective will result in a new optimal solution that is only a few simplex pivots away.

...added to the intuitive explanation above to give more detail...

In computational practice, experience simply hasn't shown any substantial benefit to warm starting primal-dual interior point methods. It isn't a feature of widely used codes like CPLEX and Gurobi (the companies that produce these packages would be certain to add such a feature if it was worth while), and there are relatively few papers discussing strategies for warm starting interior point methods.

Two references that I'll recommend are:

E. A. Yildirim and S. Wright. Warm-Start Strategies in Interior-Point Methods for Linear Programming. SIAM Journal on Optimization 12:782-810, 2002. This paper gives some nice theoretical bounds on some warm starting strategies. See http://pages.cs.wisc.edu/~swright/papers/YilW02a.pdf

A later paper coauthored by Yildirim gives some computational results, but the authors admit that simply cold starting is often faster in their tests than warm starting:

E. John and E. A. Yildirim. Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension. Computational Optimization and Applications. 41:151-183, 2008. See http://link.springer.com/article/10.1007/s10589-007-9096-y

$\endgroup$
  • $\begingroup$ I have to say I feel your explanation is a little lacking. For a problem which is a little bit ill-conditioned, finding a feasible point is already a problem by itself and most methods use "Phase I" methods to find this first feasible point. It is still unclear to me as to why can't you use a feasible point to at least skip that phase, if not to actually ensure success of the method. $\endgroup$ – olamundo Nov 18 '14 at 20:19
  • $\begingroup$ Actually, most implementations of primal-dual interior point methods use an infeasible (with respect to the equality constraints) starting point and work simultaneously on feasibility and optimality. There's no separate phase I. $\endgroup$ – Brian Borchers Nov 18 '14 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.