Optimality of Affine Policies in Multi-stage Robust Optimization
In this paper, we prove the optimality of disturbance-affine control policies in the context of one-dimensional, constrained, multistage robust optimization. Our results cover the finite-horizon case, with minimax (worst-case) objective, and convex state costs plus linear control costs. We develop a...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute for Operations Research and the Management Sciences
2011
|
| Online Access: | http://hdl.handle.net/1721.1/65896 https://orcid.org/0000-0002-1985-1003 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1826216376913625088 |
|---|---|
| author | Bertsimas, Dimitris J. Iancu, Dan Andrei Parillo, Pablo A. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bertsimas, Dimitris J. Iancu, Dan Andrei Parillo, Pablo A. |
| author_sort | Bertsimas, Dimitris J. |
| collection | MIT |
| description | In this paper, we prove the optimality of disturbance-affine control policies in the context of one-dimensional, constrained, multistage robust optimization. Our results cover the finite-horizon case, with minimax (worst-case) objective, and convex state costs plus linear control costs. We develop a new proof methodology, which explores the relationship between the geometrical properties of the feasible set of solutions and the structure of the objective function. Apart from providing an elegant and conceptually simple proof technique, the approach also entails very fast algorithms for the case of piecewise-affine state costs, which we explore in connection with a classical inventory management application. |
| first_indexed | 2024-09-23T16:46:42Z |
| format | Article |
| id | mit-1721.1/65896 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:46:42Z |
| publishDate | 2011 |
| publisher | Institute for Operations Research and the Management Sciences |
| record_format | dspace |
| spelling | mit-1721.1/658962022-09-29T21:25:39Z Optimality of Affine Policies in Multi-stage Robust Optimization Bertsimas, Dimitris J. Iancu, Dan Andrei Parillo, Pablo A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Parrilo, Pablo A. Parrilo, Pablo A. Bertsimas, Dimitris J. Iancu, Dan Andrei In this paper, we prove the optimality of disturbance-affine control policies in the context of one-dimensional, constrained, multistage robust optimization. Our results cover the finite-horizon case, with minimax (worst-case) objective, and convex state costs plus linear control costs. We develop a new proof methodology, which explores the relationship between the geometrical properties of the feasible set of solutions and the structure of the objective function. Apart from providing an elegant and conceptually simple proof technique, the approach also entails very fast algorithms for the case of piecewise-affine state costs, which we explore in connection with a classical inventory management application. 2011-09-21T14:56:08Z 2011-09-21T14:56:08Z 2010-05 2010-02 Article http://purl.org/eprint/type/JournalArticle 0364-765X 1526-5471 http://hdl.handle.net/1721.1/65896 Bertsimas, D., D. A. Iancu, and P. A. Parrilo. “Optimality of Affine Policies in Multistage Robust Optimization.” Mathematics of Operations Research 35 (2010): 363-394. https://orcid.org/0000-0002-1985-1003 https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1287/moor.1100.0444 Mathematics of Operations Research Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute for Operations Research and the Management Sciences Prof. Parrilo |
| spellingShingle | Bertsimas, Dimitris J. Iancu, Dan Andrei Parillo, Pablo A. Optimality of Affine Policies in Multi-stage Robust Optimization |
| title | Optimality of Affine Policies in Multi-stage Robust Optimization |
| title_full | Optimality of Affine Policies in Multi-stage Robust Optimization |
| title_fullStr | Optimality of Affine Policies in Multi-stage Robust Optimization |
| title_full_unstemmed | Optimality of Affine Policies in Multi-stage Robust Optimization |
| title_short | Optimality of Affine Policies in Multi-stage Robust Optimization |
| title_sort | optimality of affine policies in multi stage robust optimization |
| url | http://hdl.handle.net/1721.1/65896 https://orcid.org/0000-0002-1985-1003 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT bertsimasdimitrisj optimalityofaffinepoliciesinmultistagerobustoptimization AT iancudanandrei optimalityofaffinepoliciesinmultistagerobustoptimization AT parillopabloa optimalityofaffinepoliciesinmultistagerobustoptimization |