1 Department of Applied Mathematics and Computer Science, Technical University of Denmark2 Scientific Computing, Department of Applied Mathematics and Computer Science, Technical University of Denmark3 Department of Informatics and Mathematical Modeling, Technical University of Denmark4 Stanford University5 Stanford University
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.
Mathematical Programming Computation, 2013, Vol 5, Issue 1, p. 1-25
Warmstart; Interior point method; Homogeneous model; Conic programming