11
$\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$

1 Answer 1

12
$\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$
4
  • $\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, 2014 at 20:19
  • 1
    $\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$ Nov 18, 2014 at 22:17
  • $\begingroup$ What if you were working in a special problem space where starting on the central path is possible? e.g. I want to solve for X, I have a warm start for X, and set my dual variable to be $S = \mu\cdot X^{-1}$? This is super naive so I know it must be broken, but how? $\endgroup$
    – Y. S.
    Feb 12 at 2:26
  • $\begingroup$ The central path is a set of points where $Ax=b$, $A^{T}y+s=c$, and $XS=\mu I$. After you've changed the problem data ($A$, $b$, or $c$), then you have a completely different central path. If you warm start the perturbed problem using an old $x$ and set $S=\mu X^{-1}$, then you won't have a point on the new central path because it will have lost primal and dual feasibility. $\endgroup$ Feb 12 at 3:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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