Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems
We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasib...
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/7931 |
| _version_ | 1826193519335702528 |
|---|---|
| author | Freund, Robert M. Ordóñez, Fernando Toh, Kim Chuan |
| author_facet | Freund, Robert M. Ordóñez, Fernando Toh, Kim Chuan |
| author_sort | Freund, Robert M. |
| collection | MIT |
| description | We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the correlation between these measures and IPM iteration counts (solved using the software SDPT3) when the measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.896), and is a very good predictor of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The near-absence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations. |
| first_indexed | 2024-09-23T09:40:25Z |
| format | Working Paper |
| id | mit-1721.1/7931 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:40:25Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/79312019-04-12T11:30:09Z Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems Freund, Robert M. Ordóñez, Fernando Toh, Kim Chuan problem instance behavior interior-point method semidefinite programming aggregate geometry IPM SDP We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the correlation between these measures and IPM iteration counts (solved using the software SDPT3) when the measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.896), and is a very good predictor of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The near-absence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations. 2005-03-04T19:58:06Z 2005-03-04T19:58:06Z 2005-03-04T19:58:06Z Working Paper http://hdl.handle.net/1721.1/7931 en_US Operations Research Center Working Paper Series;OR 374-05 288865 bytes application/pdf application/pdf |
| spellingShingle | problem instance behavior interior-point method semidefinite programming aggregate geometry IPM SDP Freund, Robert M. Ordóñez, Fernando Toh, Kim Chuan Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems |
| title | Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems |
| title_full | Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems |
| title_fullStr | Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems |
| title_full_unstemmed | Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems |
| title_short | Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems |
| title_sort | behavioral measures and their correlation with ipm iteration counts on semi definite programming problems |
| topic | problem instance behavior interior-point method semidefinite programming aggregate geometry IPM SDP |
| url | http://hdl.handle.net/1721.1/7931 |
| work_keys_str_mv | AT freundrobertm behavioralmeasuresandtheircorrelationwithipmiterationcountsonsemidefiniteprogrammingproblems AT ordonezfernando behavioralmeasuresandtheircorrelationwithipmiterationcountsonsemidefiniteprogrammingproblems AT tohkimchuan behavioralmeasuresandtheircorrelationwithipmiterationcountsonsemidefiniteprogrammingproblems |