American Institute of Mathematical Sciences

Advanced
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

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 & 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. Google Scholar

[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.  Google Scholar

[3]

A. Fischer, A special Newton-type optimization method, Optim., 24 (1992), 269-284. doi: 10.1080/02331939208843795.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[8]

S. Leyffer, MacMPEC-ampl collection of mathematical programms with equilibrium constraints. Available from:, , ().   Google Scholar

[9]

G.-H. Lin, L. Guo and J.-J. Ye, Solving mathematical programs with equilibrium constraints as constrained equations,, preprint., ().   Google Scholar

[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.  Google Scholar

[11]

Z.-Q. Luo, J.-S. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints," Cambridge University Press, Cambridge, 1996. doi: 10.1017/CBO9780511983658.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithm, SIAM J. Optim., 3 (1993), 443-465. doi: 10.1137/0803021.  Google Scholar

[16]

L. Qi and J. sun, A nonsmooth version of Newton's method, Math. Program., 58 (1993), 353-367. doi: 10.1007/BF01581275.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

D. P. Bertsekas, "Nonlinear Programming," $2^{nd}$ edition, Athena Scientific, Belmont, Massachusetts, 1999. Google Scholar

[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.  Google Scholar

[3]

A. Fischer, A special Newton-type optimization method, Optim., 24 (1992), 269-284. doi: 10.1080/02331939208843795.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[8]

S. Leyffer, MacMPEC-ampl collection of mathematical programms with equilibrium constraints. Available from:, , ().   Google Scholar

[9]

G.-H. Lin, L. Guo and J.-J. Ye, Solving mathematical programs with equilibrium constraints as constrained equations,, preprint., ().   Google Scholar

[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.  Google Scholar

[11]

Z.-Q. Luo, J.-S. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints," Cambridge University Press, Cambridge, 1996. doi: 10.1017/CBO9780511983658.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithm, SIAM J. Optim., 3 (1993), 443-465. doi: 10.1137/0803021.  Google Scholar

[16]

L. Qi and J. sun, A nonsmooth version of Newton's method, Math. Program., 58 (1993), 353-367. doi: 10.1007/BF01581275.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Liyan Qi, Xiantao Xiao, Liwei Zhang. On the global convergence of a parameter-adjusting Levenberg-Marquardt method. Numerical Algebra, Control & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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]

Jahnabi Chakravarty, Ashiho Athikho, Manideepa Saha. Convergence of interval AOR method for linear interval equations. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021006
[15]

Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033
[16]

Karl Kunisch, Markus Müller. Uniform convergence of the POD method and applications to optimal control. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4477-4501. doi: 10.3934/dcds.2015.35.4477
[17]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381
[18]

Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic & Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1
[19]

Yong Duan, Jian-Guo Liu. Convergence analysis of the vortex blob method for the $b$-equation. Discrete & Continuous Dynamical Systems, 2014, 34 (5) : 1995-2011. doi: 10.3934/dcds.2014.34.1995
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (59)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy