Adaptive Subgradient Methods for Mathematical Programming Problems with Quasiconvex Functions

S. S. Ablaev ; F. S. Stonyakin ; M. S. Alkousa ; A. V. Gasnikov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 3, pp. 7-25

Résumé

The paper is devoted to subgradient methods with switching between productive and nonproductive steps for problems of minimization of quasiconvex functions under functional inequality constraints. For the problem of minimizing a convex function with quasiconvex inequality constraints, a result is obtained on the convergence of the subgradient method with an adaptive stopping rule. Further, based on an analog of a sharp minimum for nonlinear problems with inequality constraints, results are obtained on the geometric convergence of restarted versions of subgradient methods. Such results are considered separately in the case of a convex objective function and quasiconvex inequality constraints, as well as in the case of a quasiconvex objective function and convex inequality constraints. The convexity may allow to additionally suggest adaptive stopping rules for auxiliary methods, which guarantee that an acceptable solution quality is achieved. The results of computational experiments are presented, showing the advantages of using such stopping rules.

Détail

Keywords: subgradient method, sharp minimum, restarts, adaptive method.
Mots-clés : quasiconvex function

Bibliographie

[1] Polyak B.T., “Odin obschii metod resheniya ekstremalnykh zadach”, Dokl. AN SSSR, 174:1 (1967), 33–36 | Zbl

[2] Huang Y., Lin Q., Single-loop switching subgradient methods for non-smooth weakly convex optimization with non-smooth convex constraints, 2023, 49 pp., arXiv: 2301.13314

[3] Bayandina A., Dvurechensky P., Gasnikov A., Stonyakin F., Titov A., “Mirror descent and convex optimization problems with non-smooth inequality constraints”, Large-Scale and Distributed Optimization, Lecture Notes in Math., 2227, eds. Pontus Giselsson and Anders Rantzer, 2018, 181–213 | DOI | MR | Zbl

[4] Lagae S., “New efficient techniques to solve sparse structured linear systems, with applications to truss topology optimization”, Ecole polytechnique de Louvain, Université catholique de Louvain, 2017 URL: https://dial.uclouvain.be/memoire/ucl/object/thesis:12934

[5] Nesterov Yu., “Subgradient methods for huge-scale optimization problems”, Math. Prog., 146:1–2 (2015), 275–297 | DOI | MR

[6] Stonyakin F.S., Alkusa M.S., Stepanov A.N., Barinov M.A., “Adaptivnye algoritmy zerkalnogo spuska v zadachakh vypuklogo programmirovaniya s lipshitsevymi ogranichenyami”, Tr. In-ta matematiki i mekhaniki UrO RAN, 24:2 (2018), 266–279 | DOI | MR

[7] Stonyakin F.S., Stepanov A.N., Gasnikov A.V., Titov A.A., “Mirror descent for constrained optimization problems with large subgradient values of functional constraints”, Computer Research and Modeling, 12:2 (2020), 301–317 | DOI | MR

[8] Lin Q., Ma R., Nadarajah S., Soheili N., A Parameter-free and projection-free restarting level set method for adaptive constrained conver optimization under the error bound condition, 2022, 29 pp., arXiv: 2010.15267

[9] Polyak B.T., Vvedenie v optimizatsiyu, Nauka, M., 1983, 384 pp. | MR

[10] Nesterov Yu.E., Effektivnye metody nelineinogo programmirovaniya, Radio i svyaz, M., 1989, 301 pp.

[11] Klark F., Optimizatsiya i negladkii analiz, per. s angl., ed. pod red. V. I. Blagodatskikh, Nauka, M., 1988, 280 pp. | MR

[12] Polyak B.T., “Minimizatsiya negladkikh funktsionalov”, Zhyrn. vychisl. matematiki i mat. fiz., 9:3 (1969), 509–521 | Zbl

[13] Boyd S.P., Vandenberghe L., Convex optimization, Cambridge Univ. Press, Cambridge, 2004, 716 pp. | MR | Zbl