IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v86y2023i3d10.1007_s10898-022-01266-5.html
   My bibliography  Save this article

Distributed primal outer approximation algorithm for sparse convex programming with separable structures

Author

Listed:
  • Alireza Olama

    (Federal University of Santa Catarina)

  • Eduardo Camponogara

    (Federal University of Santa Catarina)

  • Paulo R. C. Mendes

    (Fraunhofer Institute for Industrial Mathematics)

Abstract

This paper presents the distributed primal outer approximation (DiPOA) algorithm for solving sparse convex programming (SCP) problems with separable structures, efficiently, and in a decentralized manner. The DiPOA algorithm development consists of embedding the recently proposed relaxed hybrid alternating direction method of multipliers (RH-ADMM) algorithm into the outer approximation (OA) algorithm. We also propose two main improvements to control the quality and the number of cutting planes that approximate nonlinear functions. In particular, the RH-ADMM algorithm acts as a distributed numerical engine inside the DiPOA algorithm. DiPOA takes advantage of the multi-core architecture of modern processors to speed up optimization algorithms. The proposed distributed algorithm makes practical the solution of SCP in learning and control problems from the application side. This paper concludes with a performance analysis of DiPOA for the distributed sparse logistic regression and quadratically constrained optimization problems. Finally, the paper concludes with a numerical comparison with state-of-the-art optimization solvers.

Suggested Citation

  • Alireza Olama & Eduardo Camponogara & Paulo R. C. Mendes, 2023. "Distributed primal outer approximation algorithm for sparse convex programming with separable structures," Journal of Global Optimization, Springer, vol. 86(3), pages 637-670, July.
    • Handle: RePEc:spr:jglopt:v:86:y:2023:i:3:d:10.1007_s10898-022-01266-5
    DOI: 10.1007/s10898-022-01266-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-022-01266-5
    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/s10898-022-01266-5?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 & Nishanth Mundru, 2021. "Sparse Convex Regression," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 262-279, January.
    2. Dimitris Bertsimas & Romy Shioda, 2009. "Algorithm for cardinality-constrained quadratic optimization," Computational Optimization and Applications, Springer, vol. 43(1), pages 1-22, May.
    3. Jan Kronqvist & Andreas Lundell & Tapio Westerlund, 2018. "Reformulations for utilizing separability when solving convex MINLP problems," Journal of Global Optimization, Springer, vol. 71(3), pages 571-592, July.
    4. Alexander Murray & Timm Faulwasser & Veit Hagenmeyer & Mario E. Villanueva & Boris Houska, 2021. "Partially distributed outer approximation," Journal of Global Optimization, Springer, vol. 80(3), pages 523-550, July.
    5. Pavlo Muts & Ivo Nowak & Eligius M. T. Hendrix, 2020. "The decomposition-based outer approximation algorithm for convex mixed-integer nonlinear programming," Journal of Global Optimization, Springer, vol. 77(1), pages 75-96, May.
    6. Sant'Anna, Leonardo Riegel & de Oliveira, Alan Delgado & Filomena, Tiago Pascoal & Caldeira, João Frois, 2020. "Solving the index tracking problem based on a convex reformulation for cointegration," Finance Research Letters, Elsevier, vol. 37(C).
    7. Aytug, Haldun, 2015. "Feature selection for support vector machines using Generalized Benders Decomposition," European Journal of Operational Research, Elsevier, vol. 244(1), pages 210-218.
    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. Andreas Lundell & Jan Kronqvist, 2022. "Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT," Journal of Global Optimization, Springer, vol. 82(4), pages 863-896, April.
    2. Alexander Murray & Timm Faulwasser & Veit Hagenmeyer & Mario E. Villanueva & Boris Houska, 2021. "Partially distributed outer approximation," Journal of Global Optimization, Springer, vol. 80(3), pages 523-550, July.
    3. Andreas Lundell & Jan Kronqvist & Tapio Westerlund, 2022. "The supporting hyperplane optimization toolkit for convex MINLP," Journal of Global Optimization, Springer, vol. 84(1), pages 1-41, September.
    4. Lili Pan & Ziyan Luo & Naihua Xiu, 2017. "Restricted Robinson Constraint Qualification and Optimality for Cardinality-Constrained Cone Programming," Journal of Optimization Theory and Applications, Springer, vol. 175(1), pages 104-118, October.
    5. 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.
    6. Ricardo M. Lima & Ignacio E. Grossmann, 2017. "On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study," Computational Optimization and Applications, Springer, vol. 66(1), pages 1-37, January.
    7. Andrés Gómez & Oleg A. Prokopyev, 2021. "A Mixed-Integer Fractional Optimization Approach to Best Subset Selection," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 551-565, May.
    8. Dimitris Bertsimas & Ryan Cory-Wright, 2022. "A Scalable Algorithm for Sparse Portfolio Selection," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1489-1511, May.
    9. Zhi-Long Dong & Fengmin Xu & Yu-Hong Dai, 2020. "Fast algorithms for sparse portfolio selection considering industries and investment styles," Journal of Global Optimization, Springer, vol. 78(4), pages 763-789, December.
    10. A. Garcia-Bernabeu & J. V. Salcedo & A. Hilario & D. Pla-Santamaria & Juan M. Herrero, 2019. "Computing the Mean-Variance-Sustainability Nondominated Surface by ev-MOGA," Complexity, Hindawi, vol. 2019, pages 1-12, December.
    11. David E. Bernal & Zedong Peng & Jan Kronqvist & Ignacio E. Grossmann, 2022. "Alternative regularizations for Outer-Approximation algorithms for convex MINLP," Journal of Global Optimization, Springer, vol. 84(4), pages 807-842, December.
    12. Nakagawa, Kei & Suimon, Yoshiyuki, 2022. "Inflation rate tracking portfolio optimization method: Evidence from Japan," Finance Research Letters, Elsevier, vol. 49(C).
    13. Ricardo M. Lima & Antonio J. Conejo & Loïc Giraldi & Olivier Le Maître & Ibrahim Hoteit & Omar M. Knio, 2022. "Risk-Averse Stochastic Programming vs. Adaptive Robust Optimization: A Virtual Power Plant Application," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1795-1818, May.
    14. Leonardo Di Gangi & M. Lapucci & F. Schoen & A. Sortino, 2019. "An efficient optimization approach for best subset selection in linear regression, with application to model selection and fitting in autoregressive time-series," Computational Optimization and Applications, Springer, vol. 74(3), pages 919-948, December.
    15. Young Woong Park, 2021. "Optimization for L 1 -Norm Error Fitting via Data Aggregation," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 120-142, January.
    16. Martin Branda & Max Bucher & Michal Červinka & Alexandra Schwartz, 2018. "Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization," Computational Optimization and Applications, Springer, vol. 70(2), pages 503-530, June.
    17. Ozcan, Erhan C. & Görgülü, Berk & Baydogan, Mustafa G., 2024. "Column generation-based prototype learning for optimizing area under the receiver operating characteristic curve," European Journal of Operational Research, Elsevier, vol. 314(1), pages 297-307.
    18. Nasim Dehghan Hardoroudi & Abolfazl Keshvari & Markku Kallio & Pekka Korhonen, 2017. "Solving cardinality constrained mean-variance portfolio problems via MILP," Annals of Operations Research, Springer, vol. 254(1), pages 47-59, July.
    19. E. Grizickas Sapkute & M. A. Sánchez-Granero & M. N. López García & J. E. Trinidad Segovia, 2022. "The impact of regulation-based constraints on portfolio selection: The Spanish case," Palgrave Communications, Palgrave Macmillan, vol. 9(1), pages 1-14, December.
    20. Gnägi, M. & Strub, O., 2020. "Tracking and outperforming large stock-market indices," Omega, Elsevier, vol. 90(C).

    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:jglopt:v:86:y:2023:i:3:d:10.1007_s10898-022-01266-5. 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.