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

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.
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, (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. doi: 10.1137/S1052623494279110. Google Scholar

[3]

A. Fischer, A special Newton-type optimization method,, Optim., 24 (1992), 269. 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. 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. 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, (2004), 206. 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. 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, (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 (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. 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. doi: 10.1007/BF01580617. Google Scholar

[15]

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

[16]

L. Qi and J. sun, A nonsmooth version of Newton's method,, Math. Program., 58 (1993), 353. 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. 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. doi: 10.1016/j.jmaa.2004.10.032. Google Scholar

show all references

References:
[1]

D. P. Bertsekas, "Nonlinear Programming,", $2^{nd}$ edition, (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. doi: 10.1137/S1052623494279110. Google Scholar

[3]

A. Fischer, A special Newton-type optimization method,, Optim., 24 (1992), 269. 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. 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. 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, (2004), 206. 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. 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, (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 (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. 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. doi: 10.1007/BF01580617. Google Scholar

[15]

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

[16]

L. Qi and J. sun, A nonsmooth version of Newton's method,, Math. Program., 58 (1993), 353. 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. 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. 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]

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

[5]

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

[6]

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

[7]

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

[8]

Monica Conti, Vittorino Pata. On the regularity of global attractors. Discrete & Continuous Dynamical Systems - A, 2009, 25 (4) : 1209-1217. doi: 10.3934/dcds.2009.25.1209

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Chun-Hsiung Hsia, Chang-Yeol Jung, Bongsuk Kwon. On the global convergence of frequency synchronization for Kuramoto and Winfree oscillators. Discrete & Continuous Dynamical Systems - B, 2019, 24 (7) : 3319-3334. doi: 10.3934/dcdsb.2018322

[16]

Hugo Beirão da Veiga, Francesca Crispo. On the global regularity for nonlinear systems of the $p$-Laplacian type. Discrete & Continuous Dynamical Systems - S, 2013, 6 (5) : 1173-1191. doi: 10.3934/dcdss.2013.6.1173

[17]

Boqing Dong, Wenjuan Wang, Jiahong Wu, Hui Zhang. Global regularity results for the climate model with fractional dissipation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (1) : 211-229. doi: 10.3934/dcdsb.2018102

[18]

Qun Liu, Daqing Jiang, Ningzhong Shi, Tasawar Hayat, Ahmed Alsaedi. Stationarity and periodicity of positive solutions to stochastic SEIR epidemic models with distributed delay. Discrete & Continuous Dynamical Systems - B, 2017, 22 (6) : 2479-2500. doi: 10.3934/dcdsb.2017127

[19]

C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial & Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193

[20]

Binjie Li, Xiaoping Xie, Shiquan Zhang. New convergence analysis for assumed stress hybrid quadrilateral finite element method. Discrete & Continuous Dynamical Systems - B, 2017, 22 (7) : 2831-2856. doi: 10.3934/dcdsb.2017153

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]