IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v320y2023i1d10.1007_s10479-022-04835-9.html
   My bibliography  Save this article

Online risk-averse submodular maximization

Author

Listed:
  • Tasuku Soma

    (Massachusetts Institute of Technology)

  • Yuichi Yoshida

    (National Institute of Informatics)

Abstract

We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given T i.i.d. samples from an underlying distribution arriving online, our algorithm produces a sequence of solutions that converges to a ( $$1-1/e$$ 1 - 1 / e )-approximate solution with a convergence rate of $$O(T^{-1/4})$$ O ( T - 1 / 4 ) for monotone continuous DR-submodular functions. Compared with previous offline algorithms, which require $$\Omega (T)$$ Ω ( T ) space, our online algorithm only requires $$O(\sqrt{T})$$ O ( T ) space. We extend our online algorithm to portfolio optimization for monotone submodular set functions under a matroid constraint. Experiments conducted on real-world datasets demonstrate that our algorithm can rapidly achieve CVaRs that are comparable to those obtained by existing offline algorithms.

Suggested Citation

  • Tasuku Soma & Yuichi Yoshida, 2023. "Online risk-averse submodular maximization," Annals of Operations Research, Springer, vol. 320(1), pages 393-414, January.
    • Handle: RePEc:spr:annopr:v:320:y:2023:i:1:d:10.1007_s10479-022-04835-9
    DOI: 10.1007/s10479-022-04835-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-022-04835-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-022-04835-9?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. Yau, Sheena & Kwon, Roy H. & Scott Rogers, J. & Wu, Desheng, 2011. "Financial and operational decisions in the electricity sector: Contract portfolio optimization with the conditional value-at-risk criterion," International Journal of Production Economics, Elsevier, vol. 134(1), pages 67-77, November.
    2. Renata Mansini & Włodzimierz Ogryczak & M. Speranza, 2007. "Conditional value at risk and related linear programming models for portfolio optimization," Annals of Operations Research, Springer, vol. 152(1), pages 227-256, July.
    Full references (including those not matched with items on IDEAS)

    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. Giovanni Bonaccolto & Massimiliano Caporin & Sandra Paterlini, 2018. "Asset allocation strategies based on penalized quantile regression," Computational Management Science, Springer, vol. 15(1), pages 1-32, January.
    2. Young Kim & Rosella Giacometti & Svetlozar Rachev & Frank Fabozzi & Domenico Mignacca, 2012. "Measuring financial risk and portfolio optimization with a non-Gaussian multivariate model," Annals of Operations Research, Springer, vol. 201(1), pages 325-343, December.
    3. Amy Givler Chapman & John E. Mitchell, 2018. "A fair division approach to humanitarian logistics inspired by conditional value-at-risk," Annals of Operations Research, Springer, vol. 262(1), pages 133-151, March.
    4. Francesco Cesarone & Andrea Scozzari & Fabio Tardella, 2015. "Linear vs. quadratic portfolio selection models with hard real-world constraints," Computational Management Science, Springer, vol. 12(3), pages 345-370, July.
    5. Soleimani, Hamed & Govindan, Kannan, 2014. "Reverse logistics network design and planning utilizing conditional value at risk," European Journal of Operational Research, Elsevier, vol. 237(2), pages 487-497.
    6. Alessandra Carleo & Francesco Cesarone & Andrea Gheno & Jacopo Maria Ricci, 2017. "Approximating exact expected utility via portfolio efficient frontiers," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 40(1), pages 115-143, November.
    7. Ethem Çanakoğlu & Esra Adıyeke, 2020. "Comparison of Electricity Spot Price Modelling and Risk Management Applications," Energies, MDPI, vol. 13(18), pages 1-22, September.
    8. Leili Javanmardi & Yuri Lawryshyn, 2016. "A new rank dependent utility approach to model risk averse preferences in portfolio optimization," Annals of Operations Research, Springer, vol. 237(1), pages 161-176, February.
    9. Sehgal, Ruchika & Sharma, Amita & Mansini, Renata, 2023. "Worst-case analysis of Omega-VaR ratio optimization model," Omega, Elsevier, vol. 114(C).
    10. Alejandro Balbas & Beatriz Balbas & Raquel Balbas, 2013. "Optimal Reinsurance: A Risk Sharing Approach," Risks, MDPI, vol. 1(2), pages 1-12, August.
    11. Johannes Holler, 2013. "Funding Strategies of Sovereign Debt Management: A Risk Focus," Monetary Policy & the Economy, Oesterreichische Nationalbank (Austrian Central Bank), issue 2, pages 51-74.
    12. Mohamed A. Ayadi & Hatem Ben-Ameur & Nabil Channouf & Quang Khoi Tran, 2019. "NORTA for portfolio credit risk," Annals of Operations Research, Springer, vol. 281(1), pages 99-119, October.
    13. Benita, Francisco & López-Ramos, Francisco & Nasini, Stefano, 2019. "A bi-level programming approach for global investment strategies with financial intermediation," European Journal of Operational Research, Elsevier, vol. 274(1), pages 375-390.
    14. Liu, Yong-Jun & Yang, Guo-Sen & Zhang, Wei-Guo, 2024. "A novel regret-rejoice cross-efficiency approach for energy stock portfolio optimization," Omega, Elsevier, vol. 126(C).
    15. P. Kumar & Jyotirmayee Behera & A. K. Bhurjee, 2022. "Solving mean-VaR portfolio selection model with interval-typed random parameter using interval analysis," OPSEARCH, Springer;Operational Research Society of India, vol. 59(1), pages 41-77, March.
    16. Lwin, Khin T. & Qu, Rong & MacCarthy, Bart L., 2017. "Mean-VaR portfolio optimization: A nonparametric approach," European Journal of Operational Research, Elsevier, vol. 260(2), pages 751-766.
    17. Fabio Vitor & Todd Easton, 2018. "The double pivot simplex method," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 87(1), pages 109-137, February.
    18. Alejandro Balbás & Iván Blanco & José Garrido, 2014. "Measuring Risk When Expected Losses Are Unbounded," Risks, MDPI, vol. 2(4), pages 1-14, September.
    19. Wei, Yi-Ming & Mi, Zhi-Fu & Huang, Zhimin, 2015. "Climate policy modeling: An online SCI-E and SSCI based literature review," Omega, Elsevier, vol. 57(PA), pages 70-84.
    20. Nasini, Stefano & Labbé, Martine & Brotcorne, Luce, 2022. "Multi-market portfolio optimization with conditional value at risk," European Journal of Operational Research, Elsevier, vol. 300(1), pages 350-365.

    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:320:y:2023:i:1:d:10.1007_s10479-022-04835-9. 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.