×

zbMATH — the first resource for mathematics

A globally convergent algorithm for MPCC. (English) Zbl 1326.49050
Summary: We propose a penalty formulation based on the new regularization scheme for Mathematical Programs with Complementarity Constraints (MPCCs). We present an active set method which solves a sequence of penalty-regularized problems. We study global convergence properties of the method under the MPCC-linear independence constraint qualification. In particular, any accumulation point of the generated iterates is a strong stationary point if the penalty parameter is bounded. Otherwise, the convergence to points having a certain stationarity property is established. A strategy for updating the penalty parameter is proposed and numerical results on a collection of test problems are reported.

MSC:
49M37 Numerical methods based on nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C30 Nonlinear programming
90C52 Methods of reduced gradient type
65K05 Numerical mathematical programming methods
Software:
AMPL; MacMPEC; Scilab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anitescu, M, On using the elastic mode in nonlinear programming approaches to mathematical programming 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] Byrd RH, Shultz GA (1982) A practical class of globally-convergent active set strategies for linearly-constrained optimization, research report CU-CS-238-82. Computer Science Department, University of Colorado at Boulder · Zbl 1127.65034
[4] Dembo RS, Sahi S (1983) A Convergence framework for Constrained Nonlinear Optimization, School of Organization and Management Working paper, Series B #69, Yale University, New Haven, Connecticut · Zbl 1122.90060
[5] Demiguel, AV; Friedlander, MP; Nogales, FJ; Scholtes, S, A two-sided relaxation scheme for mathematical programs with equilibrium constraints, SIAM J Optim, 16, 587-609, (2005) · Zbl 1122.90060
[6] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math Progr, 91A, 201-213, (2002) · Zbl 1049.90004
[7] Facchinei, F; Jiang, H; Qi, L, A smoothing method for mathematical programming with equilibrium constraints, Math Progr, 85, 107-134, (1999) · Zbl 0959.65079
[8] Fletcher R (1981) Practical methods of optimization, vol 2. Wiley, New York · Zbl 0474.65043
[9] Fletcher R, Leyffer S (2002) Numerical experience with solving MPECs as NLPs, Report NA/210, University of Dundee
[10] Fletcher, R; Leyffer, S; Ralph, D; Scholtes, S, Local convergence of SQP methods for mathematical programs with equilibrium constraints, SIAM J Optim, 17, 259-286, (2006) · Zbl 1112.90098
[11] Fukushima M, Pang JS (1999) Convergence of a smoothing continuation method for mathematical programming with complementarity constraints Ill-posed variational problems and regularization technique. In: Théra M, Tichatschke R (eds) Lecture Notes in Economics and Mathematical Systems, vol. 477. Springer, Berlin/Heidelberg, pp 99-110 · Zbl 1099.65050
[12] Fukushima, M; Tseng, P, An implementable active-set algorithm for computing a B-stationary point of a mathematical programming with complementarity constraints, SIAM J Optim, 12, 724-739, (2002) · Zbl 1005.65064
[13] Fukushima, M; Tseng, P, An implementable active-set algorithm for computing a B-stationary point of a mathematical programming with complementarity constraints, Erratum SIAM J Optim, 17, 1253-1257, (2007) · Zbl 1127.65034
[14] Gill PE, Murray W (1974) Numerical methods in constrained optimization. Academic Press, New York
[15] Hu, X; Ralph, D, Convergence of a penalty method for mathematical programming with equilibrium constraints, J Optim Theory Appl, 123, 365-390, (2004)
[16] Huang, XX; Yang, XQ; Zhu, DL, A sequential smooth penalization approach to mathematical programming with complementarity constraints, Numer Funct Anal Optim, 27, 71-98, (2006) · Zbl 1119.90051
[17] Kadrani, A; Dussault, JP; Benchakroun, A, A new regularization scheme for mathematical programming with complementarity constraints, SIAM J Optim, 20, 78-103, (2009) · Zbl 1187.65064
[18] Leyffer S (2000) MacMPEC: AMPL Collection of MPECs. http://www.mcs.anl.gov/ leyffer/MacMPEC/
[19] Leyffer, S; Lopez-Calva, G; Nocedal, J, Interior methods for mathematical programming with equilibrium constraints, SIAM J Optim, 17, 52-77, (2006) · Zbl 1112.90095
[20] Lin, GH; Fukushima, M, A modified relaxation scheme for mathematical programs with complementarity constraints, Ann Oper Res, 133, 63-84, (2005) · Zbl 1119.90058
[21] Liu, X; Sun, J, Generalized stationary points and an interior point method for mathematical programs with equilibrium constraints, Math Progr, 101, 231-261, (2004) · Zbl 1076.90059
[22] Luo ZQ, Pang JS, Ralph D (1998) Piecewise sequential quadratic programming for mathematical programs with complementarity constraints. In: Migdalas A, Pardalos PM, Varbrant P (eds). Kluwer Academic Publishers, Dordrecht, pp 209-299 · Zbl 1073.90557
[23] Nocedal J, Wright SJ (2006) Numerical optimization. Springer, New York · Zbl 1104.65059
[24] Raghunathan, A; Biegler, LT, An interior point method for mathematical programs with complementarity constraints (MPCCs), SIAM J Optim, 15, 720-750, (2005) · Zbl 1077.90079
[25] Ralph, D; Wright, SJ, Some properties of regularization and penalization schemes for mpecs, Optim Methods Softw, 19, 527-556, (2004) · Zbl 1097.90054
[26] Scheel, H; Scholtes, S, Mathematical programming with complementarity constraints: stationarity, optimality and sensitivity, Math Oper Res, 25, 1-22, (2000) · Zbl 1073.90557
[27] Scholtes, S, Convergence properties of a regularization scheme for mathematical programming with complementarity constraints, SIAM J Optim, 11, 918-936, (2001) · Zbl 1010.90086
[28] Scholtes, S; Stohr, M, Exact penalization for mathematical programming with equilibrium constraints, SIAM J Control Optim, 37, 617-652, (1997) · Zbl 0922.90128
[29] Scilab group (2008) Scilab 4.1.2. http://www.scilab.org · Zbl 0959.65079
[30] Wolfe P (1967) On the Convergence of the Gradient Methods Under Constraint, Research Report RC1752. IBM Watson Research Center, Yorktown
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.