No Access

Proximal Gradient-Type Algorithms for a Class of Bilevel Programming Problems

Dan Li

Information and Engineering College, Dalian University, Dalian 116622, P. R. China

E-mail Address: lidandlm@163.com

Corresponding author.

Search for more papers by this author

Shuang Chen

Information and Engineering College, Dalian University, Dalian 116622, P. R. China

E-mail Address: chenshuang0707@163.com

Search for more papers by this author

, and

Li-Ping Pang

School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, P. R. China

E-mail Address: lppang@dlut.edu.cn

Search for more papers by this author

https://doi.org/10.1142/S0217595921500391Cited by:1 (Source: Crossref)

Abstract

A class of proximal gradient-type algorithm for bilevel nonlinear nondifferentiable programming problems with smooth substructure is developed in this paper. The original problem is approximately reformulated by explicit slow control technique to a parameterized family function which makes full use of the information of smoothness. At each iteration, we only need to calculate one proximal point analytically or with low computational cost. We prove that the accumulation iterations generated by the algorithms are solutions of the original problem. Moreover, some results of complexity of the algorithms are presented in convergence analysis. Numerical experiments are implemented to verify the efficiency of the proximal gradient algorithms for solving this kind of bilevel programming problems.

Keywords:

References

Beck, A and M Teboulle (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1), 183–202. Crossref, Web of Science, Google Scholar
Bertsekas, DP, A Nedić and AE Ozdaglar (2003). Convex Analysis and Optimization. Belmont: Athena Scientific. Google Scholar
Boyd, S, N Parikh, E Chu, B Peleato and J Eckstein (2010). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations & Trends in Machine Learning, 3(1), 1–122. Crossref, Google Scholar
Cabot, A (2005). Proximal point algorithm controlled by a slowly vanishing term: Applications to hierarchical minimization. SIAM Journal on Optimization, 15(2), 555–572. Crossref, Web of Science, Google Scholar
Dempe, S (2002). Foundations of Bilevel Programming, Nonconvex Optimization & Its Applications, Vol. 61. Dordrecht: Kluwer Academic Publishers. Google Scholar
Dempe, S, V Kalashnikov, GA Pérez-Valdés and N Kalashnykova (2015). Bilevel Programming Problems. Berlin: Springer. Crossref, Google Scholar
Goldfarb, D, S Ma and K Scheinberg (2013). Fast alternating linearization methods for minimizing the sum of two convex functions. Mathematical Programming, 141(1–2), 349–382. Crossref, Web of Science, Google Scholar
Hare, WL (2004). Nonsmooth optimization with smooth substructure. Ph.D. Thesis, Simon Fraser University. Google Scholar
Hardy, GH, JE Littlewood and G Polya (1934). Inequalities. Cambridge: Cambridge University Press. Google Scholar
He, B and X Yuan (2014). On the $O (1 / n)$ $O (1 / n)$ convergence rate of the Douglas–Rachford alternating direction method. SIAM Journal on Numerical Analysis, 50(2), 700–709. Crossref, Web of Science, Google Scholar
Hong, M, ZQ Luo and M Razaviyayn (2014). Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM Journal on Optimization, 26(1), 3836–3840. Web of Science, Google Scholar
Kiwiel, KC (1999). A projection-proximal bundle method for convex nondifferentiable minimization. Ill-Posed Variational Problems and Regularization Techniques, pp. 137–150. Berlin: Springer. Crossref, Google Scholar
Kiwiel, KC, CH Rosa and A Ruszczynski (1999). Proximal decomposition via alternating linearization. SIAM Journal on Optimization, 9(3), 668–689. Crossref, Web of Science, Google Scholar
Lemaréchal, C and C Sagastizábal (1997). Practical aspects of the Moreau-Yosida regularization: Theoretical preliminaries. SIAM Journal on Optimization, 7, 367–385. Crossref, Web of Science, Google Scholar
Li, D et al.(2019). A class of alternating linearization algorithms for nonsmooth convex optimization. Acta Mathematicae Applicatae Sinica, 35(2), 435–443. Crossref, Web of Science, Google Scholar
Lu, Y, LP Pang, FF Guo and ZQ Xia (2010). A superlinear space decomposition algorithm for constrained nonsmooth convex program. Journal of Computational & Applied Mathematics, 234(1), 224–232. Crossref, Web of Science, Google Scholar
Lv, J, LP Pang and FY Meng (2018). A proximal bundle method for constrained nonsmooth nonconvex optimization with inexact information. Journal of Global Optimization, 70(3), 517–549. Crossref, Web of Science, Google Scholar
Meng, FY et al.(2017). An approximate bundle method for solving nonsmooth equilibrium problems. Journal of Global Optimization, 68, 537–562. Crossref, Web of Science, Google Scholar
Michael, G, S Boyd and Y Ye (2008). CVX: Matlab software for disciplined convex programming. Google Scholar
Mifflin, R and C Sagastizábal (1999). $𝒱 𝒰$ -decomposition derivatives for convex max-functions. Ill-Posed Variational Problems and Regularization Techniques, Lecture Notes in Economics and Mathematical Systems, Vol. 477. Berlin: Springer. Crossref, Google Scholar
Nesterov, YE (1983). A method for solving the convex programming problem with convergence rate $O (1 / k_{2})$ . Doklady Akademii Nauk SSSR, 269, 543–547. Google Scholar
Nesterov, Y (2004). Introductory Lectures on Convex Optimization: A Basic Course. New York: Springer. Crossref, Google Scholar
Nesterov, Y (2013). Gradient methods for minimizing composite function. Mathematical Programming, 140(1), 125–161. Crossref, Web of Science, Google Scholar
Rockafellar, RT (1970). Convex Analysis. New Jersey: Princeton University Press. Crossref, Google Scholar
Rockafellar, RT and RJ-B Wets (1998). Variational Analysis, Grundlehren Series (Fundamental Principles of Mathematical Sciences), Vol. 317. Berlin: Springer. Crossref, Google Scholar
Sagastizábal, CA and MV Solodov (2005). An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter. SIAM Journal on Optimization, 16(1), 146–169. Crossref, Web of Science, Google Scholar
Solodov, MV (2007a). An explicit descent method for bilevel convex optimization. Journal of Convex Analysis, 14(2), 227. Web of Science, Google Scholar
Solodov, MV (2007b). A bundle method for a class of bilevel nonsmooth convex minimization problems. SIAM Journal on Optimization, 18, 242–259. Crossref, Web of Science, Google Scholar
Tseng, P (2008). On accelerated proximal gradient methods for convex-concave optimization. SIAM Journal on Optimization, 2, 1–20. Google Scholar
Watson, GA (1992). Characterization of the subdifferential of some matrix norms. Linear Algebra and Its Applications, 170, 33–45. Crossref, Web of Science, Google Scholar