Globally convergent algorithm for solving stationary points formathematical programs with complementarity constraints via nonsmoothreformulations

Lei Guo; Gui-Hua Lin

doi:10.3934/jimo.2013.9.305

Article Contents

2013, Volume 9, Issue 2: 305-322. Doi: 10.3934/jimo.2013.9.305

This issue Previous Article Analysis on Buyers' cooperative strategy under group-buying price mechanism Next Article Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration

Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations

Lei Guo^1, and
Gui-Hua Lin^2,

1.
School of Mathematical Sciences, Dalian University of Technology, Dalian 116024
2.
School of Management, Shanghai University, Shanghai 200444

Received: December 31, 2011

Revised: April 30, 2012

Published: March 2013

Abstract Related Papers Cited by

Abstract

The purpose of the paper is to develop globally convergent algorithms for solving the popular stationarity systems for mathematical programs with complementarity constraints (MPCC) directly. Since the popular stationarity systems for MPCC contain some unknown index sets, we first present some nonsmooth reformulations for the stationarity systems by removing the unknown index sets and then we propose a Levenberg-Marquardt type method to solve them. Under some regularity conditions, we show that the proposed method is globally and superlinearly convergent. We further report some preliminary numerical results.

Keywords:

Mathematics Subject Classification: Primary: 90C30; Secondary: 90C33.

Citation:

Related Papers

Cited by

References

[1]	D. P. Bertsekas, "Nonlinear Programming," $2^{nd}$ edition, Athena Scientific, Belmont, Massachusetts, 1999.
[2]	F. Facchinei and J. Soares, A new merit function for nonlinear complementarity problems and a related algorithm, SIAM J. Optim., 7 (1997), 225-247.doi: 10.1137/S1052623494279110.
[3]	A. Fischer, A special Newton-type optimization method, Optim., 24 (1992), 269-284.doi: 10.1080/02331939208843795.
[4]	M. L. Flegel and C. Kanzow, Abadie-type constraint qualification for mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 124 (2005), 595-614.doi: 10.1007/s10957-004-1176-x.
[5]	R. Fletcher, S. Leyffer, D. Ralph and S. Scholtes, Local convergence of SQP methods for mathematical programs with equilibrium constraints, SIAM J. Optim., 17 (2006), 259-286.doi: 10.1137/S1052623402407382.
[6]	M. Fukushima and G.-H. Lin, Smoothing methods for mathematical programs with equilibrium constraints, Proceedings of the ICKS'04, IEEE Computer Society, (2004), 206-213.
[7]	L. Guo and G.-H. Lin, Notes on some constraint qualifications for mathematical programs with equilibrium constraints, J. Optim. Theory Appl., (2012).doi: 10.1007/s10957-012-0084-8.
[8]	S. Leyffer, MacMPEC-ampl collection of mathematical programms with equilibrium constraints. Available from: http://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC.
[9]	G.-H. Lin, L. Guo and J.-J. Ye, Solving mathematical programs with equilibrium constraints as constrained equations, preprint.
[10]	T. De Luca, F. Facchinei and C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Program., 75 (1996), 407-439.doi: 10.1016/S0025-5610(96)00028-7.
[11]	Z.-Q. Luo, J.-S. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints," Cambridge University Press, Cambridge, 1996.doi: 10.1017/CBO9780511983658.
[12]	J. V. Outrata, M. Kočvara and J. Zowe, "Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Theory, Applications and Numerical Results," Nonconvex Optimization and its Applications, 28, Kluwer Academic Publishers, Dordrecht, 1998.
[13]	J.-S. Pang, A B-differentiable equation-baesd, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems, Math. Program., 51 (1991), 101-131.doi: 10.1007/BF01586928.
[14]	J.-S. Pang and A. Gabriel, NE/SQP: A robust algorithm for the nonlinear complementarity problem, Math. Program., 60 (1993), 295-337.doi: 10.1007/BF01580617.
[15]	J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithm, SIAM J. Optim., 3 (1993), 443-465.doi: 10.1137/0803021.
[16]	L. Qi and J. sun, A nonsmooth version of Newton's method, Math. Program., 58 (1993), 353-367.doi: 10.1007/BF01581275.
[17]	P. Tseng, Growth behavior of a class of merit functions for the nonlinear complementarity problem, J. Optim. Theory Appl., 89 (1996), 17-37.doi: 10.1007/BF02192639.
[18]	J. J. Ye, Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints, J. Math. Anal. Appl., 307 (2005), 350-369.doi: 10.1016/j.jmaa.2004.10.032.