Warm-start of interior point methods for second order cone optimization via rounding over optimal Jordan frames

Interior point methods (IPM) are the most popular approaches to solve Second Order Cone Optimization (SOCO) problems, due to their theoretical polynomial complexity and practical performance. In this paper, we present a warm-start method for primal-dual IPMs to reduce the number of IPM steps needed to solve SOCO problems that appear in a Branch and Conic Cut (BCC) tree when solving Mixed Integer Second Order Cone Optimization (MISOCO) problems. Our method exploits the optimal Jordan frame of a related subproblem and provides a conic feasible primal-dual initial point for the self-dual embedding model by solving two auxiliary linear optimization problems. Numerical results on test problems in the CBLIB library show on average around 61% reduction of the IPM iterations for a variety of MISOCO problems.

Citation

Sertalp B. Çay, Imre Pólik, and Tamás Terlaky. Warm-start of interior point methods for second order cone optimization via rounding over optimal Jordan frames. Technical Report 17T-006, Lehigh University, May 2017

Article

Download

View Warm-start of interior point methods for second order cone optimization via rounding over optimal Jordan frames