The modern theory of condition measures for convex optimization problems was initially developed for convex problems in conic format, and several aspects of the theory have now been extended to handle non-conic formats as well. In this theory, the (Renegar-) condition measure C(d) for a problem instance with data d=(A,b,c) has been shown to be connected to bounds on a wide variety of behavioral and computational characteristics of the problem instance, from sizes of optimal solutions to the complexity of algorithms. Herein we test the practical relevance of the condition measure theory, as applied to linear optimization problems that one might typically encounter in practice. Using the NETLIB suite of linear optimization problems as a test bed, we found that 71% of the NETLIB suite problem instances have infinite condition measure. In order to examine condition measures of the problems that are the actual input to a modern IPM solver, we also computed condition measures for the NETLIB suite problems after pre-preprocessing by CPLEX 7.1. Here we found that 19% of the post-processed problem instances in the NETLIB suite have infinite condition measure, and that log C(d) of the post-processed problems is fairly nicely distributed. Furthermore, there is a positive linear relationship between IPM iterations and log C(d) of the post-processed problem instances (significant at the 95% confidence level), and 42% of the variation in IPM iterations among the NETLIB suite problem instances is accounted for by log C(d) of the post-processed problem instances. / Singapore-MIT Alliance (SMA)
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/3716 |
| Date | 01 1900 |
| Creators | Ordóñez, Fernando, Freund, Robert M. |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | en_US |
| Detected Language | English |
| Type | Article |
| Format | 112963 bytes, application/pdf |
| Relation | High Performance Computation for Engineered Systems (HPCES); |
Page generated in 0.0021 seconds