On Handling Free Variables in Interior-Point Methods for Conic Linear Optimization

Miguel F. Anjos (anjosstanfordalumni.org)
Samuel Burer (samuel-bureruiowa.edu)

Abstract: We revisit a regularization technique of Meszaros for handling free variables within interior-point methods for conic linear optimization. We propose a simple computational strategy, supported by a global convergence analysis, for handling the regularization. Using test problems from benchmark suites and recent applications, we demonstrate that the modern code SDPT3 modified to incorporate the proposed regularization is able to achieve the same or significantly better accuracy over standard options of splitting variables, using a quadratic cone, and solving indefinite systems.

Keywords: Infeasible primal-dual path-following algorithm, semidefinite programming, equality constraints, free variables, regularization.

Category 1: Linear, Cone and Semidefinite Programming

Citation: To appear in SIAM Journal on Optimization (accepted August 2007).

Download: [PDF]

Entry Submitted: 08/27/2006
Entry Accepted: 08/27/2006
Entry Last Modified: 08/03/2007

Modify/Update this entry