Skip to main content
Journal cover image

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

Publication ,  Journal Article
Belloni, A; Freund, RM
Published in: Mathematical Programming
May 1, 2009

In this paper we study the homogeneous conic system F: Ax = 0, x in C setminus 0 . We choose a point in ∫ C that serves as a normalizer and consider computational properties of the normalized system Fs : Ax = 0, bar 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} Tx = 1, x in C, where the symmetry of 0 in Hs is (0, Hs) := α : y Hs → -α y in H. We show that a solution of F can be computed in O(√θ In (θ/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 equation pesented iterations, which is trongly-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 × 5,000. © 2007 Springer-Verlag.

Duke Scholars

Published In

Mathematical Programming

DOI

EISSN

1436-4646

ISSN

0025-5610

Publication Date

May 1, 2009

Volume

118

Issue

2

Start / End Page

279 / 299

Related Subject Headings

  • Operations Research
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0102 Applied Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Belloni, A., & Freund, R. M. (2009). Projective re-normalization for improving the behavior of a homogeneous conic linear system. Mathematical Programming, 118(2), 279–299. https://doi.org/10.1007/s10107-007-0192-7
Belloni, A., and R. M. Freund. “Projective re-normalization for improving the behavior of a homogeneous conic linear system.” Mathematical Programming 118, no. 2 (May 1, 2009): 279–99. https://doi.org/10.1007/s10107-007-0192-7.
Belloni A, Freund RM. Projective re-normalization for improving the behavior of a homogeneous conic linear system. Mathematical Programming. 2009 May 1;118(2):279–99.
Belloni, A., and R. M. Freund. “Projective re-normalization for improving the behavior of a homogeneous conic linear system.” Mathematical Programming, vol. 118, no. 2, May 2009, pp. 279–99. Scopus, doi:10.1007/s10107-007-0192-7.
Belloni A, Freund RM. Projective re-normalization for improving the behavior of a homogeneous conic linear system. Mathematical Programming. 2009 May 1;118(2):279–299.
Journal cover image

Published In

Mathematical Programming

DOI

EISSN

1436-4646

ISSN

0025-5610

Publication Date

May 1, 2009

Volume

118

Issue

2

Start / End Page

279 / 299

Related Subject Headings

  • Operations Research
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0102 Applied Mathematics