On the explanatory value of condition numbers for convex optimization : theoretical issues and computational experience
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/29261 |
| _version_ | 1826194801530241024 |
|---|---|
| author | Ordóñez, Fernando, 1970- |
| author2 | Robert M. Freund. |
| author_facet | Robert M. Freund. Ordóñez, Fernando, 1970- |
| author_sort | Ordóñez, Fernando, 1970- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002. |
| first_indexed | 2024-09-23T10:02:20Z |
| format | Thesis |
| id | mit-1721.1/29261 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:02:20Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/292612019-04-12T08:53:51Z On the explanatory value of condition numbers for convex optimization : theoretical issues and computational experience Ordóñez, Fernando, 1970- Robert M. Freund. Sloan School of Management. Sloan School of Management. Sloan School of Management. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002. Includes bibliographical references (p. 213-216). The modern theory of condition numbers for convex optimization problems was developed for convex problems in conic format: ... The condition number C(d) for (CPd) has been shown in theory to provide upper and/or lower bounds on many behavioral and computational characteristics of (CPd), from sizes of feasible and optimal solutions to the complexity of algorithms for solving (CPd). However, it is not known to what extent these bounds might be reasonably close to their actual measures of interest. One difficulty in testing the practical relevance of such theoretical bounds is that most practical problems are not presented in conic format. While it is usually easy to transform convex optimization problems into conic format, such transformations are not unique and do not maintain the original data, making this strategy somewhat irrelevant for computational testing of the theory. The purpose of this thesis is to overcome the obstacles stated above. We introduce an extension of condition number theory to include convex optimization problems not in conic form, and is thus more amenable to computational evaluation. This extension considers problems of the form: ... where P is a closed convex set, no longer required to be a cone. We extend many results of condition number theory to problems of form (GPd), including bounds on optimal solution sizes, optimal objective function values, interior-point algorithm complexity, etc. (cont.) We also test the practical relevance of condition number bounds on quantities of interest for linear optimization problems. We use the NETLIB suite of linear optimization problems as a test-bed for condition number computation and analysis. Our computational results indicate that: (i) most of the NETLIB suite problems have infinite condition number (prior to pre-processing heuristics) (ii) there exists a positive linear relationship between the IPM iterations and log C(d) for the post-processed problem instances, which accounts for 42% of the variation in IPM iterations, (iii) condition numbers provide fairly tight upper bounds on the sizes of minimum-norm feasible solutions, and (iv) condition numbers provide fairly poor upper bounds on the sizes of optimal solutions and optimal objective function values. by Fernando Ordóñez. Ph.D. 2005-10-14T19:30:40Z 2005-10-14T19:30:40Z 2002 2002 Thesis http://hdl.handle.net/1721.1/29261 51896548 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 216 p. 6442537 bytes 6442344 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Sloan School of Management. Ordóñez, Fernando, 1970- On the explanatory value of condition numbers for convex optimization : theoretical issues and computational experience |
| title | On the explanatory value of condition numbers for convex optimization : theoretical issues and computational experience |
| title_full | On the explanatory value of condition numbers for convex optimization : theoretical issues and computational experience |
| title_fullStr | On the explanatory value of condition numbers for convex optimization : theoretical issues and computational experience |
| title_full_unstemmed | On the explanatory value of condition numbers for convex optimization : theoretical issues and computational experience |
| title_short | On the explanatory value of condition numbers for convex optimization : theoretical issues and computational experience |
| title_sort | on the explanatory value of condition numbers for convex optimization theoretical issues and computational experience |
| topic | Sloan School of Management. |
| url | http://hdl.handle.net/1721.1/29261 |
| work_keys_str_mv | AT ordonezfernando1970 ontheexplanatoryvalueofconditionnumbersforconvexoptimizationtheoreticalissuesandcomputationalexperience |