Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 90C25, 90C30; Secondary: 49J52, 49M27, 49M37.

 Citation:

•  [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.