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. 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.
    2. 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.
    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. Boguk Kim & Chulwoo Han & Frank Chongwoo Park, 2014. "Optimising Credit Portfolio Using a Quadratic Nonlinear Projection Method," Papers 1411.2525, arXiv.org, revised Jul 2016.
    2. Malavasi, Matteo & Ortobelli Lozza, Sergio & Trück, Stefan, 2021. "Second order of stochastic dominance efficiency vs mean variance efficiency," European Journal of Operational Research, Elsevier, vol. 290(3), pages 1192-1206.
    3. 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.
    4. Somayeh Moazeni & Thomas F. Coleman & Yuying Li, 2016. "Smoothing and parametric rules for stochastic mean-CVaR optimal execution strategy," Annals of Operations Research, Springer, vol. 237(1), pages 99-120, February.
    5. Balbás, Alejandro & Balbás, Beatriz & Heras, Antonio, 2011. "Stable solutions for optimal reinsurance problems involving risk measures," European Journal of Operational Research, Elsevier, vol. 214(3), pages 796-804, November.
    6. Lin, Edward M.H. & Sun, Edward W. & Yu, Min-Teh, 2020. "Behavioral data-driven analysis with Bayesian method for risk management of financial services," International Journal of Production Economics, Elsevier, vol. 228(C).
    7. Murat Köksalan & Ceren Tuncer Şakar, 2016. "An interactive approach to stochastic programming-based portfolio optimization," Annals of Operations Research, Springer, vol. 245(1), pages 47-66, October.
    8. Branda, Martin, 2013. "Diversification-consistent data envelopment analysis with general deviation measures," European Journal of Operational Research, Elsevier, vol. 226(3), pages 626-635.
    9. Justo Puerto & Moises Rodr'iguez-Madrena & Andrea Scozzari, 2019. "Location and portfolio selection problems: A unified framework," Papers 1907.07101, arXiv.org.
    10. Jinping Zhang & Keming Zhang, 2022. "Portfolio selection models based on interval-valued conditional value at risk (ICVaR) and empirical analysis," Papers 2201.02987, arXiv.org, revised Jul 2022.
    11. 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.
    12. 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.
    13. 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.
    14. Balibek, Emre & Köksalan, Murat, 2010. "A multi-objective multi-period stochastic programming model for public debt management," European Journal of Operational Research, Elsevier, vol. 205(1), pages 205-217, August.
    15. Rudloff, Birgit & Street, Alexandre & Valladão, Davi M., 2014. "Time consistency and risk averse dynamic decision models: Definition, interpretation and practical consequences," European Journal of Operational Research, Elsevier, vol. 234(3), pages 743-750.
    16. 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.
    17. Mohsen Zamani & Mahdi Abolghasemi & Seyed Mohammad Seyed Hosseini & Mir Saman Pishvaee, 2019. "Considering pricing and uncertainty in designing a reverse logistics network," Papers 1909.11633, arXiv.org.
    18. Shangmei Zhao & Qing Lu & Liyan Han & Yong Liu & Fei Hu, 2015. "A mean-CVaR-skewness portfolio optimization model based on asymmetric Laplace distribution," Annals of Operations Research, Springer, vol. 226(1), pages 727-739, March.
    19. 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.
    20. 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.

    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.