Condition-Measure Bounds on the Behavior of the Central Trajectory of a Semi-Definete Program
We present bounds on various quantities of interest regarding the central trajectory of a semi-definite program (SDP), where the bounds are functions of Renegar's condition number C(d) and other naturally-occurring quantities such as the dimensions n and m. The condition number C(d) is defined...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/5132 |
| _version_ | 1826212880763060224 |
|---|---|
| author | Nunez, Manuel A. Freund, Robert M. |
| author_facet | Nunez, Manuel A. Freund, Robert M. |
| author_sort | Nunez, Manuel A. |
| collection | MIT |
| description | We present bounds on various quantities of interest regarding the central trajectory of a semi-definite program (SDP), where the bounds are functions of Renegar's condition number C(d) and other naturally-occurring quantities such as the dimensions n and m. The condition number C(d) is defined in terms of the data instance d = (A, b, C) for SDP; it is the inverse of a relative measure of the distance of the data instance to the set of ill-posed data instances, that is, data instances for which arbitrary perturbations would make the corresponding SDP either feasible or infeasible. We provide upper and lower bounds on the solutions along the central trajectory, and upper bounds on changes in solutions and objective function values along the central trajectory when the data instance is perturbed and/or when the path parameter defining the central trajectory is changed. Based on these bounds, we prove that the solutions along the central trajectory grow at most linearly and at a rate proportional to the inverse of the distance to ill-posedness, and grow at least linearly and at a rate proportional to the inverse of C(d)2 , as the trajectory approaches an optimal solution to the SDP. Furthermore, the change in solutions and in objective function values along the central trajectory is at most linear in the size of the changes in the data. All such bounds involve polynomial functions of C(d), the size of the data, the distance to ill-posedness of the data, and the dimensions n and m of the SDP. |
| first_indexed | 2024-09-23T15:39:37Z |
| format | Working Paper |
| id | mit-1721.1/5132 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:39:37Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51322019-04-12T08:17:13Z Condition-Measure Bounds on the Behavior of the Central Trajectory of a Semi-Definete Program Nunez, Manuel A. Freund, Robert M. Semi-definite programming, Perturbation of convex programs, Central trajectory, Interior point methods, Ill-posed problems, Condition numbers. We present bounds on various quantities of interest regarding the central trajectory of a semi-definite program (SDP), where the bounds are functions of Renegar's condition number C(d) and other naturally-occurring quantities such as the dimensions n and m. The condition number C(d) is defined in terms of the data instance d = (A, b, C) for SDP; it is the inverse of a relative measure of the distance of the data instance to the set of ill-posed data instances, that is, data instances for which arbitrary perturbations would make the corresponding SDP either feasible or infeasible. We provide upper and lower bounds on the solutions along the central trajectory, and upper bounds on changes in solutions and objective function values along the central trajectory when the data instance is perturbed and/or when the path parameter defining the central trajectory is changed. Based on these bounds, we prove that the solutions along the central trajectory grow at most linearly and at a rate proportional to the inverse of the distance to ill-posedness, and grow at least linearly and at a rate proportional to the inverse of C(d)2 , as the trajectory approaches an optimal solution to the SDP. Furthermore, the change in solutions and in objective function values along the central trajectory is at most linear in the size of the changes in the data. All such bounds involve polynomial functions of C(d), the size of the data, the distance to ill-posedness of the data, and the dimensions n and m of the SDP. 2004-05-28T19:24:36Z 2004-05-28T19:24:36Z 1999-08 Working Paper http://hdl.handle.net/1721.1/5132 en_US Operations Research Center Working Paper;OR 350-01 1744 bytes 1532822 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Semi-definite programming, Perturbation of convex programs, Central trajectory, Interior point methods, Ill-posed problems, Condition numbers. Nunez, Manuel A. Freund, Robert M. Condition-Measure Bounds on the Behavior of the Central Trajectory of a Semi-Definete Program |
| title | Condition-Measure Bounds on the Behavior of the Central Trajectory of a Semi-Definete Program |
| title_full | Condition-Measure Bounds on the Behavior of the Central Trajectory of a Semi-Definete Program |
| title_fullStr | Condition-Measure Bounds on the Behavior of the Central Trajectory of a Semi-Definete Program |
| title_full_unstemmed | Condition-Measure Bounds on the Behavior of the Central Trajectory of a Semi-Definete Program |
| title_short | Condition-Measure Bounds on the Behavior of the Central Trajectory of a Semi-Definete Program |
| title_sort | condition measure bounds on the behavior of the central trajectory of a semi definete program |
| topic | Semi-definite programming, Perturbation of convex programs, Central trajectory, Interior point methods, Ill-posed problems, Condition numbers. |
| url | http://hdl.handle.net/1721.1/5132 |
| work_keys_str_mv | AT nunezmanuela conditionmeasureboundsonthebehaviorofthecentraltrajectoryofasemidefineteprogram AT freundrobertm conditionmeasureboundsonthebehaviorofthecentraltrajectoryofasemidefineteprogram |