An alternating linearization method with inexact data for bilevel nonsmooth convex optimization

Previous Article
Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems
JIMO Home
This Issue
Next Article
Performance analysis of renewal input $(a,c,b)$ policy queue with multiple working vacations and change over times

July 2014, 10(3): 859-869. doi: 10.3934/jimo.2014.10.859

An alternating linearization method with inexact data for bilevel nonsmooth convex optimization

Dan Li ^1, , Li-Ping Pang ^1, , Fang-Fang Guo ^1, and Zun-Quan Xia ^1,

1.	School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, Liaoning, China, China, China, China

Received December 2011 Revised June 2013 Published November 2013

Abstract
Related Papers

An alternating linearization method with inexact data, for the bilevel problem of minimizing a nonsmooth convex function over the optimal solution set of another nonsmooth convex problem, is presented in this paper. The problem is first approximately transformed into an unconstrained optimization with the help of a penalty function and we prove that the penalty function admits exact penalization under some mild conditions. The objective function of this unconstrained problem is the sum of two nonsmooth convex functions and in the algorithm each iteration involves solving two easily solved subproblems. It is shown that the iterative sequence converges to a solution of the original problem by parametric minimization theorem. Numerical experiments validate the theoretical convergence analysis and illustrate the implementation of the alternating linearization algorithm for this bilevel program.

Keywords: bilevel programming., exact penalty function, convex programming, nonsmooth optimization, Proximal point.

Mathematics Subject Classification: Primary: 90C25, 90C30; Secondary: 49J52, 49M27, 49M3.

Citation: Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

References:

[1]	D. P. Bertsekas, Convex Analysis and Optimization, With Angelia Nedić and Asuman E. Ozdaglar, Athena Scientific, Belmont, MA, 2003.
[2]	S. Dempe, Foundations of Bilevel Programming, Nonconvex Optimization and its Applications, 61, Kluwer Academic Publishers, Dordrecht, 2002.
[3]	M. Hintermüller, A proximal bundle method based on approximate subgradients, Computational Optimization and Applications, 20 (2001), 245-266. doi: 10.1023/A:1011259017643.
[4]	K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, 1133, Springer-Verlag, Berlin, 1985.
[5]	K. C. Kiwiel, Approximations in proximal bundle methods and decomposition of convex programs, J. Optim. Theory Appl., 84 (1995), 529-548. doi: 10.1007/BF02191984.
[6]	K. C. Kiwiel, C. H. Rosa and A. Ruszczyński, Proximal decomposition via alternating linearization, SIAM J. Optimization, 9 (1999), 668-689. doi: 10.1137/S1052623495288064.
[7]	C. Lemaréchal and C. Sagastizábal, Practical aspects of the Moreau-Yosida regularization: Theoretical preliminaries, SIAM J. Optim., 7 (1997), 367-385. doi: 10.1137/S1052623494267127.
[8]	O. L. Mangasarian, Sufficiency of exact penalty minimization, SIAM Journal on Control and Optimization, 23 (1985), 30-37. doi: 10.1137/0323003.
[9]	M. M. Mäkelä and P. Neittaanmäki, Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, World Scientific Publishing Co., Inc., River Edge, New Jersey, 1992.
[10]	R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, New Jersey, 1970.
[11]	R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM. Control Optim., 14 (1976), 877-898. doi: 10.1137/0314056.
[12]	R. T. Rockafellar and R. J. -B. Wets, Variational Analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 317, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.
[13]	M. V. Solodov, A bundle method for a class of bilevel nonsmooth convex minimization problems, SIAM J. Optimization, 18 (2007), 242-259. doi: 10.1137/050647566.

show all references

References:

[1]	D. P. Bertsekas, Convex Analysis and Optimization, With Angelia Nedić and Asuman E. Ozdaglar, Athena Scientific, Belmont, MA, 2003.
[2]	S. Dempe, Foundations of Bilevel Programming, Nonconvex Optimization and its Applications, 61, Kluwer Academic Publishers, Dordrecht, 2002.
[3]	M. Hintermüller, A proximal bundle method based on approximate subgradients, Computational Optimization and Applications, 20 (2001), 245-266. doi: 10.1023/A:1011259017643.
[4]	K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, 1133, Springer-Verlag, Berlin, 1985.
[5]	K. C. Kiwiel, Approximations in proximal bundle methods and decomposition of convex programs, J. Optim. Theory Appl., 84 (1995), 529-548. doi: 10.1007/BF02191984.
[6]	K. C. Kiwiel, C. H. Rosa and A. Ruszczyński, Proximal decomposition via alternating linearization, SIAM J. Optimization, 9 (1999), 668-689. doi: 10.1137/S1052623495288064.
[7]	C. Lemaréchal and C. Sagastizábal, Practical aspects of the Moreau-Yosida regularization: Theoretical preliminaries, SIAM J. Optim., 7 (1997), 367-385. doi: 10.1137/S1052623494267127.
[8]	O. L. Mangasarian, Sufficiency of exact penalty minimization, SIAM Journal on Control and Optimization, 23 (1985), 30-37. doi: 10.1137/0323003.
[9]	M. M. Mäkelä and P. Neittaanmäki, Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, World Scientific Publishing Co., Inc., River Edge, New Jersey, 1992.
[10]	R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, New Jersey, 1970.
[11]	R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM. Control Optim., 14 (1976), 877-898. doi: 10.1137/0314056.
[12]	R. T. Rockafellar and R. J. -B. Wets, Variational Analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 317, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.
[13]	M. V. Solodov, A bundle method for a class of bilevel nonsmooth convex minimization problems, SIAM J. Optimization, 18 (2007), 242-259. doi: 10.1137/050647566.

[1]	Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[2]	Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[3]	Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283
[4]	Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[5]	Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585
[6]	Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895
[7]	Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems and Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357
[8]	Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial and Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767
[9]	Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092
[10]	Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial and Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743
[11]	Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[12]	Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial and Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533
[13]	Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems and Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305
[14]	Aleksandar Jović. Saddle-point type optimality criteria, duality and a new approach for solving nonsmooth fractional continuous-time programming problems. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022025
[15]	Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79
[16]	Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091
[17]	Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529
[18]	Bhawna Kohli. Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3209-3221. doi: 10.3934/jimo.2020114
[19]	Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[20]	Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Dan Li Li-Ping Pang Fang-Fang Guo Zun-Quan Xia
on Google Scholar
Dan Li Li-Ping Pang Fang-Fang Guo Zun-Quan Xia

[Back to Top]