Abstract
In this paper, we present new convergence results of augmented Lagrangian methods for mathematical programs with complementarity constraints (MPCC). Modified augmented Lagrangian methods based on four different algorithmic strategies are considered for the constrained nonconvex optimization reformulation of MPCC. We show that the convergence to a global optimal solution of the problem can be ensured without requiring the boundedness condition of the multipliers.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andreani R., Birgin E.G., Martínez J.M., Schuverdt M.L.: On augmented Lagrangian methods with general lower-level constraints. SIAM J. Optim. 18, 1286–1309 (2007)
Andreani R., Birgin E.G., Martínez J.M., Schuverdt M.L.: Augmented Lagrangian methods under the constant positive linear dependence constraint qualification. Math. Program. 111, 5–32 (2008)
Bertsekas D.P.: Constrained Optimization and Lagrangian Multiplier Methods. Academic Press, New York (1982)
Birgin E.G., Castillo R.A., Martínez J.M.: Numerical comparison of augmented Lagrangian algorithms for nonconvex problems. Comput. Optim. Appl. 31, 31–55 (2005)
Conn A.R., Gould N.I.M., Toint P.L.: A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds. SIAM J. Numer. Anal. 28, 545–572 (1991)
Di Pillo G., Lucidi S.: An augmented Lagrangian function with improved exactness properties. SIAM J. Optim. 12, 376–406 (2001)
Facchinei F., Jiang H., Qi L.: A smoothing method of mathematical programs with equilibrium constraints. Math. Program. 85, 107–134 (1999)
Fukushima M., Pang J.S.: Some feasibility issues in mathematical programs with equilibrium constraints. SIAM J. Optim. 8, 673–681 (1998)
Fukushima M., Tseng P.: An implementable active-set algorithm for computing a B-stationary point of a mathematical program with linear complementarity constraints. SIAM J. Optim. 12, 724–739 (2001)
Giannessi, F., Maugeri, A., Pardalos, P.M. (eds.): Equilibrium Problems and Variational Models. Kluwer, Dordrecht (2001)
Giannessi, F., Pardalos, P.M., Rapcsak, T. (eds.): New Trends in Equilibrium Systems. Kluwer, Dordrecht (2001)
Griva I., Polyak R.: A primal–dual nonlinear rescaling method with dynamic scaling parameter update. Math. Program. 106, 237–259 (2006)
Hu X.M., Ralph D.: Convergence of a penalty method for mathematical programming with complementarity constraints. J. Optim. Theory Appl. 123, 365–390 (2004)
Huang X.X., Yang X.Q., Teo K.L.: Partial augmented Lagrangian method and mathematical programs with complementarity constraints. J. Global Optim. 35, 235–254 (2006)
Kanzow C., Yamashita N., Fukushima M.: New NCP-functions and thier properties. J. Optim. Theory Appl. 94, 115–135 (1997)
Lewis R.M., Torczon V.: A globally convergent augmented Lagrangian pattern search algorithm for optimization with general constraints and simple bounds. SIAM J. Optim. 12, 1075–1089 (2002)
Luo, H.Z.: Studies on the Augmented Lagrangian Methods and Convexification Methods for Constrained Global Optimization. PhD thesis, Shanghai University (2007)
Luo H.Z., Sun X.L., Li D.: On the convergence of augmented Lagrangian methods for constrained global optimization. SIAM J. Optim. 18, 1209–1230 (2007)
Luo H.Z., Sun X.L., Wu H.X.: Convergence properties of augmented Lagrangian methods for constrained global optimization. Optim. Methods Softw. 23, 763–778 (2008)
Luo Z.Q., Pang J.S., Ralph D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
Mangasarian O.L.: Unconstrained Lagrangians in nonlinear programming. SIAM J. Control Optim. 13, 772–791 (1975)
Mangasarian O.L.: Equivalence of the complementarity problem to a system of nonlinear equations. SIAM Appl. Math. 31, 89–92 (1976)
Nguyen V.H., Strodiot J.J.: On the convergence rate of a penalty function method of exponential type. J. Optim. Theory Appl. 27, 495–508 (1979)
Pardalos P.M., Rosen J.B.: Global optimization approach to the linear complementarity problem. SIAM J. Sci. Stat. Comput. 9, 341–353 (1988)
Polyak R.: Modified barrier functions: theory and methods. Math. Program. 54, 177–222 (1992)
Polyak R.: Log-Sigmoid multipliers method in constrained optimization. Ann. Oper. Res. 101, 427–460 (2001)
Polyak R.: Nonlinear rescaling vs. smoothing technique in convex optimization. Math. Program. 92, 197–235 (2002)
Rockafellar R.T.: Lagrange multipliers and optimality. SIAM Rev. 35, 183–238 (1993)
Rockafellar R.T., Wets R.J.-B.: Variational Analysis. Springer, Berlin (1988)
Scheel H., Scholtes S.: Exact penalization of mathematical programs with equilibrium constraints. SIAM J. Control Optim. 37, 617–652 (1999)
Scholtes S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936 (2001)
Scholtes S., Stohr M.: Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity. Math. Oper. Res. 25, 1–22 (2000)
Sun X.L., Li D., McKinnon K.I.M.: On saddle points of augmented Lagrangians for constrained nonconvex optimization. SIAM J. Optim. 15, 1128–1146 (2005)
Tseng P., Bertsekas D.P.: On the convergence of the exponential multiplier method for convex programming. Math. Program. 60, 1–19 (1993)
Yang X.Q., Huang X.X.: Convergence analysis of an augmented Lagrangian methods for mathematical programs with complementarity constraints. Nonlinear Anal. 63, 2247–2256 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Luo, H.Z., Sun, X.L., Xu, Y.F. et al. On the convergence properties of modified augmented Lagrangian methods for mathematical programming with complementarity constraints. J Glob Optim 46, 217–232 (2010). https://doi.org/10.1007/s10898-009-9419-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-009-9419-x