American Institute of Mathematical Sciences

Advanced
  • 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

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 & 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.  Google Scholar

[2]

S. Dempe, Foundations of Bilevel Programming, Nonconvex Optimization and its Applications, 61, Kluwer Academic Publishers, Dordrecht, 2002.  Google Scholar

[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.  Google Scholar

[4]

K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, 1133, Springer-Verlag, Berlin, 1985.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

O. L. Mangasarian, Sufficiency of exact penalty minimization, SIAM Journal on Control and Optimization, 23 (1985), 30-37. doi: 10.1137/0323003.  Google Scholar

[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.  Google Scholar

[10]

R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, New Jersey, 1970.  Google Scholar

[11]

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

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

D. P. Bertsekas, Convex Analysis and Optimization, With Angelia Nedić and Asuman E. Ozdaglar, Athena Scientific, Belmont, MA, 2003.  Google Scholar

[2]

S. Dempe, Foundations of Bilevel Programming, Nonconvex Optimization and its Applications, 61, Kluwer Academic Publishers, Dordrecht, 2002.  Google Scholar

[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.  Google Scholar

[4]

K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, 1133, Springer-Verlag, Berlin, 1985.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

O. L. Mangasarian, Sufficiency of exact penalty minimization, SIAM Journal on Control and Optimization, 23 (1985), 30-37. doi: 10.1137/0323003.  Google Scholar

[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.  Google Scholar

[10]

R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, New Jersey, 1970.  Google Scholar

[11]

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

[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.  Google Scholar

[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.  Google Scholar

[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]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305
[14]

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
[15]

Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091
[16]

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
[17]

Bhawna Kohli. Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020114
[18]

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
[19]

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
[20]

Tim Hoheisel, Maxime Laborde, Adam Oberman. A regularization interpretation of the proximal point method for weakly convex functions. Journal of Dynamics & Games, 2020, 7 (1) : 79-96. doi: 10.3934/jdg.2020005

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (55)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences