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

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

April 2013, 9(2): 305-322. doi: 10.3934/jimo.2013.9.305

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, China
2.	School of Management, Shanghai University, Shanghai 200444, China

Received January 2012 Revised May 2012 Published February 2013

Abstract
Related Papers

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: Levenberg-Marquardt method, global convergence., MPCC, MPCC-stationarity, regularity.

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

Citation: Lei Guo, Gui-Hua Lin. Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations. Journal of Industrial and Management Optimization, 2013, 9 (2) : 305-322. doi: 10.3934/jimo.2013.9.305

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:, , ().
[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.

show all references

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:, , ().
[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.

[1]	Liyan Qi, Xiantao Xiao, Liwei Zhang. On the global convergence of a parameter-adjusting Levenberg-Marquardt method. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 25-36. doi: 10.3934/naco.2015.5.25
[2]	Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial and Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199
[3]	Jinyan Fan, Jianyu Pan. Inexact Levenberg-Marquardt method for nonlinear equations. Discrete and Continuous Dynamical Systems - B, 2004, 4 (4) : 1223-1232. doi: 10.3934/dcdsb.2004.4.1223
[4]	Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068
[5]	Xin-He Miao, Kai Yao, Ching-Yu Yang, Jein-Shan Chen. Levenberg-Marquardt method for absolute value equation associated with second-order cone. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 47-61. doi: 10.3934/naco.2021050
[6]	Jinyan Fan. On the Levenberg-Marquardt methods for convex constrained nonlinear equations. Journal of Industrial and Management Optimization, 2013, 9 (1) : 227-241. doi: 10.3934/jimo.2013.9.227
[7]	Johann Baumeister, Barbara Kaltenbacher, Antonio Leitão. On Levenberg-Marquardt-Kaczmarz iterative methods for solving systems of nonlinear ill-posed equations. Inverse Problems and Imaging, 2010, 4 (3) : 335-350. doi: 10.3934/ipi.2010.4.335
[8]	Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013
[9]	Gonglin Yuan, Zhan Wang, Pengyuan Li. Global convergence of a modified Broyden family method for nonconvex functions. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021164
[10]	Yuhua Zhu. A local sensitivity and regularity analysis for the Vlasov-Poisson-Fokker-Planck system with multi-dimensional uncertainty and the spectral convergence of the stochastic Galerkin method. Networks and Heterogeneous Media, 2019, 14 (4) : 677-707. doi: 10.3934/nhm.2019027
[11]	Nora Merabet. Global convergence of a memory gradient method with closed-form step size formula. Conference Publications, 2007, 2007 (Special) : 721-730. doi: 10.3934/proc.2007.2007.721
[12]	Monica Conti, Vittorino Pata. On the regularity of global attractors. Discrete and Continuous Dynamical Systems, 2009, 25 (4) : 1209-1217. doi: 10.3934/dcds.2009.25.1209
[13]	Wilhelm Schlag. Regularity and convergence rates for the Lyapunov exponents of linear cocycles. Journal of Modern Dynamics, 2013, 7 (4) : 619-637. doi: 10.3934/jmd.2013.7.619
[14]	Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems and Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033
[15]	Karl Kunisch, Markus Müller. Uniform convergence of the POD method and applications to optimal control. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4477-4501. doi: 10.3934/dcds.2015.35.4477
[16]	Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial and Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381
[17]	Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic and Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1
[18]	Yong Duan, Jian-Guo Liu. Convergence analysis of the vortex blob method for the $b$-equation. Discrete and Continuous Dynamical Systems, 2014, 34 (5) : 1995-2011. doi: 10.3934/dcds.2014.34.1995
[19]	Jiequn Han, Jihao Long. Convergence of the deep BSDE method for coupled FBSDEs. Probability, Uncertainty and Quantitative Risk, 2020, 5 (0) : 5-. doi: 10.1186/s41546-020-00047-w
[20]	Jahnabi Chakravarty, Ashiho Athikho, Manideepa Saha. Convergence of interval AOR method for linear interval equations. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 293-308. doi: 10.3934/naco.2021006

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Lei Guo Gui-Hua Lin
on Google Scholar
Lei Guo Gui-Hua Lin

[Back to Top]