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.
Citation
MIT Operations Research Center Working Paper OR 375-05, May, 2005.
Article
View Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System