-

 

 

 




Optimization Online





 

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

Sertalp B. Çay (sertalpbilal***at***gmail.com)
Imre Pólik (imre.polik***at***sas.com)
Tamás Terlaky (terlaky***at***lehigh.edu)

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

Keywords: mixed integer optimization, conic optimization, interior point method, branch and bound, warm-start

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

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

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

Download: [PDF]

Entry Submitted: 05/08/2017
Entry Accepted: 05/08/2017
Entry Last Modified: 05/10/2017

Modify/Update this entry


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

 

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