Volume 26, No 3, 2019, P. 88-114

UDC 519.85
F. S. Stonyakin, M. Alkousa, A. N. Stepanov, and A. A. Titov
Adaptive mirror descent algorithms for convex and strongly convex optimization problems with functional constraints

Abstract:
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.

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

DOI: 10.33048/daio.2019.26.636

Fedor S. Stonyakin ^1,2
Mohammad Alkousa ²
Aleksey N. Stepanov ¹
Aleksandr A. Titov ²
1. Vernadsky Crimean Federal University,
4 Vernadsky Avenue, 295007 Simferopol, Russia
2. Moscow Institute of Physics and Technologies,
9 Institutskii Bystreet, 141701 Dolgoprudnyi, Russia
e-mail: fedyor@mail.ru, mohammad.alkousa@phystech.edu, stepanov.student@gmail.com, a.a.titov@phystech.edu

Received October 17, 2018
Revised February 24, 2019
Accepted February 27, 2019

References

[1] A. Ben-Tal and A. Nemirovski, Robust truss topology design via semidefinite programming, SIAM J. Optim. 7 (4), 991–1016 (1997).

[2] Yu. Nesterov and S. Shpirko, Primal-dual subgradient methods for hugescale linear conic problem, SIAM J. Optim. 24 (3), 1444–1457 (2014).

[3] Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course (Kluwer Acad. Publ., Massachusetts, 2004).

[4] F. P. Vasil’ev, Optimization Methods, Vol. 1 (MTsNMO, Moscow, 2011) [Russian].

[5] F. P. Vasil’ev, Optimization Methods, Vol. 2 (MTsNMO, Moscow, 2011) [Russian].

[6] G. Lan, Gradient sliding for composite optimization, Math. Program. 159 (1–2), 201–235 (2016).

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

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

[9] A. Nemirovskii and D. Yudin, Problem Complexity and Method Efficiency in Optimization (Nauka, Moscow, 1979 [Russian]; J. Wiley & Sons, New York, 1983).

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

[11] B. T. Polyak, A general method of solving extremum problems, Soviet Math. Dokl. 8 (3), 593–597 (1967).

[12] A. Beck, A. Ben-Tal, N. Guttmann-Beck, and L. Tetruashvili, The CoMirror Algorithm for solving nonsmooth constrained convex problems, Oper. Res. Lett. 38 (6), 493–498 (2010).

[13] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization (SIAM, Philadelphia, 2001).

[14] A. Bayandina, P. Dvurechensky, A. Gasnikov, F. Stonyakin, and A. Titov, Mirror descent and convex optimization problems with non-smooth inequality constraints, in Large-Scale and Distributed Optimization: Lecture Notes in Mathematics, Vol. 2227 (Springer, Cham, 2018), pp. 181–213.

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

[16] A. A. Titov, F. S. Stonyakin, A. V. Gasnikov, and M. S. Alkousa, Mirror descent and constrained online optimization problems optimization and applications, in Optimization and Applications: Revised Selected Papers, 9th International Conference OPTIMA-2018 (Petrovac, Montenegro, October 1-5, 2018). Ser. Communications in Computer and Information Science, Vol. 974 (Springer, Cham, 2019), pp. 64–78.

[17] Yu. Nesterov, Subgradient methods for convex functions with nonstandard growth properties, (2016). Available at www.mathnet.ru:8080/PresentFiles/16179/growthbm_nesterov.pdf.

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

[19] Yu. Nesterov, A method of solving a convex programming problem with convergence rate $O(1/k^2)$, Soviet Math. Doklady 27 (2), 372–376 (1983).

[20] A. Juditsky and A. Nemirovski, First order methods for non-smooth convex large-scale optimization. I: General purpose methods, in Optimization for Machine Learning, (MIT Press, Cambridge, MA, 2012), pp. 121–148.

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

[22] X. Meng and H. Chen, Accelerating Nesterov’s method for strongly convex functions with Lipschitz gradient, (Cornell Univ. Libr. e-Print Archive, 2011; arXiv: 1109.6058). Available at https://arxiv.org/pdf/1109.6058.pdf.