{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T08:18:46Z","timestamp":1762157926490,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T00:00:00Z","timestamp":1728259200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T00:00:00Z","timestamp":1728259200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006595","name":"Unitatea Executiva pentru Finantarea Invatamantului Superior, a Cercetarii, Dezvoltarii si Inovarii","doi-asserted-by":"publisher","award":["PN-III-P4-PCE-2021-0720, under project L2O-MOC, nr. 70\/2022"],"award-info":[{"award-number":["PN-III-P4-PCE-2021-0720, under project L2O-MOC, nr. 70\/2022"]}],"id":[{"id":"10.13039\/501100006595","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}} (k^{-1\/2})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when the objective function is convex, and <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}} (k^{-1})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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.<\/jats:p>","DOI":"10.1007\/s10589-024-00612-5","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T21:01:44Z","timestamp":1728334904000},"page":"659-689","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A stochastic moving ball approximation method for smooth convex constrained minimization"],"prefix":"10.1007","volume":"89","author":[{"given":"Nitesh Kumar","family":"Singh","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1102-2654","authenticated-orcid":false,"given":"Ion","family":"Necoara","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"issue":"6","key":"612_CR1","doi-asserted-by":"publisher","first-page":"3232","DOI":"10.1137\/090763317","volume":"20","author":"A Auslender","year":"2010","unstructured":"Auslender, A., Shefi, R., Teboulle, M.: A moving balls approximation method for a class of smooth constrained minimization problems. SIAM J. Optim. 20(6), 3232\u20133259 (2010)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"612_CR2","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s10107-012-0582-3","volume":"142","author":"A Auslender","year":"2013","unstructured":"Auslender, A.: A very simple SQCQP method for a class of smooth convex constrained minimization problems with nice convergence results. Math. Program. 142(1\u20132), 349\u2013369 (2013)","journal-title":"Math. Program."},{"key":"612_CR3","doi-asserted-by":"crossref","unstructured":"Berthier, E., Carpentier, J., Rudi, A., Bach, F.: Infinite-dimensional sums-of-squares for optimal control. Conference on Decision and Control. 577\u2013582 (2022)","DOI":"10.1109\/CDC51059.2022.9992396"},{"issue":"6","key":"612_CR4","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1089\/cmb.2004.11.1073","volume":"11","author":"C Bhattacharyya","year":"2004","unstructured":"Bhattacharyya, C., Grate, L.R., Jordan, M.I., El Ghaoui, L., Mian, S.: Robust sparse hyperplane classifiers: application to uncertain molecular profiling data. J. Comput. Biol. 11(6), 1073\u20131089 (2004)","journal-title":"J. Comput. Biol."},{"key":"612_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-024-02057-4","author":"Digvijay Boob","year":"2024","unstructured":"Boob, Digvijay, Deng, Qi., Lan, Guanghui: Level constrained first order methods for function constrained optimization. Math. Program. (2024). https:\/\/doi.org\/10.1007\/s10107-024-02057-4","journal-title":"Math. Program."},{"issue":"1","key":"612_CR6","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s10107-021-01742-y","volume":"197","author":"Digvijay Boob","year":"2023","unstructured":"Boob, Digvijay, Deng, Qi., Lan, Guanghui: Stochastic first-order methods for convex and nonconvex functional constrained optimization. Math. Program. 197(1), 215\u2013279 (2023). https:\/\/doi.org\/10.1007\/s10107-021-01742-y","journal-title":"Math. Program."},{"issue":"1\u20132","key":"612_CR7","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s10107-013-0701-9","volume":"146","author":"J\u00e9r\u00f4me Bolte","year":"2014","unstructured":"Bolte, J\u00e9r\u00f4me., Sabach, Shoham, Teboulle, Marc: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1\u20132), 459\u2013494 (2014). https:\/\/doi.org\/10.1007\/s10107-013-0701-9","journal-title":"Math. Program."},{"key":"612_CR8","doi-asserted-by":"publisher","unstructured":"Campi, M.C., Garatti, S.: A sampling-and-discarding approach to\u00a0chance-constrained optimization: feasibility\u00a0and\u00a0optimality. J. Optim. Theory Appl. 148(2), 257\u2013280 (2011). https:\/\/doi.org\/10.1007\/s10957-010-9754-6","DOI":"10.1007\/s10957-010-9754-6"},{"key":"612_CR9","doi-asserted-by":"publisher","unstructured":"Chen, Run, Liu, Andrew L.: A distributed algorithm for high-dimension convex quadratically constrained quadratic programs. Comput. Optim. Appl. 80(3), 781\u2013830 (2021). https:\/\/doi.org\/10.1007\/s10589-021-00319-x","DOI":"10.1007\/s10589-021-00319-x"},{"issue":"1","key":"612_CR10","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/s10957-021-01929-5","volume":"193","author":"E Cohen","year":"2022","unstructured":"Cohen, E., Hallak, N., Teboulle, M.: A dynamic alternating direction of multipliers for nonconvex minimization with nonlinear functional equality constraints. J. Optim. Theory Appl. 193(1), 324\u2013353 (2022)","journal-title":"J. Optim. Theory Appl."},{"key":"612_CR11","unstructured":"FICO Xpress Optimization, https:\/\/www.fico.com\/en\/products\/fico-xpress-optimization"},{"key":"612_CR12","unstructured":"Gurobi Optimization, https:\/\/www.gurobi.com"},{"issue":"1","key":"612_CR13","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s10589-022-00384-w","volume":"83","author":"L Jin","year":"2022","unstructured":"Jin, L., Wang, X.: A stochastic primal-dual method for a class of nonconvex constrained optimization. Comput. Optim. Appl. 83(1), 143\u2013180 (2022)","journal-title":"Comput. Optim. Appl."},{"key":"612_CR14","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s10107-006-0050-z","volume":"112","author":"KC Kiwiel","year":"2008","unstructured":"Kiwiel, K.C.: Breakpoint searching algorithms for the continuous quadratic knapsack problem. Math. Program. 112, 473\u2013491 (2008)","journal-title":"Math. Program."},{"key":"612_CR15","doi-asserted-by":"crossref","unstructured":"Lewis, A., Pang, J.S.: Error bounds for convex inequality systems, Generalized Convexity, Generalized Monotonicity (J.-P. Crouzeix, J.-E.Martinez-Legaz, and M. Volle, eds.), 75\u2013110, Cambridge University Press, 1998","DOI":"10.1007\/978-1-4613-3341-8_3"},{"key":"612_CR16","unstructured":"Moulines, E., Bach, F.: Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in Neural Information Processing Systems (2011)"},{"key":"612_CR17","volume-title":"Problem complexity and method efficiency in optimization","author":"A Nemirovski","year":"1983","unstructured":"Nemirovski, A., Yudin, D.B.: Problem complexity and method efficiency in optimization. John Wiley, Hoboken (1983)"},{"issue":"4","key":"612_CR18","doi-asserted-by":"publisher","first-page":"1574","DOI":"10.1137\/070704277","volume":"19","author":"A Nemirovski","year":"2009","unstructured":"Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4), 1574\u20131609 (2009)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"612_CR19","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-011-0468-9","volume":"129","author":"A Nedich","year":"2011","unstructured":"Nedich, A.: Random algorithms for convex minimization problems. Mathem. Program. 129(2), 225\u2013273 (2011)","journal-title":"Mathem. Program."},{"issue":"5","key":"612_CR20","doi-asserted-by":"publisher","first-page":"3109","DOI":"10.1137\/120897547","volume":"52","author":"V Nedelcu","year":"2014","unstructured":"Nedelcu, V., Necoara, I., Tran Dinh, Q.: Computational complexity of inexact gradient augmented Lagrangian methods: application to constrained MPC. SIAM J. Control Optim. 52(5), 3109\u20133134 (2014)","journal-title":"SIAM J. Control Optim."},{"key":"612_CR21","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/s10957-021-01821-2","volume":"189","author":"I Necoara","year":"2021","unstructured":"Necoara, I.: General convergence analysis of stochastic first-order methods for composite optimization. J. Optim. Theory Appl. 189, 66\u201395 (2021)","journal-title":"J. Optim. Theory Appl."},{"issue":"3","key":"612_CR22","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/s00245-019-09609-7","volume":"80","author":"A Nedich","year":"2019","unstructured":"Nedich, A., Necoara, I.: Random minibatch subgradient algorithms for convex problems with functional constraints. Appl. Math. Optim. 80(3), 801\u2013833 (2019)","journal-title":"Appl. Math. Optim."},{"issue":"265","key":"612_CR23","first-page":"1","volume":"23","author":"I Necoara","year":"2022","unstructured":"Necoara, I., Singh, N.K.: Stochastic subgradient for composite convex optimization with functional constraints. J. Mach. Learn. Res. 23(265), 1\u201335 (2022)","journal-title":"J. Mach. Learn. Res."},{"key":"612_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on convex optimization","author":"Yu Nesterov","year":"2018","unstructured":"Nesterov, Yu.: Lectures on convex optimization. Springer, Berlin (2018)"},{"key":"612_CR25","doi-asserted-by":"publisher","first-page":"21","DOI":"10.21314\/JOR.2000.038","volume":"2","author":"RT Rockafellar","year":"2000","unstructured":"Rockafellar, R.T., Uryasev, S.P.: Optimization of conditional value-at-risk. J. Risk 2, 21\u201341 (2000)","journal-title":"J. Risk"},{"issue":"3","key":"612_CR26","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1214\/aoms\/1177729586","volume":"22","author":"H Robbins","year":"1951","unstructured":"Robbins, H., Monro, S.: A stochastic approximation method. Ann. Math. Stat. 22(3), 400\u2013407 (1951)","journal-title":"Ann. Math. Stat."},{"key":"612_CR27","doi-asserted-by":"publisher","DOI":"10.1080\/02331934.2023.2189015","author":"NK Singh","year":"2023","unstructured":"Singh, N.K., Necoara, I., Kungurtsev, V.: Mini-batch stochastic subgradient for functional constrained optimization. Optimization (2023). https:\/\/doi.org\/10.1080\/02331934.2023.2189015","journal-title":"Optimization"},{"key":"612_CR28","doi-asserted-by":"crossref","unstructured":"Tibshirani, R.: The solution path of the generalized lasso, Phd Thesis, Stanford University, (2011)","DOI":"10.1214\/11-AOS878"},{"key":"612_CR29","volume-title":"Statistical learning theory","author":"V Vapnik","year":"1998","unstructured":"Vapnik, V.: Statistical learning theory. John Wiley, Hoboken (1998)"},{"issue":"1","key":"612_CR30","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1137\/130931278","volume":"26","author":"M Wang","year":"2016","unstructured":"Wang, M., Bertsekas, D.P.: Stochastic first-order methods with random constraint projection. SIAM J. Optim. 26(1), 681\u2013717 (2016)","journal-title":"SIAM J. Optim."},{"key":"612_CR31","doi-asserted-by":"crossref","unstructured":"Wang, C., Bahreinian, M., Tron, R.: Chance constraint robust control with control barrier functions. American Control Conference. USA, 2315\u20132322 (2021)","DOI":"10.23919\/ACC50511.2021.9482973"},{"issue":"2","key":"612_CR32","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.1137\/18M1229869","volume":"30","author":"Y Xu","year":"2020","unstructured":"Xu, Y.: Primal-dual stochastic gradient method for convex programs with many functional constraints. SIAM J. Optim. 30(2), 1664\u20131692 (2020)","journal-title":"SIAM J. Optim."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00612-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-024-00612-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00612-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T13:12:57Z","timestamp":1731676377000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-024-00612-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["612"],"URL":"https:\/\/doi.org\/10.1007\/s10589-024-00612-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"13 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}