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

Abstract

In this paper we present a general theory for transforming a normalized homogeneous conic system F : Ax = 0, s'x = 1, x in C to an equivalent system via projective transformation induced by the choice of a point w in the set H'(s) = { v : s - A'v in C*}. Such a projective transformation serves to pre-condition the conic system into a system that has both geometric and computational properties with certain guarantees. We characterize both the geometric behavior and the computational behavior of the transformed system as a function of the symmetry of w in H'(s) as well as the complexity parameter of the barrier for C. Under the assumption that F has an interior solution, H'(s) must contain a point w whose symmetry is at least 1/m; if we can find a point whose symmetry is O(1/m) then we can projectively transform the conic system to one whose geometric properties and computational complexity will be strongly-polynomial-time in m and the barrier parameter. We present a method for generating such a point w based on sampling and on a geometric random walk on H'(s) with associated complexity and probabilistic analysis. Finally, we implement this methodology on randomly generated homogeneous linear programming feasibility problems, constructed to be poorly behaved. Our computational results indicate that the projective pre-conditioning 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 × 5000.