×

zbMATH — the first resource for mathematics

The price of inexactness: convergence properties of relaxation methods for mathematical programs with complementarity constraints revisited. (English) Zbl 1344.90058
Summary: Mathematical programs with equilibrium (or complementarity) constraints, MPECs for short, form a difficult class of optimization problems. The feasible set has a very special structure and violates most of the standard constraint qualifications. Therefore, one typically applies specialized algorithms in order to solve MPECs. One prominent class of specialized algorithms is the relaxation (or regularization) methods. The first relaxation method for MPECs is due to S. Scholtes [SIAM J. Optim. 11, No. 4, 918–936 (2001; Zbl 1010.90086)], but in the meantime, there exists a number of different regularization schemes that try to relax the difficult constraints in different ways. Some of these more recent schemes have better theoretical properties than does the original method by Scholtes. Nevertheless, numerical experience shows that the Scholtes relaxation method [loc. cit.] is still among the fastest and most reliable ones. To give a possible explanation for this, we consider that, numerically, the regularized subproblems are not solved exactly. In this light, we analyze the convergence properties of a number of relaxation schemes and study the impact of inexactly solved subproblems on the kind of stationarity we can expect in a limit point. Surprisingly, it turns out that the inexact version of Scholtes’ method has the same convergence properties as its exact counterpart, whereas most of the other relaxation schemes lose a lot of their original properties.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods
49M37 Numerical methods based on nonlinear programming
Software:
Ipopt; KNITRO; MacMPEC; SNOPT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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. CrossRef · Zbl 1099.65050
[2] Anitescu M (2005b) On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15:1203-1236. CrossRef · Zbl 1097.90050
[3] Bazaraa MS, Shetty CM (1976) Foundations of Optimization, Lecture Notes in Economics and Mathematical Systems (Springer, Berlin). CrossRef
[4] Byrd B, Hribar ME, Nocedal J (1999) An interior point method for large-scale nonlinear programming. SIAM J. Optim. 9:877-900. CrossRef · Zbl 0957.65057
[5] Byrd R, Nocedal J, Waltz RA (2006) KNITRO: An integrated package for nonlinear optimization. Pillo GD, Roma M, eds. Large-Scale Nonlinear Optimization (Springer, New York), 35-59. CrossRef · Zbl 1108.90004
[6] Demiguel V, Friedlander MP, Nogales FJ, Scholtes S (2005) A two-sided relaxation scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 16:587-609. CrossRef · Zbl 1122.90060
[7] Dempe S (2002) Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications, Vol. 61 (Kluwer Academic Publishers, Dordrecht, The Netherlands). · Zbl 1038.90097
[8] Dutta J, Deb K, Tulshyan R, Arora R (2013) Approximate KKT points and a proximity measure for termination. J. Global Optim. 56:1463-1499. CrossRef · Zbl 1297.90150
[9] Facchinei F, Jiang H, Qi L (1999) A smoothing method for mathematical programs with equilibrium constraints. Math. Programming 85:107-134. CrossRef · Zbl 0959.65079
[10] Flegel ML, Kanzow C (2005) Abadie-type constraint qualification for mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 124:595-614. CrossRef · Zbl 1090.90200
[11] Flegel ML, Kanzow C (2005) On the Guignard constraint qualification for mathematical programs with equilibrium constraints. Optimization 54:517-534. CrossRef · Zbl 1147.90397
[12] Fletcher R, Leyffer S (2002) Nonlinear programming without a penalty function. Math. Programming 91:239-269. CrossRef · Zbl 1049.90088
[13] Fletcher R, Leyffer S (2004) Solving mathematical programs with complementarity constraints as nonlinear programs. Optim. Methods Software 19:15-40. CrossRef · Zbl 1074.90044
[14] Gill PE, Murray W, Saunders MA (2002) SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM J. Optim. 12:979-1006. CrossRef · Zbl 1027.90111
[15] Hoheisel T, Kanzow C, Schwartz A (2011) Improved convergence properties of the Lin-Fukushima-regularization method for mathematical programs with complementarity constraints. Numerical Algebra, Control, Optim. 1:49-60. CrossRef · Zbl 1230.65067
[16] Hoheisel T, Kanzow C, Schwartz A (2012) Convergence of a local regularization approach for mathematical programs with complementarity or vanishing constraints. Optim. Methods Software 27:483-512. CrossRef · Zbl 1266.90170
[17] Hoheisel T, Kanzow C, Schwartz A (2013) Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. Math. Programming 137:257-288. CrossRef · Zbl 1262.65065
[18] Hu XM, Ralph D (2004) Convergence of a penalty method for mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 123:365-390. CrossRef
[19] Izmailov AF, Pogosyan AL, Solodov MV (2012) Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints. Computational Optim. Appl. 51:199-221. CrossRef · Zbl 1245.90124
[20] Kadrani A, Dussault J-P, Benchakroun A (2009) A new regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 20:78-103. CrossRef · Zbl 1187.65064
[21] Kanzow C, Schwartz A (2010) A new regularization method for mathematical programs with complementarity constraints with strong convergence properties. Technnical report, Institute of Mathematics, University of Würzburg, Würzburg, Germany. · Zbl 1282.65069
[22] Kanzow C, Schwartz A (2013) A new regularization method for mathematical programs with complementarity constraints with strong convergence properties. SIAM J. Optim. 23:770-798. CrossRef · Zbl 1282.65069
[23] Kanzow C, Schwartz A (2014) Convergence properties of the inexact Lin-Fukushima relaxation method for mathematical programs with equilibrium constraints. Computational Optim. Appl. 59(1-2):249-262CrossRef · Zbl 1326.90086
[24] Leyffer S, López-Calva G, Nocedal J (2007) Interior methods for mathematical programs with complementarity constraints. SIAM J. Optim. 17:52-77. CrossRef · Zbl 1112.90095
[25] Lin GH, Fukushima M (2005) A modified relaxation scheme for mathematical programs with complementarity constraints. Ann. Oper. Res. 133:63-84. CrossRef · Zbl 1119.90058
[26] Luo Z-Q, Pang J-S, Ralph D (1996) Mathematical Programs with Equilibrium Constraints (Cambridge University Press, Cambridge, UK). CrossRef
[27] Nocedal J, Wright SJ (2006) Numerical Optimization, Second ed. (Springer, New York).
[28] Outrata JV (1999) Optimality conditions for a class of mathematical programs with equilibrium constraints. Math. Oper. Res. 24:627-644. Abstract · Zbl 1039.90088
[29] Outrata JV (2000) A generalized mathematical program with equilibrium constraints. SIAM J. Control Optim. 38:1623-1638. CrossRef · Zbl 0968.49012
[30] Outrata JV, Kočvara M, Zowe J (1998) Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Nonconvex Optimization and Its Applications (Kluwer Academic Publishers, Dordrecht, the Netherlands). CrossRef
[31] Pang J-S, Fukushima M (1999) Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints. Computational Optim. Appl. 13:111-136. CrossRef · Zbl 1040.90560
[32] Raghunathan AU, Biegler LT (2005) An interior point method for mathematical programs with complementarity constraints (MPCCs). SIAM J. Optim. 15:720-750. CrossRef · Zbl 1077.90079
[33] Ralph D, Wright SJ (2004) Some properties of regularization and penalization schemes for MPECs. Optim. Methods Software 19:527-556. CrossRef · Zbl 1097.90054
[34] Scheel H, Scholtes S (2000) Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25:1-22. Abstract · Zbl 1073.90557
[35] Scholtes S (2001) Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11:918-936. CrossRef · Zbl 1010.90086
[36] Steffensen S, Ulbrich M (2010) A new regularization scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 20:2504-2539. CrossRef · Zbl 1231.90350
[37] Stein O (2012) Lifting mathematical programs with complementarity constraints. Math. Programming 131:71-94. CrossRef · Zbl 1250.90094
[38] Veelken S (2009) A new relaxation scheme for mathematical programs with equilibrium constraints: Theory and numerical experience. Ph.D. thesis, Technical University of Munich, Germany.
[39] Wächter A, Biegler LT (2006) On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Programming 106:25-57. CrossRef · Zbl 1134.90542
[40] Ye JJ (2000) Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints. SIAM J. Optim. 10:943-962. CrossRef · Zbl 1005.49019
[41] Ye JJ (2005) Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. J. Math. Anal. Appl. 307:350-369. CrossRef · Zbl 1112.90062
[42] Ye JJ, Ye XY (1997) Necessary optimality conditions for optimization problems with variational inequality constraints. Math. Oper. Res. 22:977-997. Abstract · Zbl 1088.90042
[43] Ye JJ, Zhu DL (1995) Optimality conditions for bilevel programming problems. Optimization 33:9-27. CrossRef · 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.