Generalized decision rule approximations for stochastic programming via liftings
Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Rannpháirtithe: | |
| Formáid: | Alt |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
Springer Berlin Heidelberg
2016
|
| Rochtain ar líne: | http://hdl.handle.net/1721.1/103397 |
| _version_ | 1826200159035326464 |
|---|---|
| author | Georghiou, Angelos Wiesemann, Wolfram Kuhn, Daniel |
| author2 | Massachusetts Institute of Technology. Process Systems Engineering Laboratory |
| author_facet | Massachusetts Institute of Technology. Process Systems Engineering Laboratory Georghiou, Angelos Wiesemann, Wolfram Kuhn, Daniel |
| author_sort | Georghiou, Angelos |
| collection | MIT |
| description | Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the optimal value of a stochastic program. Unfortunately, linear decision rules often provide crude approximations that result in loose bounds. To address this problem, we propose a lifting technique that maps a given stochastic program to an equivalent problem on a higher-dimensional probability space. We prove that solving the lifted problem in primal and dual linear decision rules provides tighter bounds than those obtained from applying linear decision rules to the original problem. We also show that there is a one-to-one correspondence between linear decision rules in the lifted problem and families of nonlinear decision rules in the original problem. Finally, we identify structured liftings that give rise to highly flexible piecewise linear and nonlinear decision rules, and we assess their performance in the context of a dynamic production planning problem. |
| first_indexed | 2024-09-23T11:32:04Z |
| format | Article |
| id | mit-1721.1/103397 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:32:04Z |
| publishDate | 2016 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1033972022-10-01T04:16:59Z Generalized decision rule approximations for stochastic programming via liftings Georghiou, Angelos Wiesemann, Wolfram Kuhn, Daniel Massachusetts Institute of Technology. Process Systems Engineering Laboratory Georghiou, Angelos Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the optimal value of a stochastic program. Unfortunately, linear decision rules often provide crude approximations that result in loose bounds. To address this problem, we propose a lifting technique that maps a given stochastic program to an equivalent problem on a higher-dimensional probability space. We prove that solving the lifted problem in primal and dual linear decision rules provides tighter bounds than those obtained from applying linear decision rules to the original problem. We also show that there is a one-to-one correspondence between linear decision rules in the lifted problem and families of nonlinear decision rules in the original problem. Finally, we identify structured liftings that give rise to highly flexible piecewise linear and nonlinear decision rules, and we assess their performance in the context of a dynamic production planning problem. Engineering and Physical Sciences Research Council (grant EP/H0204554/1) 2016-06-30T19:59:05Z 2016-06-30T19:59:05Z 2014-05 2010-08 2016-05-23T12:11:09Z Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/103397 Georghiou, Angelos, Wolfram Wiesemann, and Daniel Kuhn. “Generalized Decision Rule Approximations for Stochastic Programming via Liftings.” Math. Program. 152, no. 1–2 (May 25, 2014): 301–338. en http://dx.doi.org/10.1007/s10107-014-0789-6 Mathematical Programming Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Georghiou, Angelos Wiesemann, Wolfram Kuhn, Daniel Generalized decision rule approximations for stochastic programming via liftings |
| title | Generalized decision rule approximations for stochastic programming via liftings |
| title_full | Generalized decision rule approximations for stochastic programming via liftings |
| title_fullStr | Generalized decision rule approximations for stochastic programming via liftings |
| title_full_unstemmed | Generalized decision rule approximations for stochastic programming via liftings |
| title_short | Generalized decision rule approximations for stochastic programming via liftings |
| title_sort | generalized decision rule approximations for stochastic programming via liftings |
| url | http://hdl.handle.net/1721.1/103397 |
| work_keys_str_mv | AT georghiouangelos generalizeddecisionruleapproximationsforstochasticprogrammingvialiftings AT wiesemannwolfram generalizeddecisionruleapproximationsforstochasticprogrammingvialiftings AT kuhndaniel generalizeddecisionruleapproximationsforstochasticprogrammingvialiftings |