IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i1p196-210.html
   My bibliography  Save this article

Robust Optimization for Models with Uncertain Second-Order Cone and Semidefinite Programming Constraints

Author

Listed:
  • Jianzhe Zhen

    (Automatic Control Laboratory, Eidgenössische Technische Hochschule (ETH) Zürich, 8092 Switzerland; Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands)

  • Frans J. C. T. de Ruiter

    (Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands; Consultants in Quantitative Methods (CQM), 5616 RM Eindhoven, Netherlands)

  • Ernst Roos

    (Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands)

  • Dick den Hertog

    (Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands; Faculty of Economics and Business, University of Amsterdam, 1102 CV Amsterdam, Netherlands)

Abstract

In this paper, we consider uncertain second-order cone (SOC) and semidefinite programming (SDP) constraints with polyhedral uncertainty, which are in general computationally intractable. We propose to reformulate an uncertain SOC or SDP constraint as a set of adjustable robust linear optimization constraints with an ellipsoidal or semidefinite representable uncertainty set, respectively. The resulting adjustable problem can then (approximately) be solved by using adjustable robust linear optimization techniques. For example, we show that if linear decision rules are used, then the final robust counterpart consists of SOC or SDP constraints, respectively, which have the same computational complexity as the nominal version of the original constraints. We propose an efficient method to obtain good lower bounds. Moreover, we extend our approach to other classes of robust optimization problems, such as nonlinear problems that contain wait-and-see variables, linear problems that contain bilinear uncertainty, and general conic constraints. Numerically, we apply our approach to reformulate the problem on finding the minimum volume circumscribing ellipsoid of a polytope and solve the resulting reformulation with linear and quadratic decision rules as well as Fourier-Motzkin elimination. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it with the state-of-the-art copositive approach. Moreover, we apply the proposed approach to a robust regression problem and a robust sensor network problem and use linear decision rules to solve the resulting adjustable robust linear optimization problems, which solve the problem to (near) optimality. Summary of Contribution: Computing robust solutions for nonlinear optimization problems with uncertain second-order cone and semidefinite programming constraints are of much interest in real-life applications, yet they are in general computationally intractable. This paper proposes a computationally tractable approximation for such problems. Extensive computational experiments on (i) computing the minimum volume circumscribing ellipsoid of a polytope, (ii) robust regressions, and (iii) robust sensor networks are conducted to demonstrate the effectiveness and efficiency of the proposed approach.

Suggested Citation

  • Jianzhe Zhen & Frans J. C. T. de Ruiter & Ernst Roos & Dick den Hertog, 2022. "Robust Optimization for Models with Uncertain Second-Order Cone and Semidefinite Programming Constraints," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 196-210, January.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:1:p:196-210
    DOI: 10.1287/ijoc.2020.1025
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.1025
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2020.1025?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
    ---><---

    References listed on IDEAS

    as
    1. Krzysztof Postek & Dick den Hertog, 2016. "Multistage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty Set," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 553-574, August.
    2. Dimitris Bertsimas & Iain Dunning, 2016. "Multistage Robust Mixed-Integer Optimization with Adaptive Partitions," Operations Research, INFORMS, vol. 64(4), pages 980-998, August.
    3. Jack Elzinga & Donald Hearn, 1974. "The minimum sphere covering a convex polyhedron," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 21(4), pages 715-718, December.
    4. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    5. Gorissen, Bram L. & den Hertog, Dick, 2013. "Robust counterparts of inequalities containing sums of maxima of linear functions," European Journal of Operational Research, Elsevier, vol. 227(1), pages 30-43.
    6. Zhen, Jianzhe, 2018. "Adjustable robust optimization : Theory, algorithm and applications," Other publications TiSEM d7f25656-92c5-45bf-b103-c, Tilburg University, School of Economics and Management.
    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. Jianzhe Zhen & Ahmadreza Marandi & Danique de Moor & Dick den Hertog & Lieven Vandenberghe, 2022. "Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2410-2427, September.

    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. Marcio Costa Santos & Michael Poss & Dritan Nace, 2018. "A perfect information lower bound for robust lot-sizing problems," Annals of Operations Research, Springer, vol. 271(2), pages 887-913, December.
    2. Jianzhe Zhen & Ahmadreza Marandi & Danique de Moor & Dick den Hertog & Lieven Vandenberghe, 2022. "Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2410-2427, September.
    3. Anirudh Subramanyam & Frank Mufalli & José M. Lí?nez-Aguirre & Jose M. Pinto & Chrysanthos E. Gounaris, 2021. "Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty," Operations Research, INFORMS, vol. 69(1), pages 30-60, January.
    4. Dimitris Bertsimas & Frans J. C. T. de Ruiter, 2016. "Duality in Two-Stage Adaptive Linear Optimization: Faster Computation and Stronger Bounds," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 500-511, August.
    5. Cohen, Izack & Postek, Krzysztof & Shtern, Shimrit, 2023. "An adaptive robust optimization model for parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 306(1), pages 83-104.
    6. 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).
    7. Bertsimas, Dimitris & Ng, Yeesian, 2019. "Robust and stochastic formulations for ambulance deployment and dispatch," European Journal of Operational Research, Elsevier, vol. 279(2), pages 557-571.
    8. 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.
    9. Marcio Costa Santos & Agostinho Agra & Michael Poss, 2020. "Robust inventory theory with perishable products," Annals of Operations Research, Springer, vol. 289(2), pages 473-494, June.
    10. Hossein Hashemi Doulabi & Patrick Jaillet & Gilles Pesant & Louis-Martin Rousseau, 2021. "Exploiting the Structure of Two-Stage Robust Optimization Models with Exponential Scenarios," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 143-162, January.
    11. Angelos Georghiou & Angelos Tsoukalas & Wolfram Wiesemann, 2020. "A Primal–Dual Lifting Scheme for Two-Stage Robust Optimization," Operations Research, INFORMS, vol. 68(2), pages 572-590, March.
    12. Cambier, Adrien & Chardy, Matthieu & Figueiredo, Rosa & Ouorou, Adam & Poss, Michael, 2022. "Optimizing subscriber migrations for a telecommunication operator in uncertain context," European Journal of Operational Research, Elsevier, vol. 298(1), pages 308-321.
    13. Hamed Mamani & Shima Nassiri & Michael R. Wagner, 2017. "Closed-Form Solutions for Robust Inventory Management," Management Science, INFORMS, vol. 63(5), pages 1625-1643, May.
    14. Metzker Soares, Paula & Thevenin, Simon & Adulyasak, Yossiri & Dolgui, Alexandre, 2024. "Adaptive robust optimization for lot-sizing under yield uncertainty," European Journal of Operational Research, Elsevier, vol. 313(2), pages 513-526.
    15. Walid Ben-Ameur & Adam Ouorou & Guanglei Wang & Mateusz Żotkiewicz, 2018. "Multipolar robust optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 395-434, December.
    16. Borumand, Ali & Marandi, Ahmadreza & Nookabadi, Ali S. & Atan, Zümbül, 2024. "An oracle-based algorithm for robust planning of production routing problems in closed-loop supply chains of beverage glass bottles," Omega, Elsevier, vol. 122(C).
    17. Feng, Wei & Feng, Yiping & Zhang, Qi, 2021. "Multistage robust mixed-integer optimization under endogenous uncertainty," European Journal of Operational Research, Elsevier, vol. 294(2), pages 460-475.
    18. Portoleau, Tom & Artigues, Christian & Guillaume, Romain, 2024. "Robust decision trees for the multi-mode project scheduling problem with a resource investment objective and uncertain activity duration," European Journal of Operational Research, Elsevier, vol. 312(2), pages 525-540.
    19. Arkajyoti Roy & Shaunak S. Dabadghao & Ahmadreza Marandi, 2024. "Value of intermediate imaging in adaptive robust radiotherapy planning to manage radioresistance," Annals of Operations Research, Springer, vol. 339(3), pages 1307-1328, August.
    20. Marin Bougeret & Jérémy Omer & Michael Poss, 2023. "Optimization Problems in Graphs with Locational Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 578-592, May.

    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:inm:orijoc:v:34:y:2022:i:1:p:196-210. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.