文章基本信息

标题：Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems
本地全文：下载
作者：Skajaa, Anders ; Andersen, Erling D. ; Ye, Yinyu 等
期刊名称：Mathematical Programming Computation
印刷版ISSN：1867-2957
出版年度：2013
页码：1-25
DOI：10.1007/mpc.v0i0.101
语种：English
出版社：Mathematical Programming Computation
摘要：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.
关键词：90C25; 90C51; 90C05; 90C20