×

zbMATH — the first resource for mathematics

Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. (English) Zbl 1262.65065
The authors deal with convergence properties of five relaxation methods for solving mathematical programs with equilibrium constraints (MPECs). Several existed convergence results are improved and some new results regarding the satisfaction of standard constraint qualifications for the relaxed problems are obtained. They present a numerical comparison of these methods based on the MacMPEC test problem collection. Numerical results favour the oldest relaxation scheme due to Scholtes.

MSC:
65K05 Numerical mathematical programming methods
Software:
MacMPEC
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anitescu M.: On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15, 1203–1236 (2005) · Zbl 1097.90050
[2] Anitescu M.: Global convergence of an elastic mode approach for a class of mathematical programs with complementarity constraints. SIAM J. Optim. 16, 120–145 (2005) · Zbl 1099.65050
[3] Andreani R., Martínez J.M., Schuverdt M.L.: The CPLD condition of Qi and Wei implies the quasinormality constraint qualification. J. Optim. Theory Appl. 125, 473–485 (2005) · Zbl 1125.90058
[4] Bazaraa M.S., Shetty C.M.: Foundations of Optimization (Lecture Notes in Economics and Mathematical Systems). Springer, Berlin (1976) · Zbl 0334.90049
[5] Benson H.Y., Shanno D.F., Vanderbei R.J.: Interior point methods for nonconvex nonlinear programming: complementarity constraints. Technical Report ORFE-02-02. Operations Research and Financial Engineering. Princeton University, Princeton (2002) · Zbl 1022.90017
[6] Bertsekas D.P., Ozdaglar A.E.: Pseudonormality and a Lagrange multiplier theory for constrained optimization. J. Optim. Theory Appl. 114, 187–343 (2002) · Zbl 1026.90092
[7] Demiguel A.V., Friedlander M.P., Nogales F.J., Scholtes S.: A two-sided relaxation scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 16, 587–609 (2005) · Zbl 1122.90060
[8] Dempe S.: Foundations of Bilevel Programming. Nonconvex Optimization and Its Applications. vol. 61. Kluwer, Dordrecht (2002) · Zbl 1038.90097
[9] Dolan E.D., Moré J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004
[10] Facchinei F., Jiang H., Qi L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85, 107–134 (1999) · Zbl 0959.65079
[11] Flegel M.L., Kanzow C.: On the Guignard constraint qualification for mathematical programs with equilibrium constraints. Optimization 54, 517–534 (2005) · Zbl 1147.90397
[12] Flegel M.L., Kanzow C.: Abadie-type constraint qualification for mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 124, 595–614 (2005) · Zbl 1090.90200
[13] Flegel M.L., Kanzow C.: A direct proof for M-stationarity under MPEC-GCQ for mathematical programs with equilibrium constraints. In: Dempe, S., Kalashnikov, V. (eds) Optimization with Multivalued Mappings: Theory, Applications and Algorithms, pp. 111–122. Springer, New York (2006) · Zbl 1125.90062
[14] Fletcher R., Leyffer S.: Solving mathematical programs with complementarity constraints as nonlinear programs. Optim. Methods Softw. 19, 15–40 (2004) · Zbl 1074.90044
[15] Guignard M.: Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space. SIAM J. Control 7, 232–241 (1969) · Zbl 0182.53101
[16] Hoheisel, T., Kanzow, C., Schwartz, A.: Convergence of a local regularization approach for mathematical programs with complementarity or vanishing constraints. Optim. Methods Softw. (to appear) · Zbl 1266.90170
[17] Hoheisel, T., Kanzow, C., Schwartz, A.: Improved convergence properties of the Lin-Fukushima-regularization method for mathematical programs with complementarity constraints. Numer Algebra Control Optim. (to appear) · Zbl 1230.65067
[18] Hu X.M., Ralph D.: Convergence of a penalty method for mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 123, 365–390 (2004)
[19] Izmailov, A.F., Pogosyan, A.L., Solodov, M.V.: Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints. Optim. Methods Softw. (to appear) · Zbl 1245.90124
[20] Janin R.: Directional derivative of the marginal function in nonlinear programming. Math. Program. Study 21, 110–126 (1984) · Zbl 0549.90082
[21] Kadrani A., Dussault J.-P., Benchakroun A.: A new regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 20, 78–103 (2009) · Zbl 1187.65064
[22] Kanzow C., Schwartz A.: A new regularization method for mathematical programs with complementarity constraints with strong convergence properties. Preprint 296, Institute of Mathematics. University of Würzburg, Würzburg (2010) · Zbl 1282.65069
[23] Leyffer, S.: MacMPEC: AMPL collection of MPECs. http://www.mcs.anl.go/\(\sim\)leyffer/MacMPEC (2000)
[24] Leyffer S., López-Calva G., Nocedal J.: Interior methods for mathematical programs with complementarity constraints. SIAM J. Optim. 17, 52–77 (2007) · Zbl 1112.90095
[25] Lin G.H., Fukushima M.: A modified relaxation scheme for mathematical programs with complementarity constraints. Ann. Oper. Res. 133, 63–84 (2005) · Zbl 1119.90058
[26] Luo Z.-Q., Pang J.-S., Ralph D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
[27] Outrata J.V., Kočvara M., Zowe J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Nonconvex Optimization and its Applications. Kluwer, Dordrecht (1998) · Zbl 0947.90093
[28] Qi L., Wei Z.: On the constant positive linear dependence condition and its applications to SQP methods. SIAM J. Optim. 10, 963–981 (2000) · Zbl 0999.90037
[29] Raghunathan A.U., Biegler L.T.: An interior point method for mathematical programs with complementarity constraints (MPCCs). SIAM J. Optim. 15, 720–750 (2005) · Zbl 1077.90079
[30] Ralph D., Wright S.J.: Some properties of regularization and penalization schemes for MPECs. Optim. Methods Softw. 19, 527–556 (2004) · Zbl 1097.90054
[31] Scheel H., Scholtes S.: Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22 (2000) · Zbl 1073.90557
[32] Scholtes S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936 (2001) · Zbl 1010.90086
[33] Steffensen S., Ulbrich M.: A new relaxation scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 20, 2504–2539 (2010) · Zbl 1231.90350
[34] Stein, O.: Lifting mathematical programs with complementarity constraints. Math. Program. (to appear) · Zbl 1250.90094
[35] www.netlib.org/ampl/solvers/examples/amplfunc.c
[36] Ye J.J., Zhu D.L.: Optimality conditions for bilevel programming problems. Optimization 33, 9–27 (1995) · Zbl 0820.65032
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.