PROJECTIVE RE-NORMALIZATION FOR IMPROVING THE BEHAVIOR OF A HOMOGENEOUS CONIC LINEAR

Abstract. In this paper we study the homogeneous conic system F: Ax = 0, x ∈ C \ {0}. We choose a point s ̄ ∈ intC ∗ that serves as a normalizer and consider computational properties of the normalized system Fs ̄ : Ax = 0, s̄T x = 1, x ∈ C. We show that the computational complexity of solving F via an interior-point method depends only on the complexity value ϑ of the barrier for C and on the symmetry of the origin in the image set Hs ̄: = {Ax: s̄T x = 1, x ∈ C}, where the symmetry of 0 in Hs ̄ is sym(0, Hs̄): = max{α: y ∈ Hs ̄ ⇒ −αy ∈ Hs̄}. We show that a solution of F can be computed in O( ϑ ln(ϑ/sym(0, Hs̄)) interior-point iterations. In order to improve the theoretical and practical computation of a solution of F, we next present a general theory for projective re-normalization of the feasible region Fs ̄ and the image set Hs ̄ and prove the existence of a normalizer s ̄ such that sym(0, Hs̄) ≥ 1/m provided that F has an interior solution. We develop a methodology for constructing a normalizer s ̄ such that sym(0, Hs̄) ≥ 1/m with high probability, based on sampling on a geometric random walk with associated probabilistic complexity analysis. While such a normalizer is not itself computable in strongly-polynomial-time, the normalizer will yield a conic system that is solvable in O( ϑ ln(mϑ)) iterations, which is strongly-polynomial-time. 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 re-normalization 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. 1