Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System

Alexandre Belloni (bellonimit.edu)
Robert M. Freund (rfreundmit.edu)

Abstract: We present a general theory for transforming a homogeneous conic system F: Ax = 0, x \in C, x \ne 0, to an equivalent system via projective transformation induced by the choice of a point in a related dual set. Such a projective transformation serves to pre-condition the conic system into a system that has both geometric and computational properties with certain guarantees. There must exist projective transformations that transform F to a system whose complexity is strongly-polynomial-time in m and the barrier parameter. We present a method for generating such a projective transformation based on sampling in the dual set, with associated probabilistic analysis. Finally, we present computational results that indicate that this methodology holds the promise to markedly reduce the overall computation time for conic feasibility problems; for instance we observe a 46% decrease in average IPM iterations for 100 randomly generated poorly-behaved problem instances of dimension 1000 x 5000.

Keywords: conic programming, interior-point method, projective transformation, symmetry, random walk, probabilistic analysis

Category 1: Linear, Cone and Semidefinite Programming

Citation: MIT Operations Research Center Working Paper OR 375-05, May, 2005.

Download: [PDF]

Entry Submitted: 05/31/2005
Entry Accepted: 05/31/2005
Entry Last Modified: 05/31/2005

Modify/Update this entry