Projective re-normalization for improving the behavior of a homogeneous conic linear system |
| |
Authors: | Alexandre Belloni Robert M Freund |
| |
Institution: | (1) Fuqua School of Business, Duke University, 1 Towerview Drive, Durham, NC 27708, USA;(2) MIT Sloan School of Management, Building E53–357, 50 Memorial Drive, Cambridge, MA 02139-4307, USA |
| |
Abstract: | In this paper we study the homogeneous conic system . We choose a point that serves as a normalizer and consider computational properties of the normalized system . 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
, where the symmetry of 0 in isWe show that a solution of F can be computed in 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 and the image set and prove the existence of a normalizer such that provided that F has an interior solution. We develop a methodology for constructing a normalizer such that 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 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 × 5,000.
This research has been partially supported through the MIT-Singapore Alliance. |
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) 90C05 90C25 90C51 |
本文献已被 SpringerLink 等数据库收录! |
|