# 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:
KNITRO; Ipopt; SNOPT; MacMPEC
Full Text:
##### References:
  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  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  Bazaraa MS, Shetty CM (1976) Foundations of Optimization, Lecture Notes in Economics and Mathematical Systems (Springer, Berlin). CrossRef  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  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  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  Dempe S (2002) Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications, Vol. 61 (Kluwer Academic Publishers, Dordrecht, The Netherlands). · Zbl 1038.90097  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  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  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  Flegel ML, Kanzow C (2005) On the Guignard constraint qualification for mathematical programs with equilibrium constraints. Optimization 54:517-534. CrossRef · Zbl 1147.90397  Fletcher R, Leyffer S (2002) Nonlinear programming without a penalty function. Math. Programming 91:239-269. CrossRef · Zbl 1049.90088  Fletcher R, Leyffer S (2004) Solving mathematical programs with complementarity constraints as nonlinear programs. Optim. Methods Software 19:15-40. CrossRef · Zbl 1074.90044  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  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  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  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  Hu XM, Ralph D (2004) Convergence of a penalty method for mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 123:365-390. CrossRef  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  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  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  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  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  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  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  Luo Z-Q, Pang J-S, Ralph D (1996) Mathematical Programs with Equilibrium Constraints (Cambridge University Press, Cambridge, UK). CrossRef  Nocedal J, Wright SJ (2006) Numerical Optimization, Second ed. (Springer, New York).  Outrata JV (1999) Optimality conditions for a class of mathematical programs with equilibrium constraints. Math. Oper. Res. 24:627-644. Abstract · Zbl 1039.90088  Outrata JV (2000) A generalized mathematical program with equilibrium constraints. SIAM J. Control Optim. 38:1623-1638. CrossRef · Zbl 0968.49012  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  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  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  Ralph D, Wright SJ (2004) Some properties of regularization and penalization schemes for MPECs. Optim. Methods Software 19:527-556. CrossRef · Zbl 1097.90054  Scheel H, Scholtes S (2000) Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25:1-22. Abstract · Zbl 1073.90557  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  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  Stein O (2012) Lifting mathematical programs with complementarity constraints. Math. Programming 131:71-94. CrossRef · Zbl 1250.90094  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.  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  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  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  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  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.