PROXIMAL ALGORITHMS FOR BI-LEVEL CONVEX OPTIMIZATION PROBLEMS
Abstract
In this paper, problems of bi-level convex minimization in a Hilbert space are considered. The bi-level convex minimization problem is to minimize the first convex function on the set of minima of the second convex function. This setting has many applications, but the implicit constraints generated by the internal problem make it difficult to obtain optimality conditions and construct algorithms. Multilevel optimization problems are formulated in a similar way, the source of which is the operation research problems (optimization according to sequentially specified criteria or lexicographic optimization). Attention is focused on problem solving using two proximal methods. The main theoretical results are theorems on the convergence of methods in various situations. The first of the methods is obtained by combining the penalty function method and the proximal method. Strong convergence is proved in the case of strong convexity of the function of the exterior problem. In the general case, only weak convergence has been proved. The second, the so-called proximal-gradient method, is a combination of one of the variants of the fast proximal-gradient algorithm with the method of penalty functions. The rates of convergence of the proximal-gradient method and its weak convergence are proved.
References
Podinovskii V.V., Gavrilov V.M. Optimization with respect to successively applied criteria. Moscow: Sovetskoe Radio, 1975. 192 p.
Bakushinskii A. B., Goncharskii A. V. Iterative Methods for Solving Ill-Posed Problems. Moscow: Nauka, 1989. 126 p.
Attouch H. Viscosity Solutions of Minimization Problems. SIAM J. on Optim. 1996. Vol. 6. P. 769–806.
Solodov M. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis. 2007. Vol. 4. P. 227–238.
Solodov M. A bundle method for a class of bilevel nonsmooth convex minimization problems. SIAM J. on Optim. 2007. Vol. 18. P. 242–259.
Guler O. On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 1991. Vol. 29. P. 403–419.
Passty G.B. Ergodic Convergence to a Zero of the Sum of Monotone Operators in Hilbert Spaces. Journal of Mathematical Analysis and Applications. 1979. Vol. 72. P. 383-390.
Malitsky Yu. Chambolle-Pock and Tseng's methods: relationship and extension to the bilevel optimization. arXiv:1706.02602. 2017.
Luita A.V., Semenov V.V. A novel method for the bilevel optimization problem. XXXII International Conference “Problems of decision making under uncertainties”. August 27-31, 2018. Prague, Czech Republic. Abstracts. P. 81–82.
Luita A.V., Semenov V.V. A novel proximal-gradient method for the bilevel optimization problem. Proceedings of the XXIV All-Ukrainian Scientific Conference “Contemporary Problems of Applied Mathematics and Informatics”. September 26-28, 2018. Lviv. P. 77–79.
Tseng P. On accelerated proximal gradient methods for convex-concave optimization. 2008. http://www.mit.edu/~dimitrib/PTseng/papers/apgm.pdf.
