Abstract
The elastic-mode formulation of the problem of minimizing a nonlinear function subject to equilibrium constraints has appealing local properties in that, for a finite value of the penalty parameter, local solutions satisfying first- and second-order necessary optimality conditions for the original problem are also first- and second-order points of the elastic-mode formulation. Here we study global convergence properties of methods based on this formulation, which involve generating an (exact or inexact) first- or second-order point of the formulation, for nondecreasing values of the penalty parameter. Under certain regularity conditions on the active constraints, we establish finite or asymptotic convergence to points having a certain stationarity property (such as strong stationarity, M-stationarity, or C-stationarity). Numerical experience with these approaches is discussed. In particular, our analysis and the numerical evidence show that exact complementarity can be achieved finitely even when the elastic-mode formulation is solved inexactly.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Anitescu M. (2005) On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15, 1203–1236
Anitescu M. (2005) Global convergence of an elastic mode approach for a class of mathematical programs with complementarity constraints. SIAM J. Optim. 16, 120–145
DeMiguel A., Friedlander M., Nogales F.J., Scholtes S.: An interior-point method for MPECs based on strictly feasible relaxations, Preprint ANL/MCS-P1150-0404, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, USA, Argonne, IL, USA (2004)
Fletcher R., Leyffer S. (2002) Nonlinear programming without a penalty function. Math. Program. Ser. A 91, 239–269
Fletcher R., Leyffer S.: Numerical experience with solving MPECs as NLPs, Report NA/210, University of Dundee (2002)
Fukushima M., Pang J.-S.: Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: Théra, M., Tichatschke R. (eds.) Ill-posed Variational Problems and Regularization Techniques, vol. 477 of Lecture Notes in Economics and Mathematical Systems, Springer, Berlin Heidelberg New York, pp. 99–110 (1999)
Fukushima M., Tseng P. (2002) 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
Gay D.M.: Hooking your solver to AMPL, technical report, Bell Laboratories. Murray Hill, NJ, 1993. Revised 1994, 1997
Hu X.M., Ralph D. (2004) Convergence of a penalty method for mathematical programming with complementarity constraints. J. Optim. Theory Appl. 123, 365–390
Jongen H.T., Jonker P., Twilt F. (1986) Critical sets in parametric optimization. Math. Program. 34, 333–353
Jongen H.T., Jonker P., Twilt F. (1986) One-parameter families of optimization problems: Equality constraints. J Optim. Theory Appl. 48, 141–161
Kocvara M., Outrata J. (2004) Optimization problems with equilibrium constraints and their numerical solution. Math. Program. 101, 119–149
Leyffer S.: MacMPEC AMPL collection of mathematical programs with equilibrium constraints
Lin G.H., Fukushima M. (2003) New relaxation method for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 118, 81–116
Liu X., Sun J. (2004) Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints. Math. Program. 101, 231–261
Luo Z.-Q., Pang J.-S., Ralph D.: Piecewise sequential quadratic programming for mathematical programs with nonlinear complementarity constraints. In: Migdalas A., Pardalos P., Värbrand P. (eds.) Multilevel Optimization: Algorithms, Complexity and Applications. Kluwer, Dordrecht, pp. 209–229 (1998)
Outrata J.(1999) Optimality conditions for a class of mathematical programs with equilibrium constraints. Math. Oper. Res. 24, 627–644
Outrata J., Kocvara M., Zowe J. (1998) Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications, and Numerical Results. Kluwer, Dordrecht
Overton M.L.: Numerical Computing with IEEE Floating-Point Arithmetic. SIAM (2001)
Ralph D., Wright S.J. (2004) Some properties of regularization and penalization schemes for MPECs. Optim. Methods Softw. 19, 527–556
Robinson S.M. (1982) Generalized equations and their solutions. Part II: Applications to nonlinear programming. Math. Program. Study 19, 200–221
Scheel H., Scholtes S. (2000) Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22
Scholtes S. (2001) Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936
Scholtes S., Stöhr M. (2001) How stringent is the linear independence assumption for mathematical programs with complementarity constraints? Math. Oper. Res. 26, 851–863
Author information
Authors and Affiliations
Corresponding author
Additional information
The submitted manuscript has been created by the University of Chicago as Operator of Argonne National Laboratory (“Argonne”) under Contract No. W-31-109-ENG-38 with the U.S. Department of Energy. The U.S. Government retains for itself, and others acting on its behalf, a paid-up, nonexclusive, irrevocable worldwide license in said article to reproduce, prepare derivative works, distribute copies to the public, and perform publicly and display publicly, by or on behalf of the Government.
Rights and permissions
About this article
Cite this article
Anitescu, M., Tseng, P. & Wright, S.J. Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties. Math. Program. 110, 337–371 (2007). https://doi.org/10.1007/s10107-006-0005-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0005-4
Keywords
- Nonlinear programming
- Equilibrium constraints
- Complementarity constraints
- Elastic-mode formulation
- Strong stationarity
- C-stationarity
- M-stationarity