Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System
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 transformati...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2005
|
| Online Access: | http://hdl.handle.net/1721.1/17074 |
| _version_ | 1811086313958408192 |
|---|---|
| author | Belloni, Alexandre Freund, Robert M. |
| author_facet | Belloni, Alexandre Freund, Robert M. |
| author_sort | Belloni, Alexandre |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:24:12Z |
| format | Working Paper |
| id | mit-1721.1/17074 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:24:12Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/170742019-04-12T11:30:10Z Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System Belloni, Alexandre Freund, Robert M. 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. 2005-06-01T14:59:14Z 2005-06-01T14:59:14Z 2005-05-31 Working Paper http://hdl.handle.net/1721.1/17074 en_US Operations Research Center Working Paper Series;OR 375-05 341787 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Belloni, Alexandre Freund, Robert M. Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System |
| title | Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System |
| title_full | Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System |
| title_fullStr | Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System |
| title_full_unstemmed | Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System |
| title_short | Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System |
| title_sort | projective pre conditioners for improving the behavior of a homogeneous conic linear system |
| url | http://hdl.handle.net/1721.1/17074 |
| work_keys_str_mv | AT bellonialexandre projectivepreconditionersforimprovingthebehaviorofahomogeneousconiclinearsystem AT freundrobertm projectivepreconditionersforimprovingthebehaviorofahomogeneousconiclinearsystem |