Adaptive mirror descent algorithms for~convex~and strongly convex optimization problems with~functional constraints

F. S. Stonyakin ; M. Alkousa ; A. N. Stepanov ; A. A. Titov

Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 88-114.

Résumé

Under consideration are some adaptive mirror descent algorithms for the problems of minimization of a convex objective functional with several convex Lipschitz (generally, nonsmooth) functional constraints. It is demonstrated that the methods are applicable to the objective functionals of various levels of smoothness: The Lipschitz condition holds either for the objective functional itself or for its gradient or Hessian (while the functional itself can fail to satisfy the Lipschitz condition). The main idea is the adaptive adjustment of the method with respect to the Lipschitz constant of the objective functional (its gradient or Hessian), as well as the Lipschitz constant of the constraint. The two types of methods are considered: adaptive (not requiring the knowledge of the Lipschitz constants neither for the objective functional nor for constraints) and partially adaptive (requiring the knowledge of the Lipschitz constant for constraints). Using the restart technique, some methods are proposed for strongly convex minimization problems. Some estimates of the rate of convergence are obtained for all algorithms under consideration in dependence on the level of smoothness of the objective functional. Numerical experiments are presented to illustrate the advantages of the proposed methods for some examples. Tab. 3, bibliogr. 22.

Détail

Keywords: adaptive Mirror Descent, Lipschitz condition, Lipschitz gradient, Lipschitz Hessian, strongly convex function, the technique of restarts.

Bibliographie

[1] Ben-Tal A., Nemirovski A., “Robust truss topology design via semidefinite programming”, SIAM J. Optim., 7:4 (1997), 991–1016 | DOI | MR | Zbl

[2] Nesterov Yu., Shpirko S., “Primal-dual subgradient methods for huge-scale linear conic problem”, SIAM J. Optim., 24:3 (2014), 1444–1457 | DOI | MR | Zbl

[3] Nesterov Yu., Introductory lectures on convex optimization: A basic course, Appl. Optim., 87, Kluwer Acad. Publ., Dordrecht, 2004 | DOI | MR | Zbl

[4] F. P. Vasil'ev, Optimization Methods, v. 1, MTsNMO, M., 2011 (Russian)

[5] F. P. Vasil'ev, Optimization Methods, v. 2, MTsNMO, M., 2011 (Russian)

[6] Lan G., “Gradient sliding for composite optimization”, Math. Program., 159:1–2 (2016), 201–235 | DOI | MR | Zbl

[7] Beck A., Teboulle M., “Mirror descent and nonlinear projected subgradient methods for convex optimization”, Oper. Res. Lett., 31:3 (2003), 167–175 | DOI | MR | Zbl

[8] A. Nemirovskii, D. Yudin, “Efficient methods for large-scale convex optimization problems”, Ekonomika Mat. Metody, 1979, no. 2, 135–152 (Russian)

[9] A. Nemirovskii, D. Yudin, Problem Complexity and Method Efficiency in Optimization, J. Wiley Sons, New York, 1983 | MR

[10] N. Z. Shor, “Application of generalized gradient descent in block programming”, Kibernetika, 1967, no. 3, 53–55 (Russian) | Zbl

[11] Polyak B. T., “A general method of solving extremum problems”, Sov. Math. Dokl., 8:3 (1967), 593–597 | MR | Zbl

[12] Beck A., Ben-Tal A., Guttmann-Beck N., Tetruashvili L., “The CoMirror algorithm for solving nonsmooth constrained convex problems”, Oper. Res. Lett., 38:6 (2010), 493–498 | DOI | MR | Zbl

[13] Ben-Tal A., Nemirovski A., Lectures on modern convex optimization, SIAM, Philadelphia, PA, 2001 | MR | Zbl

[14] 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, Lect. Notes Math., 2227, Springer, Cham, 2018, 181–213 | DOI | MR | Zbl

[15] F. S. Stonyakin, M. S. Alkousa, A. N. Stepanov, M. A. Barinov, “Adaptive mirror descent algorithms in convex programming problems with Lipschitz constraints”, Trudy Inst. Mat. Mekh., 24, no. 2, 2018, 266–279 (Russian) | MR

[16] Titov A. A., Stonyakin F. S., Gasnikov A. V., Alkousa M. S., “Mirror descent and constrained online optimization problems”, Optimization and Applications, Rev. Sel. Pap. 9th Int. Conf. OPTIMA-2018 (Petrovac, Montenegro, Oct. 1–5, 2018), Commun. Comput. Inform. Sci., 974, Springer, Cham, 2018, 64–78 | DOI

[17] Nesterov Yu., Subgradient methods for convex functions with nonstandard growth properties, , 2016 http://mathnet.ru/PresentFiles/16179/growthbm_nesterov.pdf

[18] Stonyakin F. S., Titov A. A., “One mirror descent algorithm for convex constrained optimization problems with non-standard growth properties”, Proc. School-Seminar on Optimization Problems and Their Applications (Omsk, Russia, July 8–14, 2018), CEUR Workshop Proc., 2098, RWTH Aachen Univ., Aachen, 2018, 372–384 http://ceur-ws.org/Vol-2098

[19] Nesterov Yu., “A method of solving a convex programming problem with convergence rate $O(1/k^2)$”, Sov. Math. Dokl., 27:2 (1983), 372–376 | MR | Zbl

[20] Juditsky A., Nemirovski A., “First order methods for non-smooth convex large-scale optimization, I: General purpose methods”, Optimization for machine learning, MIT Press, Cambridge, MA, 2012, 121–148

[21] A. S. Bayandina, A. V. Gasnikov, E. V. Gasnikova, S. V. Matsievsky, “Primal-dual mirror descent for the stochastic programming problems with functional constraints”, Comput. Math. Math. Phys., 58:11 (2018), 1728–1736 | MR | Zbl

[22] Meng X., Chen H., Accelerating Nesterov's method for strongly convex functions with Lipschitz gradient, Cornell Univ. Libr. e-Print Archive, 2011, arXiv: 1109.6058