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

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

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.
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 & 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, (2003).

[2]

S. Dempe, Foundations of Bilevel Programming,, Nonconvex Optimization and its Applications, (2002).

[3]

M. Hintermüller, A proximal bundle method based on approximate subgradients,, Computational Optimization and Applications, 20 (2001), 245. doi: 10.1023/A:1011259017643.

[4]

K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization,, Lecture Notes in Mathematics, (1133).

[5]

K. C. Kiwiel, Approximations in proximal bundle methods and decomposition of convex programs,, J. Optim. Theory Appl., 84 (1995), 529. 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. 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. doi: 10.1137/S1052623494267127.

[8]

O. L. Mangasarian, Sufficiency of exact penalty minimization,, SIAM Journal on Control and Optimization, 23 (1985), 30. 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., (1992).

[10]

R. T. Rockafellar, Convex Analysis,, Princeton Mathematical Series, (1970).

[11]

R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM. Control Optim., 14 (1976), 877. doi: 10.1137/0314056.

[12]

R. T. Rockafellar and R. J. -B. Wets, Variational Analysis,, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], (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. doi: 10.1137/050647566.

show all references

References:
[1]

D. P. Bertsekas, Convex Analysis and Optimization,, With Angelia Nedić and Asuman E. Ozdaglar, (2003).

[2]

S. Dempe, Foundations of Bilevel Programming,, Nonconvex Optimization and its Applications, (2002).

[3]

M. Hintermüller, A proximal bundle method based on approximate subgradients,, Computational Optimization and Applications, 20 (2001), 245. doi: 10.1023/A:1011259017643.

[4]

K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization,, Lecture Notes in Mathematics, (1133).

[5]

K. C. Kiwiel, Approximations in proximal bundle methods and decomposition of convex programs,, J. Optim. Theory Appl., 84 (1995), 529. 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. 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. doi: 10.1137/S1052623494267127.

[8]

O. L. Mangasarian, Sufficiency of exact penalty minimization,, SIAM Journal on Control and Optimization, 23 (1985), 30. 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., (1992).

[10]

R. T. Rockafellar, Convex Analysis,, Princeton Mathematical Series, (1970).

[11]

R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM. Control Optim., 14 (1976), 877. doi: 10.1137/0314056.

[12]

R. T. Rockafellar and R. J. -B. Wets, Variational Analysis,, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], (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. 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 & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

[2]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283

[3]

Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585

[4]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[5]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895

[6]

Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357

[7]

Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767

[8]

Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092

[9]

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 & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485

[10]

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 & Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533

[11]

Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743

[12]

Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305

[13]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79

[14]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171

[15]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[16]

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 & Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167

[17]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[18]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965

[19]

Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361

[20]

Michael Hintermüller, Tao Wu. Bilevel optimization for calibrating point spread functions in blind deconvolution. Inverse Problems & Imaging, 2015, 9 (4) : 1139-1169. doi: 10.3934/ipi.2015.9.1139

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]