Projective re-normalization for improving the behavior of a homogeneous conic linear system

• 成果类型: Article
• 署名作者: Belloni, Alexandre; Freund, Robert M.
• 署名单位: Massachusetts Institute of Technology (MIT); Duke University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0192-7
• 发表日期: 2009
• 页码: 279-299
• 关键词: polyhedron; number; volume

摘要

In this paper we study the homogeneous conic system F : Ax = 0, is an element of C\{0}. We choose a point (s) over bar. is an element of intC* that serves as a normalizer and consider computational properties of the normalized system F (s) over bar : Ax = 0, s(-T) x = 1, x is an element of C. We show that the computational complexity of solving F via an interior-point method depends only on the complexity value v of the barrier for C and on the symmetry of the origin in the image set H ((s)) over bar := {Ax: (s) over bar (T) x = 1, x is an element of C}, where the symmetry of 0 in H (s) over bar is sym(0, H ((s)) over bar) := max{alpha : y is an element of H (s) over bar double right arrow alpha y is an element of H (s) over bar}. We show that a solution of F can be computed in O(root v ln (v/sym (0, H ((s)) over bar) 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 F ((s)) over bar and the image set H ((s)) over bar and prove the existence of a normalizer (s) over bar such that sym(0, H ((s)) over bar) = 1/m provided that F has an interior solution. We develop a methodology for constructing a normalizer (s) over bar such that sym(0, H ((s)) over bar) >= 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(root v ln (mv)) 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 1,000 x 5,000.