{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T00:43:56Z","timestamp":1772757836037,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T00:00:00Z","timestamp":1708905600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T00:00:00Z","timestamp":1708905600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004871","name":"Technische Universit\u00e4t Braunschweig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004871","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Gradient-based methods have been highly successful for solving a variety of both unconstrained and constrained nonlinear optimization problems. In real-world applications, such as optimal control or machine learning, the necessary function and derivative information may be corrupted by noise, however. Sun and Nocedal have recently proposed a remedy for smooth unconstrained problems by means of a stabilization of the acceptance criterion for computed iterates, which leads to convergence of the iterates of a trust-region method to a region of criticality (Sun and Nocedal in Math Program 66:1\u201328, 2023. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1007\/s10107-023-01941-9\">https:\/\/doi.org\/10.1007\/s10107-023-01941-9<\/jats:ext-link>). We extend their analysis to the successive linear programming algorithm (Byrd et al. in Math Program 100(1):27\u201348, 2003. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1007\/s10107-003-0485-4\">https:\/\/doi.org\/10.1007\/s10107-003-0485-4<\/jats:ext-link>, SIAM J Optim 16(2):471\u2013489, 2005. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1137\/S1052623403426532\">https:\/\/doi.org\/10.1137\/S1052623403426532<\/jats:ext-link>) for unconstrained optimization problems with objectives that can be characterized as the composition of a polyhedral function with a smooth function, where the latter and its gradient may be corrupted by noise. This gives the flexibility to cover, for example, (sub)problems arising in image reconstruction or constrained optimization algorithms. We provide computational examples that illustrate the findings and point to possible strategies for practical determination of the stabilization parameter that balances the size of the critical region with a relaxation of the acceptance criterion (or descent property) of the algorithm.<\/jats:p>","DOI":"10.1007\/s10589-024-00564-w","type":"journal-article","created":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T14:02:05Z","timestamp":1708956125000},"page":"567-601","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Convergence of successive linear programming algorithms for noisy functions"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3948-9344","authenticated-orcid":false,"given":"Christoph","family":"Hansknecht","sequence":"first","affiliation":[]},{"given":"Christian","family":"Kirches","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Manns","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,26]]},"reference":[{"key":"564_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-023-01941-9","volume":"66","author":"S Sun","year":"2023","unstructured":"Sun, S., Nocedal, J.: A trust region method for noisy unconstrained optimization. Math. Program. 66, 1\u201328 (2023). https:\/\/doi.org\/10.1007\/s10107-023-01941-9","journal-title":"Math. Program."},{"issue":"1","key":"564_CR2","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s10107-003-0485-4","volume":"100","author":"RH Byrd","year":"2003","unstructured":"Byrd, R.H., Gould, N.I., Nocedal, J., Waltz, R.A.: An algorithm for nonlinear optimization using linear programming and equality constrained subproblems. Math. Program. 100(1), 27\u201348 (2003). https:\/\/doi.org\/10.1007\/s10107-003-0485-4","journal-title":"Math. Program."},{"issue":"2","key":"564_CR3","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/S1052623403426532","volume":"16","author":"RH Byrd","year":"2005","unstructured":"Byrd, R.H., Gould, N.I., Nocedal, J., Waltz, R.A.: On the convergence of successive linear-quadratic programming algorithms. SIAM J. Optim. 16(2), 471\u2013489 (2005). https:\/\/doi.org\/10.1137\/S1052623403426532","journal-title":"SIAM J. Optim."},{"key":"564_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-40065-5","volume-title":"Numerical Optimization","author":"S Wright","year":"2006","unstructured":"Wright, S., Nocedal, J., et al.: Numerical Optimization, 2nd edn. Springer, Berlin (2006). https:\/\/doi.org\/10.1007\/978-0-387-40065-5","edition":"2"},{"issue":"1","key":"564_CR5","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"R Tibshirani","year":"1996","unstructured":"Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B Methodol. 58(1), 267\u2013288 (1996). https:\/\/doi.org\/10.1111\/j.2517-6161.1996.tb02080.x","journal-title":"J. R. Stat. Soc. Ser. B Methodol."},{"issue":"8","key":"564_CR6","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"EJ Candes","year":"2006","unstructured":"Candes, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. A J. Issued Courant Inst. Math. Sci. 59(8), 1207\u20131223 (2006). https:\/\/doi.org\/10.1002\/cpa.20124","journal-title":"Commun. Pure Appl. Math. A J. Issued Courant Inst. Math. Sci."},{"issue":"3","key":"564_CR7","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF00342633","volume":"20","author":"K Fukushima","year":"1975","unstructured":"Fukushima, K.: Cognitron: a self-organizing multilayered neural network. Biol. Cybernet. 20(3), 121\u2013136 (1975). https:\/\/doi.org\/10.1007\/BF00342633","journal-title":"Biol. Cybernet."},{"issue":"2","key":"564_CR8","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1137\/15M103580X","volume":"9","author":"T Aspelmeier","year":"2016","unstructured":"Aspelmeier, T., Charitha, C., Luke, D.R.: Local linear convergence of the admm\/douglas-rachford algorithms without strong convexity and application to statistical imaging. SIAM J. Imaging Sci. 9(2), 842\u2013868 (2016). https:\/\/doi.org\/10.1137\/15M103580X","journal-title":"SIAM J. Imaging Sci."},{"issue":"4","key":"564_CR9","doi-asserted-by":"publisher","first-page":"1721","DOI":"10.1137\/11082381X","volume":"21","author":"C Cartis","year":"2011","unstructured":"Cartis, C., Gould, N.I., Toint, P.L.: On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming. SIAM J. Optim. 21(4), 1721\u20131739 (2011). https:\/\/doi.org\/10.1137\/11082381X","journal-title":"SIAM J. Optim."},{"issue":"1","key":"564_CR10","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s11228-015-0352-5","volume":"24","author":"P Apkarian","year":"2016","unstructured":"Apkarian, P., Noll, D., Ravanbod, L.: Nonsmooth bundle trust-region algorithm with applications to robust stability. Set-Valued Var. Anal. 24(1), 115\u2013148 (2016). https:\/\/doi.org\/10.1007\/s11228-015-0352-5","journal-title":"Set-Valued Var. Anal."},{"key":"564_CR11","doi-asserted-by":"publisher","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., et al: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends\u00ae Mach. Learn. 3(1), 1\u2013122 (2011). https:\/\/doi.org\/10.1561\/2200000016","DOI":"10.1561\/2200000016"},{"issue":"1","key":"564_CR12","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10107-012-0629-5","volume":"140","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Gradient methods for minimizing composite functions. Math. Program. 140(1), 125\u2013161 (2013). https:\/\/doi.org\/10.1007\/s10107-012-0629-5","journal-title":"Math. Program."},{"issue":"4","key":"564_CR13","doi-asserted-by":"publisher","first-page":"1307","DOI":"10.1137\/0907087","volume":"7","author":"F Santosa","year":"1986","unstructured":"Santosa, F., Symes, W.W.: Linear inversion of band-limited reflection seismograms. SIAM J. Sci. Stat. Comput. 7(4), 1307\u20131330 (1986). https:\/\/doi.org\/10.1137\/0907087","journal-title":"SIAM J. Sci. Stat. Comput."},{"issue":"1","key":"564_CR14","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01588250","volume":"17","author":"S-P Han","year":"1979","unstructured":"Han, S.-P., Mangasarian, O.L.: Exact penalty functions in nonlinear programming. Math. Program. 17(1), 251\u2013269 (1979). https:\/\/doi.org\/10.1007\/BF01588250","journal-title":"Math. Program."},{"issue":"1","key":"564_CR15","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1137\/20M1373190","volume":"32","author":"H-JM Shi","year":"2022","unstructured":"Shi, H.-J.M., Xie, Y., Byrd, R., Nocedal, J.: A noise-tolerant quasi-newton algorithm for unconstrained optimization. SIAM J. Optim. 32(1), 29\u201355 (2022). https:\/\/doi.org\/10.1137\/20M1373190","journal-title":"SIAM J. Optim."},{"issue":"3","key":"564_CR16","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1007\/s10589-022-00448-x","volume":"84","author":"B Irwin","year":"2023","unstructured":"Irwin, B., Haber, E.: Secant penalized bfgs: a noise robust quasi-newton method via penalizing the secant condition. Comput. Optim. Appl. 84(3), 651\u2013702 (2023). https:\/\/doi.org\/10.1007\/s10589-022-00448-x","journal-title":"Comput. Optim. Appl."},{"key":"564_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-023-01999-5","volume":"66","author":"L Cao","year":"2023","unstructured":"Cao, L., Berahas, A.S., Scheinberg, K.: First-and second-order high probability complexity bounds for trust-region methods with noisy oracles. Math. Program. 66, 1\u201352 (2023). https:\/\/doi.org\/10.1007\/s10107-023-01999-5","journal-title":"Math. Program."},{"issue":"1","key":"564_CR18","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s11081-020-09507-w","volume":"22","author":"R Gal","year":"2021","unstructured":"Gal, R., Haber, E., Irwin, B., Saleh, B., Ziv, A.: How to catch a lion in the desert: on the solution of the coverage directed generation (cdg) problem. Optim. Eng. 22(1), 217\u2013245 (2021). https:\/\/doi.org\/10.1007\/s11081-020-09507-w","journal-title":"Optim. Eng."},{"issue":"3","key":"564_CR19","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1287\/ijoo.2018.0010","volume":"1","author":"FE Curtis","year":"2019","unstructured":"Curtis, F.E., Scheinberg, K., Shi, R.: A stochastic trust region algorithm based on careful step normalization. Informs J. Optim. 1(3), 200\u2013220 (2019). https:\/\/doi.org\/10.1287\/ijoo.2018.0010","journal-title":"Informs J. Optim."},{"issue":"2","key":"564_CR20","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1137\/18M1177718","volume":"29","author":"AS Berahas","year":"2019","unstructured":"Berahas, A.S., Byrd, R.H., Nocedal, J.: Derivative-free optimization of noisy functions via quasi-newton methods. SIAM J. Optim. 29(2), 965\u2013993 (2019). https:\/\/doi.org\/10.1137\/18M1177718","journal-title":"SIAM J. Optim."},{"issue":"1","key":"564_CR21","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/19M1240794","volume":"30","author":"Y Xie","year":"2020","unstructured":"Xie, Y., Byrd, R.H., Nocedal, J.: Analysis of the BFGS method with errors. SIAM J. Optim. 30(1), 182\u2013209 (2020). https:\/\/doi.org\/10.1137\/19M1240794","journal-title":"SIAM J. Optim."},{"key":"564_CR22","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2022). https:\/\/www.gurobi.com"},{"issue":"1","key":"564_CR23","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s12532-017-0130-5","volume":"10","author":"Q Huangfu","year":"2018","unstructured":"Huangfu, Q., Hall, J.J.: Parallelizing the dual revised simplex method. Math. Program. Comput. 10(1), 119\u2013142 (2018). https:\/\/doi.org\/10.1007\/s12532-017-0130-5","journal-title":"Math. Program. Comput."},{"key":"564_CR24","doi-asserted-by":"publisher","unstructured":"Byrd, R.H., Nocedal, J., Waltz, R.A.: Knitro: an integrated package for nonlinear optimization. In: Large-Sscale Nonlinear Optimization, pp. 35\u201359. Springer, Berlin (2006). https:\/\/doi.org\/10.1007\/0-387-30065-1_4","DOI":"10.1007\/0-387-30065-1_4"},{"key":"564_CR25","doi-asserted-by":"publisher","unstructured":"Fletcher, R.: Practical Methods of Optimization: Vol. 2: Constrained Optimization (1981). https:\/\/doi.org\/10.1002\/9781118723203","DOI":"10.1002\/9781118723203"},{"issue":"2","key":"564_CR26","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/BF02591750","volume":"31","author":"Y-x Yuan","year":"1985","unstructured":"Yuan, Y.-x: Conditions for convergence of trust region algorithms for nonsmooth optimization. Math. Program. 31(2), 220\u2013228 (1985). https:\/\/doi.org\/10.1007\/BF02591750","journal-title":"Math. Program."},{"key":"564_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02431-3","volume-title":"Variational Analysis","author":"RT Rockafellar","year":"2009","unstructured":"Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis, vol. 317. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-02431-3"},{"issue":"7825","key":"564_CR28","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/s41586-020-2649-2","volume":"585","author":"CR Harris","year":"2020","unstructured":"Harris, C.R., Millman, K.J., van der Walt, S.J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N.J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M.H., Brett, M., Haldane, A., del R\u00edo, J.F., Wiebe, M., Peterson, P., G\u00e9rard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., Oliphant, T.E.: Array programming with NumPy. Nature 585(7825), 357\u2013362 (2020). https:\/\/doi.org\/10.1038\/s41586-020-2649-2","journal-title":"Nature"},{"key":"564_CR29","doi-asserted-by":"publisher","unstructured":"Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S.J., Brett, M., Wilson, J., Millman, K.J., Mayorov, N., Nelson, A.R.J., Jones, E., Kern, R., Larson, E., Carey, C.J., Polat, \u0130, Feng, Y., Moore, E.W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E.A., Harris, C.R., Archibald, A.M., Ribeiro, A.H., Pedregosa, F., van Mulbregt, P.: SciPy 1.0 Contributors: SciPy 1.0: fundamental algorithms for scientific computing in python. Nat. Methods 17, 261\u2013272 (2020). https:\/\/doi.org\/10.1038\/s41592-019-0686-2","DOI":"10.1038\/s41592-019-0686-2"},{"issue":"1","key":"564_CR30","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-004-0559-y","volume":"106","author":"A W\u00e4chter","year":"2006","unstructured":"W\u00e4chter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25\u201357 (2006). https:\/\/doi.org\/10.1007\/s10107-004-0559-y","journal-title":"Math. Program."},{"issue":"2","key":"564_CR31","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1214\/aoms\/1177692644","volume":"43","author":"G Marsaglia","year":"1972","unstructured":"Marsaglia, G.: Choosing a point from the surface of a sphere. Ann. Math. Stat. 43(2), 645\u2013646 (1972). https:\/\/doi.org\/10.1214\/aoms\/1177692644","journal-title":"Ann. Math. Stat."},{"issue":"3","key":"564_CR32","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s10589-014-9687-3","volume":"60","author":"NI Gould","year":"2015","unstructured":"Gould, N.I., Orban, D., Toint, P.L.: Cutest: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl. 60(3), 545\u2013557 (2015). https:\/\/doi.org\/10.1007\/s10589-014-9687-3","journal-title":"Comput. Optim. Appl."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00564-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-024-00564-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00564-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T16:09:10Z","timestamp":1715616550000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-024-00564-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,26]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["564"],"URL":"https:\/\/doi.org\/10.1007\/s10589-024-00564-w","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,26]]},"assertion":[{"value":"16 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}