Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems

• Published in: Mathematical programming computation 2013-03, Vol.5 (1), p.1-25
• Main Authors: Skajaa, Anders, Andersen, Erling D., Ye, Yinyu
• Format: Article
• Language: English
• Subjects: Full Length Paper; Mathematics; Mathematics and Statistics; Mathematics of Computing; Operations Research/Decision Theory; Optimization; Theory of Computation
• ISSN: 1867-2949; 1867-2957
• DOI: 10.1007/s12532-012-0046-z

We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when compared to previously suggested strategies that require a pool of iterates from the solution process of the initial problem. Consequently our strategies are better suited for users who use optimization algorithms as black-box routines which usually only output the final solution. Our two strategies differ in that one assumes knowledge only of the final primal solution while the other assumes the availability of both primal and dual solutions. We analyze the strategies and deduce conditions under which they result in improved theoretical worst-case complexity. We present extensive computational results showing work reductions when warmstarting compared to coldstarting in the range 30–75% depending on the problem class and magnitude of the problem perturbation. The computational experiments thus substantiate that the warmstarting strategies are useful in practice.