• 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

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

[2]

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

[3]

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

[4]

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

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

[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.  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.  doi: 10.1137/S1052623494267127.  Google Scholar

[8]

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

[10]

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

[11]

R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM. Control Optim., 14 (1976), 877.  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], (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.  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, (2003).   Google Scholar

[2]

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

[3]

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

[4]

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

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

[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.  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.  doi: 10.1137/S1052623494267127.  Google Scholar

[8]

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

[10]

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

[11]

R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM. Control Optim., 14 (1976), 877.  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], (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.  doi: 10.1137/050647566.  Google Scholar

[1]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[2]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[3]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[4]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

[5]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[6]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[7]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[8]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[9]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[10]

Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020264

[11]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[12]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]