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

Dan Li; Li-Ping Pang; Fang-Fang Guo; Zun-Quan Xia

doi:10.3934/jimo.2014.10.859

Article Contents

2014, Volume 10, Issue 3: 859-869. Doi: 10.3934/jimo.2014.10.859

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

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

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

Received: November 30, 2011

Revised: May 31, 2013

Published: June 2014

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.