Optimization Online


Warmstarting the Homogeneous and Self-Dual Interior Point Method for Linear and Conic Quadratic Problems

Anders Skajaa (andsk***at***imm.dtu.dk)
Erling Andersen (e.d.andersen***at***mosek.com)
Ye Yinyu (yinyu-ye***at***stanford.edu)

Abstract: 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 comparing 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.

Keywords: Warmstart, Interior Point Method, Homogeneous model, Conic Programming

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: Submitted to Math. Prog. Comp., November 2011.


Entry Submitted: 02/08/2012
Entry Accepted: 02/08/2012
Entry Last Modified: 08/09/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society