×

Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties. (English) Zbl 1119.90050

Authors’ summary: 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.

MSC:

90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods

Software:

AMPL; MacMPEC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anitescu M. (2005) On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15, 1203–1236 · Zbl 1097.90050 · doi:10.1137/S1052623402401221
[2] 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 · Zbl 1099.65050 · doi:10.1137/040606855
[3] 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)
[4] Fletcher R., Leyffer S. (2002) Nonlinear programming without a penalty function. Math. Program. Ser. A 91, 239–269 · Zbl 1049.90088 · doi:10.1007/s101070100244
[5] Fletcher R., Leyffer S.: Numerical experience with solving MPECs as NLPs, Report NA/210, University of Dundee (2002)
[6] 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) · Zbl 0944.65070
[7] 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 · Zbl 1005.65064 · doi:10.1137/S1052623499363232
[8] Gay D.M.: Hooking your solver to AMPL, technical report, Bell Laboratories. Murray Hill, NJ, 1993. Revised 1994, 1997
[9] Hu X.M., Ralph D. (2004) Convergence of a penalty method for mathematical programming with complementarity constraints. J. Optim. Theory Appl. 123, 365–390 · doi:10.1007/s10957-004-5154-0
[10] Jongen H.T., Jonker P., Twilt F. (1986) Critical sets in parametric optimization. Math. Program. 34, 333–353 · Zbl 0599.90114 · doi:10.1007/BF01582234
[11] Jongen H.T., Jonker P., Twilt F. (1986) One-parameter families of optimization problems: Equality constraints. J Optim. Theory Appl. 48, 141–161 · Zbl 0556.90086
[12] Kocvara M., Outrata J. (2004) Optimization problems with equilibrium constraints and their numerical solution. Math. Program. 101, 119–149 · Zbl 1076.90058 · doi:10.1007/s10107-004-0539-2
[13] Leyffer S.: MacMPEC AMPL collection of mathematical programs with equilibrium constraints
[14] Lin G.H., Fukushima M. (2003) New relaxation method for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 118, 81–116 · Zbl 1033.90086 · doi:10.1023/A:1024739508603
[15] Liu X., Sun J. (2004) Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints. Math. Program. 101, 231–261 · Zbl 1076.90059 · doi:10.1007/s10107-004-0543-6
[16] 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) · Zbl 0897.90184
[17] Outrata J.(1999) Optimality conditions for a class of mathematical programs with equilibrium constraints. Math. Oper. Res. 24, 627–644 · Zbl 1039.90088 · doi:10.1287/moor.24.3.627
[18] Outrata J., Kocvara M., Zowe J. (1998) Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications, and Numerical Results. Kluwer, Dordrecht · Zbl 0947.90093
[19] Overton M.L.: Numerical Computing with IEEE Floating-Point Arithmetic. SIAM (2001) · Zbl 0981.68057
[20] Ralph D., Wright S.J. (2004) Some properties of regularization and penalization schemes for MPECs. Optim. Methods Softw. 19, 527–556 · Zbl 1097.90054 · doi:10.1080/10556780410001709439
[21] Robinson S.M. (1982) Generalized equations and their solutions. Part II: Applications to nonlinear programming. Math. Program. Study 19, 200–221 · Zbl 0495.90077
[22] Scheel H., Scholtes S. (2000) Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22 · Zbl 1073.90557 · doi:10.1287/moor.25.1.1.15213
[23] Scholtes S. (2001) Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936 · Zbl 1010.90086 · doi:10.1137/S1052623499361233
[24] 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 · Zbl 1082.90580 · doi:10.1287/moor.26.4.851.10007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.