IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v89y2024i3d10.1007_s10589-024-00612-5.html
   My bibliography  Save this article

A stochastic moving ball approximation method for smooth convex constrained minimization

Author

Listed:
  • Nitesh Kumar Singh

    (National University of Science and Technology Politehnica Bucharest)

  • Ion Necoara

    (National University of Science and Technology Politehnica Bucharest
    Gheorghe Mihoc-Caius Iacob Institute of Mathematical Statistics and Applied Mathematics of the Romanian Academy)

Abstract

In this paper, we consider constrained optimization problems with convex objective and smooth convex functional constraints. We propose a new stochastic gradient algorithm, called the Stochastic Moving Ball Approximation (SMBA) method, to solve this class of problems, where at each iteration we first take a (sub)gradient step for the objective function and then perform a projection step onto one ball approximation of a randomly chosen constraint. The computational simplicity of SMBA, which uses first-order information and considers only one constraint at a time, makes it suitable for large-scale problems with many functional constraints. We provide a convergence analysis for the SMBA algorithm using basic assumptions on the problem, that yields new convergence rates in both optimality and feasibility criteria evaluated at some average point. Our convergence proofs are novel since we need to deal properly with infeasible iterates and with quadratic upper approximations of constraints that may yield empty balls. We derive convergence rates of order $${\mathcal {O}} (k^{-1/2})$$ O ( k - 1 / 2 ) when the objective function is convex, and $${\mathcal {O}} (k^{-1})$$ O ( k - 1 ) when the objective function is strongly convex. Preliminary numerical experiments on quadratically constrained quadratic problems demonstrate the viability and performance of our method when compared to some existing state-of-the-art optimization methods and software.

Suggested Citation

  • Nitesh Kumar Singh & Ion Necoara, 2024. "A stochastic moving ball approximation method for smooth convex constrained minimization," Computational Optimization and Applications, Springer, vol. 89(3), pages 659-689, December.
  • Handle: RePEc:spr:coopap:v:89:y:2024:i:3:d:10.1007_s10589-024-00612-5
    DOI: 10.1007/s10589-024-00612-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-024-00612-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/s10589-024-00612-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. Yurii Nesterov, 2018. "Lectures on Convex Optimization," Springer Optimization and Its Applications, Springer, edition 2, number 978-3-319-91578-4, July.
    2. Ion Necoara, 2021. "General Convergence Analysis of Stochastic First-Order Methods for Composite Optimization," Journal of Optimization Theory and Applications, Springer, vol. 189(1), pages 66-95, April.
    3. M. C. Campi & S. Garatti, 2011. "A Sampling-and-Discarding Approach to Chance-Constrained Optimization: Feasibility and Optimality," Journal of Optimization Theory and Applications, Springer, vol. 148(2), pages 257-280, February.
    4. Eyal Cohen & Nadav Hallak & Marc Teboulle, 2022. "A Dynamic Alternating Direction of Multipliers for Nonconvex Minimization with Nonlinear Functional Equality Constraints," Journal of Optimization Theory and Applications, Springer, vol. 193(1), pages 324-353, June.
    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. Shota Takahashi & Mituhiro Fukuda & Mirai Tanaka, 2022. "New Bregman proximal type algorithms for solving DC optimization problems," Computational Optimization and Applications, Springer, vol. 83(3), pages 893-931, December.
    2. A. Scagliotti & P. Colli Franzone, 2022. "A piecewise conservative method for unconstrained convex optimization," Computational Optimization and Applications, Springer, vol. 81(1), pages 251-288, January.
    3. Xin Jiang & Lieven Vandenberghe, 2022. "Bregman primal–dual first-order method and application to sparse semidefinite programming," Computational Optimization and Applications, Springer, vol. 81(1), pages 127-159, January.
    4. Ritter, Andreas & Widmer, Fabio & Duhr, Pol & Onder, Christopher H., 2022. "Long-term stochastic model predictive control for the energy management of hybrid electric vehicles using Pontryagin’s minimum principle and scenario-based optimization," Applied Energy, Elsevier, vol. 322(C).
    5. Rocchetta, Roberto & Crespo, Luis G., 2021. "A scenario optimization approach to reliability-based and risk-based design: Soft-constrained modulation of failure probability bounds," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    6. 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.
    7. Molin An & Xueshan Han & Tianguang Lu, 2024. "A Stochastic Model Predictive Control Method for Tie-Line Power Smoothing under Uncertainty," Energies, MDPI, vol. 17(14), pages 1-17, July.
    8. Huiyi Cao & Kamil A. Khan, 2023. "General convex relaxations of implicit functions and inverse functions," Journal of Global Optimization, Springer, vol. 86(3), pages 545-572, July.
    9. Egor Gladin & Alexander Gasnikov & Pavel Dvurechensky, 2025. "Accuracy Certificates for Convex Minimization with Inexact Oracle," Journal of Optimization Theory and Applications, Springer, vol. 204(1), pages 1-23, January.
    10. Francisco García Riesgo & Sergio Luis Suárez Gómez & Enrique Díez Alonso & Carlos González-Gutiérrez & Jesús Daniel Santos, 2021. "Fully Convolutional Approaches for Numerical Approximation of Turbulent Phases in Solar Adaptive Optics," Mathematics, MDPI, vol. 9(14), pages 1-20, July.
    11. Pavel Shcherbakov & Mingyue Ding & Ming Yuchi, 2021. "Random Sampling Many-Dimensional Sets Arising in Control," Mathematics, MDPI, vol. 9(5), pages 1-16, March.
    12. Liam Madden & Stephen Becker & Emiliano Dall’Anese, 2021. "Bounds for the Tracking Error of First-Order Online Optimization Methods," Journal of Optimization Theory and Applications, Springer, vol. 189(2), pages 437-457, May.
    13. Shariat Torbaghan, Shahab & Madani, Mehdi & Sels, Peter & Virag, Ana & Le Cadre, Hélène & Kessels, Kris & Mou, Yuting, 2021. "Designing day-ahead multi-carrier markets for flexibility: Models and clearing algorithms," Applied Energy, Elsevier, vol. 285(C).
    14. Paul R. Rosenbaum, 2023. "Sensitivity analyses informed by tests for bias in observational studies," Biometrics, The International Biometric Society, vol. 79(1), pages 475-487, March.
    15. Xiao Liu & Simge Küçükyavuz, 2018. "A polyhedral study of the static probabilistic lot-sizing problem," Annals of Operations Research, Springer, vol. 261(1), pages 233-254, February.
    16. Xue Gao & Xingju Cai & Deren Han, 2020. "A Gauss–Seidel type inertial proximal alternating linearized minimization for a class of nonconvex optimization problems," Journal of Global Optimization, Springer, vol. 76(4), pages 863-887, April.
    17. Alexander Kononov & Yulia Zakharova, 2022. "Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion," Journal of Global Optimization, Springer, vol. 83(3), pages 539-564, July.
    18. Jean-Jacques Forneron, 2023. "Noisy, Non-Smooth, Non-Convex Estimation of Moment Condition Models," Papers 2301.07196, arXiv.org, revised Feb 2023.
    19. Azimbek Khudoyberdiev & Shabir Ahmad & Israr Ullah & DoHyeun Kim, 2020. "An Optimization Scheme Based on Fuzzy Logic Control for Efficient Energy Consumption in Hydroponics Environment," Energies, MDPI, vol. 13(2), pages 1-27, January.
    20. Ashley M. Hou & Line A. Roald, 2022. "Data-driven tuning for chance constrained optimization: analysis and extensions," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(3), pages 649-682, October.

    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:coopap:v:89:y:2024:i:3:d:10.1007_s10589-024-00612-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.