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, (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]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[2]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597
[3]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[4]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[5]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053
[6]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[7]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[8]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[9]

Philippe G. Lefloch, Cristinel Mardare, Sorin Mardare. Isometric immersions into the Minkowski spacetime for Lorentzian manifolds with limited regularity. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 341-365. doi: 10.3934/dcds.2009.23.341
[10]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[11]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397
[12]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[13]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206
[14]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044
[15]

Hyeong-Ohk Bae, Hyoungsuk So, Yeonghun Youn. Interior regularity to the steady incompressible shear thinning fluids with non-Standard growth. Networks & Heterogeneous Media, 2018, 13 (3) : 479-491. doi: 10.3934/nhm.2018021
[16]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[17]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065
[18]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213
[19]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210
[20]

Ying Yang. Global classical solutions to two-dimensional chemotaxis-shallow water system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2625-2643. doi: 10.3934/dcdsb.2020198

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences