Computational experience and the explanatory value of condition numbers for linear optimization
Abstract in HTML and working paper for download in PDF available via World Wide Web at the Social Science Research Network.
| Other Authors: | |
|---|---|
| Language: | eng |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://papers2.ssrn.com/paper.taf?ABSTRACT%5FID=299326 http://hdl.handle.net/1721.1/5408 |
| _version_ | 1826198409575399424 |
|---|---|
| author2 | Ordóñez, Fernando, 1970- |
| author_facet | Ordóñez, Fernando, 1970- |
| collection | MIT |
| description | Abstract in HTML and working paper for download in PDF available via World Wide Web at the Social Science Research Network. |
| first_indexed | 2024-09-23T11:04:26Z |
| id | mit-1721.1/5408 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:04:26Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/54082019-04-10T10:36:21Z Computational experience and the explanatory value of condition numbers for linear optimization Ordóñez, Fernando, 1970- Freund, Robert M. Abstract in HTML and working paper for download in PDF available via World Wide Web at the Social Science Research Network. Title from cover. "January 2002." Includes bibliographical references (leaves 32-34). The goal of this paper is to develop some computational experience and test the practical relevance of the theory of condition numbers C(d) for linear optimization, as applied to problem instances that one might encounter in practice. We used the NETLIB suite of linear optimization problems as a test bed for condition number computation and analysis. Our computational results indicate that 72% of the NETLIB suite problem instances are ill-conditioned. However, after pre-processing heuristics are applied, only 19% of the post-processed problem instances are ill-conditioned, and log C(d) of the finitely-conditioned post-processed problems is fairly nicely distributed. We also show that the number of IPM iterations needed to solve the problems in the NETLIB suite varies roughly linearly (and monotonically) with log C(d) of the post-processed problem instances. Empirical evidence yields a positive linear relationship between IPM iterations and log C(d) for the post-processed problem instances, significant at the 95% confidence level. Furthermore, 42% of the variation in IPM iterations among the NETLIB suite problem instances is accounted for by log C(d) of the problem instances after pre-processing. Keywords: Convex Optimization, Complexity, Interior-Point Method, Barrier Method. Fernando Ordonez [and] Robert M. Freund. 2004-06-01T16:43:10Z 2004-06-01T16:43:10Z 2002 2002 4337-02 http://papers2.ssrn.com/paper.taf?ABSTRACT%5FID=299326 http://hdl.handle.net/1721.1/5408 eng Operations Research Center Working Paper;OR 361-02 http://papers2.ssrn.com/paper.taf?ABSTRACT%5FID=299326 34 leaves 2013959 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Computational experience and the explanatory value of condition numbers for linear optimization |
| title | Computational experience and the explanatory value of condition numbers for linear optimization |
| title_full | Computational experience and the explanatory value of condition numbers for linear optimization |
| title_fullStr | Computational experience and the explanatory value of condition numbers for linear optimization |
| title_full_unstemmed | Computational experience and the explanatory value of condition numbers for linear optimization |
| title_short | Computational experience and the explanatory value of condition numbers for linear optimization |
| title_sort | computational experience and the explanatory value of condition numbers for linear optimization |
| url | http://papers2.ssrn.com/paper.taf?ABSTRACT%5FID=299326 http://hdl.handle.net/1721.1/5408 |