IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v77y2013i3p323-343.html
   My bibliography  Save this article

On the approximability of adjustable robust convex optimization under uncertainty

Author

Listed:
  • Dimitris Bertsimas
  • Vineet Goyal

Abstract

In this paper, we consider adjustable robust versions of convex optimization problems with uncertain constraints and objectives and show that under fairly general assumptions, a static robust solution provides a good approximation for these adjustable robust problems. An adjustable robust optimization problem is usually intractable since it requires to compute a solution for all possible realizations of uncertain parameters, while an optimal static solution can be computed efficiently in most cases if the corresponding deterministic problem is tractable. The performance of the optimal static robust solution is related to a fundamental geometric property, namely, the symmetry of the uncertainty set. Our work allows for the constraint and objective function coefficients to be uncertain and for the constraints and objective functions to be convex, thereby providing significant extensions of the results in Bertsimas and Goyal (Math Oper Res 35:284–305, 2010 ) and Bertsimas et al. (Math Oper Res 36: 24–54, 2011b ) where only linear objective and linear constraints were considered. The models in this paper encompass a wide variety of problems in revenue management, resource allocation under uncertainty, scheduling problems with uncertain processing times, semidefinite optimization among many others. To the best of our knowledge, these are the first approximation bounds for adjustable robust convex optimization problems in such generality. Copyright Springer-Verlag 2013

Suggested Citation

  • Dimitris Bertsimas & Vineet Goyal, 2013. "On the approximability of adjustable robust convex optimization under uncertainty," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 77(3), pages 323-343, June.
  • Handle: RePEc:spr:mathme:v:77:y:2013:i:3:p:323-343
    DOI: 10.1007/s00186-012-0405-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00186-012-0405-6
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s00186-012-0405-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    2. George B. Dantzig, 1955. "Linear Programming under Uncertainty," Management Science, INFORMS, vol. 1(3-4), pages 197-206, 04-07.
    3. Dimitris Bertsimas & Vineet Goyal, 2010. "On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 284-305, May.
    4. A. Ben-Tal & A. Nemirovski, 1998. "Robust Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 769-805, November.
    5. D. Goldfarb & G. Iyengar, 2003. "Robust Portfolio Selection Problems," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 1-38, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Marandi, Ahmadreza & den Hertog, Dick, 2015. "When are Static and Adjustable Robust Optimization with Constraint-Wise Uncertainty Equivalent?," Discussion Paper 2015-045, Tilburg University, Center for Economic Research.
    2. Yanıkoğlu, İhsan & Gorissen, Bram L. & den Hertog, Dick, 2019. "A survey of adjustable robust optimization," European Journal of Operational Research, Elsevier, vol. 277(3), pages 799-813.
    3. Christoph Buchheim & Jannis Kurtz, 2018. "Robust combinatorial optimization under convex and discrete cost uncertainty," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(3), pages 211-238, September.
    4. Ali Haddad-Sisakht & Sarah M. Ryan, 2018. "Conditions under which adjustability lowers the cost of a robust linear program," Annals of Operations Research, Springer, vol. 269(1), pages 185-204, October.
    5. Ning Zhang & Chang Fang, 2020. "Saddle point approximation approaches for two-stage robust optimization problems," Journal of Global Optimization, Springer, vol. 78(4), pages 651-670, December.
    6. Nicolas Kämmerling & Jannis Kurtz, 2020. "Oracle-based algorithms for binary two-stage robust optimization," Computational Optimization and Applications, Springer, vol. 77(2), pages 539-569, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dimitris Bertsimas & Vineet Goyal & Xu Andy Sun, 2011. "A Geometric Characterization of the Power of Finite Adaptability in Multistage Stochastic and Adaptive Optimization," Mathematics of Operations Research, INFORMS, vol. 36(1), pages 24-54, February.
    2. Marla, Lavanya & Rikun, Alexander & Stauffer, Gautier & Pratsini, Eleni, 2020. "Robust modeling and planning: Insights from three industrial applications," Operations Research Perspectives, Elsevier, vol. 7(C).
    3. Taozeng Zhu & Jingui Xie & Melvyn Sim, 2022. "Joint Estimation and Robustness Optimization," Management Science, INFORMS, vol. 68(3), pages 1659-1677, March.
    4. Hsien-Chung Wu, 2019. "Numerical Method for Solving the Robust Continuous-Time Linear Programming Problems," Mathematics, MDPI, vol. 7(5), pages 1-50, May.
    5. L. Jeff Hong & Zhiyuan Huang & Henry Lam, 2021. "Learning-Based Robust Optimization: Procedures and Statistical Guarantees," Management Science, INFORMS, vol. 67(6), pages 3447-3467, June.
    6. Guanglei Wang & Hassan Hijazi, 2018. "Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches," Computational Optimization and Applications, Springer, vol. 71(2), pages 553-608, November.
    7. Aharon Ben-Tal & Dimitris Bertsimas & David B. Brown, 2010. "A Soft Robust Model for Optimization Under Ambiguity," Operations Research, INFORMS, vol. 58(4-part-2), pages 1220-1234, August.
    8. Steffen Rebennack, 2022. "Data-driven stochastic optimization for distributional ambiguity with integrated confidence region," Journal of Global Optimization, Springer, vol. 84(2), pages 255-293, October.
    9. Gianfranco Guastaroba & Gautam Mitra & M Grazia Speranza, 2011. "Investigating the effectiveness of robust portfolio optimization techniques," Journal of Asset Management, Palgrave Macmillan, vol. 12(4), pages 260-280, September.
    10. Soleimanian, Azam & Salmani Jajaei, Ghasemali, 2013. "Robust nonlinear optimization with conic representable uncertainty set," European Journal of Operational Research, Elsevier, vol. 228(2), pages 337-344.
    11. Andrew J. Keith & Darryl K. Ahner, 2021. "A survey of decision making and optimization under uncertainty," Annals of Operations Research, Springer, vol. 300(2), pages 319-353, May.
    12. Sandra Cruz Caçador & Pedro Manuel Cortesão Godinho & Joana Maria Pina Cabral Matos Dias, 2022. "A minimax regret portfolio model based on the investor’s utility loss," Operational Research, Springer, vol. 22(1), pages 449-484, March.
    13. Somayeh Moazeni & Thomas Coleman & Yuying Li, 2013. "Regularized robust optimization: the optimal portfolio execution case," Computational Optimization and Applications, Springer, vol. 55(2), pages 341-377, June.
    14. Shaghayegh Mokarami & S. Hashemi, 2015. "Constrained shortest path with uncertain transit times," Journal of Global Optimization, Springer, vol. 63(1), pages 149-163, September.
    15. Bakker, Hannah & Dunke, Fabian & Nickel, Stefan, 2020. "A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice," Omega, Elsevier, vol. 96(C).
    16. Raphael Hauser & Vijay Krishnamurthy & Reha Tutuncu, 2013. "Relative Robust Portfolio Optimization," Papers 1305.0144, arXiv.org, revised May 2013.
    17. de Oliveira, Glauber Cardoso & Bertone, Edoardo & Stewart, Rodney A., 2022. "Optimisation modelling tools and solving techniques for integrated precinct-scale energy–water system planning," Applied Energy, Elsevier, vol. 318(C).
    18. Gülpınar, Nalan & Pachamanova, Dessislava & Çanakoğlu, Ethem, 2013. "Robust strategies for facility location under uncertainty," European Journal of Operational Research, Elsevier, vol. 225(1), pages 21-35.
    19. Gregory, Christine & Darby-Dowman, Ken & Mitra, Gautam, 2011. "Robust optimization and portfolio selection: The cost of robustness," European Journal of Operational Research, Elsevier, vol. 212(2), pages 417-428, July.
    20. Jang Ho Kim & Woo Chang Kim & Frank J. Fabozzi, 2014. "Recent Developments in Robust Portfolios with a Worst-Case Approach," Journal of Optimization Theory and Applications, Springer, vol. 161(1), pages 103-121, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:mathme:v:77:y:2013:i:3:p:323-343. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.