Robust optimization
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/17725 |
| _version_ | 1826204003292151808 |
|---|---|
| author | Sim, Melvyn |
| author2 | Dimitris J. Bertsimas. |
| author_facet | Dimitris J. Bertsimas. Sim, Melvyn |
| author_sort | Sim, Melvyn |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. |
| first_indexed | 2024-09-23T12:47:36Z |
| format | Thesis |
| id | mit-1721.1/17725 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:47:36Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/177252023-03-01T02:09:39Z Robust optimization Sim, Melvyn Dimitris J. Bertsimas. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Operations Research Center. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. Includes bibliographical references (p. 169-171). We propose new methodologies in robust optimization that promise greater tractability, both theoretically and practically than the classical robust framework. We cover a broad range of mathematical optimization problems, including linear optimization (LP), quadratic constrained quadratic optimization (QCQP), general conic optimization including second order cone programming (SOCP) and semidefinite optimization (SDP), mixed integer optimization (MIP), network flows and 0 - 1 discrete optimization. Our approach allows the modeler to vary the level of conservatism of the robust solutions in terms of probabilistic bounds of constraint violations, while keeping the problem tractable. Specifically, for LP, MIP, SOCP, SDP, our approaches retain the same complexity class as the original model. The robust QCQP becomes a SOCP, which is computationally as attractive as the nominal problem. In network flows, we propose an algorithm for solving the robust minimum cost flow problem in polynomial number of nominal minimum cost flow problems in a modified network. For 0 - 1 discrete optimization problem with cost uncertainty, the robust counterpart of a polynomially solvable 0 - 1 discrete optimization problem remains polynomially solvable and the robust counterpart of an NP-hard o-approximable 0-1 discrete optimization problem, remains a-approximable. (cont.) Under an ellipsoidal uncertainty set, we show that the robust problem retains the complexity of the nominal problem when the data is uncorrelated and identically distributed. For uncorrelated, but not identically distributed data, we propose an approximation method that solves the robust problem within arbitrary accuracy. We also propose a Frank-Wolfe type algorithm for this case, which we prove converges to a locally optimal solution, and in computational experiments is remarkably effective. by Melvyn Sim. Ph.D. 2005-06-02T18:24:20Z 2005-06-02T18:24:20Z 2004 2004 Thesis http://hdl.handle.net/1721.1/17725 56462083 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 171 p. 4979081 bytes 4978895 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Sim, Melvyn Robust optimization |
| title | Robust optimization |
| title_full | Robust optimization |
| title_fullStr | Robust optimization |
| title_full_unstemmed | Robust optimization |
| title_short | Robust optimization |
| title_sort | robust optimization |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/17725 |
| work_keys_str_mv | AT simmelvyn robustoptimization |