IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v229y2015i1p103-12010.1007-s10479-015-1786-8.html
   My bibliography  Save this article

A general solution for robust linear programs with distortion risk constraints

Author

Listed:
  • Pavel Bazovkin
  • Karl Mosler

Abstract

Linear optimization problems are investigated that have random parameters in their $$m\ge 1$$ m ≥ 1 constraints. In constructing a robust solution $${\mathbf {x}}\in \mathbb {R}^d$$ x ∈ R d , we control the risk arising from violations of the constraints. This risk is measured by set-valued risk measures, which extend the usual univariate coherent distortion (=spectral) risk measures to the multivariate case. To obtain a robust solution in $$d$$ d variables, the linear goal function is optimized under the restrictions holding uniformly for all parameters in a $$d$$ d -variate uncertainty set. This set is built from uncertainty sets of the single constraints, each of which is a weighted-mean trimmed region in $$\mathbb {R}^d$$ R d and can be efficiently calculated. Furthermore, a possible substitution of violations between different constraints is investigated by means of the admissable set of the multivariate risk measure. In the case of no substitution, we give an exact geometric algorithm, which possesses a worst-case polynomial complexity. We extend the algorithm to the general substitutability case, that is, to robust polyhedral optimization. The consistency of the approach is shown for generally distributed parameters. Finally, an application of the model to supervised machine learning is discussed. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • Pavel Bazovkin & Karl Mosler, 2015. "A general solution for robust linear programs with distortion risk constraints," Annals of Operations Research, Springer, vol. 229(1), pages 103-120, June.
  • Handle: RePEc:spr:annopr:v:229:y:2015:i:1:p:103-120:10.1007/s10479-015-1786-8
    DOI: 10.1007/s10479-015-1786-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-015-1786-8
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s10479-015-1786-8?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. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    2. Karthik Natarajan & Dessislava Pachamanova & Melvyn Sim, 2009. "Constructing Risk Measures from Uncertainty Sets," Operations Research, INFORMS, vol. 57(5), pages 1129-1141, October.
    3. Wenqing Chen & Melvyn Sim, 2009. "Goal-Driven Optimization," Operations Research, INFORMS, vol. 57(2), pages 342-357, April.
    4. Aharon Ben-Tal & Dick den Hertog & Anja De Waegenaere & Bertrand Melenberg & Gijs Rennen, 2013. "Robust Solutions of Optimization Problems Affected by Uncertain Probabilities," Management Science, INFORMS, vol. 59(2), pages 341-357, April.
    5. Dyckerhoff, Rainer & Mosler, Karl, 2011. "Weighted-mean trimming of multivariate data," Journal of Multivariate Analysis, Elsevier, vol. 102(3), pages 405-421, March.
    6. Bazovkin, Pavel & Mosler, Karl, 2012. "An Exact Algorithm for Weighted-Mean Trimmed Regions in Any Dimension," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 47(i13).
    7. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    8. Dimitris Bertsimas & David B. Brown, 2009. "Constructing Uncertainty Sets for Robust Linear Optimization," Operations Research, INFORMS, vol. 57(6), pages 1483-1495, December.
    9. Bazovkin, Pavel, 2014. "Geometrical framework for robust portfolio optimization," Discussion Papers in Econometrics and Statistics 01/14, University of Cologne, Institute of Econometrics and Statistics.
    10. Frank Fabozzi & Dashan Huang & Guofu Zhou, 2010. "Robust portfolios: contributions from operations research and finance," Annals of Operations Research, Springer, vol. 176(1), pages 191-220, April.
    11. Ignacio Cascos & Ilya Molchanov, 2007. "Multivariate risks and depth-trimmed regions," Finance and Stochastics, Springer, vol. 11(3), pages 373-397, July.
    12. Erick Delage & Yinyu Ye, 2010. "Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems," Operations Research, INFORMS, vol. 58(3), pages 595-612, June.
    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. Pavlo Mozharovskyi & Julie Josse & François Husson, 2017. "Nonparametric imputation by data depth," Working Papers 2017-72, Center for Research in Economics and Statistics.
    2. 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.
    3. Bazovkin, Pavel, 2014. "Geometrical framework for robust portfolio optimization," Discussion Papers in Econometrics and Statistics 01/14, University of Cologne, Institute of Econometrics and Statistics.

    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. Wolfram Wiesemann & Daniel Kuhn & Melvyn Sim, 2014. "Distributionally Robust Convex Optimization," Operations Research, INFORMS, vol. 62(6), pages 1358-1376, December.
    2. Bazovkin, Pavel & Mosler, Karl, 2011. "Stochastic linear programming with a distortion risk constraint," Discussion Papers in Econometrics and Statistics 6/11, University of Cologne, Institute of Econometrics and Statistics.
    3. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    4. Postek, K.S. & den Hertog, D. & Melenberg, B., 2015. "Computationally Tractable Counterparts of Distributionally Robust Constraints on Risk Measures (revision of CentER DP 2014-031)," Discussion Paper 2015-047, Tilburg University, Center for Economic Research.
    5. 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.
    6. Mengshi Lu & Zuo‐Jun Max Shen, 2021. "A Review of Robust Operations Management under Model Uncertainty," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1927-1943, June.
    7. Postek, K.S. & den Hertog, D. & Melenberg, B., 2015. "Computationally Tractable Counterparts of Distributionally Robust Constraints on Risk Measures (revision of CentER DP 2014-031)," Other publications TiSEM eeb9c898-6943-4199-b747-3, Tilburg University, School of Economics and Management.
    8. Ang, James & Meng, Fanwen & Sun, Jie, 2014. "Two-stage stochastic linear programs with incomplete information on uncertainty," European Journal of Operational Research, Elsevier, vol. 233(1), pages 16-22.
    9. Fernandes, Betina & Street, Alexandre & Valladão, Davi & Fernandes, Cristiano, 2016. "An adaptive robust portfolio optimization model with loss constraints based on data-driven polyhedral uncertainty sets," European Journal of Operational Research, Elsevier, vol. 255(3), pages 961-970.
    10. Zhi Chen & Melvyn Sim & Huan Xu, 2019. "Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," Operations Research, INFORMS, vol. 67(5), pages 1328-1344, September.
    11. Pengyu Qian & Zizhuo Wang & Zaiwen Wen, 2015. "A Composite Risk Measure Framework for Decision Making under Uncertainty," Papers 1501.01126, arXiv.org.
    12. Chen, Qingxin & Ma, Shoufeng & Li, Hongming & Zhu, Ning & He, Qiao-Chu, 2024. "Optimizing bike rebalancing strategies in free-floating bike-sharing systems: An enhanced distributionally robust approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 184(C).
    13. 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).
    14. Liu, Kanglin & Li, Qiaofeng & Zhang, Zhi-Hai, 2019. "Distributionally robust optimization of an emergency medical service station location and sizing problem with joint chance constraints," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 79-101.
    15. Alireza Ghahtarani & Ahmed Saif & Alireza Ghasemi, 2022. "Robust portfolio selection problems: a comprehensive review," Operational Research, Springer, vol. 22(4), pages 3203-3264, September.
    16. Alireza Ghahtarani & Ahmed Saif & Alireza Ghasemi, 2021. "Robust Portfolio Selection Problems: A Comprehensive Review," Papers 2103.13806, arXiv.org, revised Jan 2022.
    17. Berk Wheelock, Lauren & Pachamanova, Dessislava A., 2022. "Acceptable set topic modeling," European Journal of Operational Research, Elsevier, vol. 299(2), pages 653-673.
    18. Shunichi Ohmori, 2021. "A Predictive Prescription Using Minimum Volume k -Nearest Neighbor Enclosing Ellipsoid and Robust Optimization," Mathematics, MDPI, vol. 9(2), pages 1-16, January.
    19. Benati, S. & Conde, E., 2022. "A relative robust approach on expected returns with bounded CVaR for portfolio selection," European Journal of Operational Research, Elsevier, vol. 296(1), pages 332-352.
    20. 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.

    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:annopr:v:229:y:2015:i:1:p:103-120:10.1007/s10479-015-1786-8. 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.