# American Institute of Mathematical Sciences

• Previous Article
CVaR-based formulation and approximation method for stochastic variational inequalities
• NACO Home
• This Issue
• Next Article
Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions
2011, 1(1): 49-60. doi: 10.3934/naco.2011.1.49

## Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints

 1 University of Würzburg, Institute of Mathematics, Am Hubland, 97074 Würzburg, Germany, Germany, Germany

Received  September 2010 Revised  October 2010 Published  February 2011

We consider a regularization method for the numerical solution of mathematical programs with complementarity constraints (MPCC) introduced by Gui-Hua Lin and Masao Fukushima. Existing convergence results are improved in the sense that the MPCC-LICQ assumption is replaced by the weaker MPCC-MFCQ. Moreover, some preliminary numerical results are presented in order to illustrate the theoretical improvements.
Citation: Tim Hoheisel, Christian Kanzow, Alexandra Schwartz. Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 49-60. doi: 10.3934/naco.2011.1.49
##### References:
 [1] M. S. Bazaraa and C. M. Shetty, "Foundations of Optimization,'', Lecture Notes in Economics and Mathematical Systems, (1976). [2] Y. Chen and M. Florian, The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions,, Optimization, 32 (1995), 193. doi: 10.1080/02331939508844048. [3] A. V. Demiguel, M. P. Friedlander, F. J. Nogales and S. Scholtes, A two-sided relaxation scheme for mathematical programs with equilibrium constraints,, SIAM Journal on Optimization, 16 (2005), 587. doi: 10.1137/04060754x. [4] S. Dempe, "Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications,", 61 (2002), 61 (2002). [5] M. L. Flegel and C. Kanzow, On the Guignard constraint qualification for mathematical programs with equilibrium constraints,, Optimization, 54 (2005), 517. doi: 10.1080/02331930500342591. [6] M. L. Flegel and C. Kanzow, A direct proof for M-stationarity under MPEC-ACQ for mathematical programs with equilibrium constraints,, In, (2006), 111. doi: 10.1007/0-387-34221-4_6. [7] T. Hoheisel, C. Kanzow and A. Schwartz, Convergence of a local regularization approach for mathematical programs with complementarity or vanishing constraints,, Preprint 293, (2010). [8] T. Hoheisel, C. Kanzow and A. Schwartz, Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints,, Preprint 299, (2010). [9] A. Kadrani, J. P. Dussault and A. Benchakroun, A new regularization scheme for mathematical programs with complementarity constraints,, SIAM Journal on Optimization, 20 (2009), 78. doi: 10.1137/070705490. [10] C. Kanzow and A. Schwartz, A new regularization method for mathematical programs with complementarity constraints with strong convergence properties,, Preprint 296, (2010). [11] S. Leyffer, MacMPEC: AMPL collection of MPECs,, , (2000). [12] G. H. Lin and M. Fukushima, A modified relaxation scheme for mathematical programs with complementarity constraints,, Annals of Operations Research, 133 (2005), 63. doi: 10.1007/s10479-004-5024-z. [13] , www.netlib.org/ampl/solvers, /examples/amplfunc.c, (). [14] Z. Q. Luo, J. S. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints,'', Cambridge University Press, (1996). [15] O. L. Mangasarian, "Nonlinear Programming,'', McGraw-Hill, (1969). [16] J. V. Outrata, M. Kočvara and J. Zowe, "Nonsmooth Approach to Optimization Problems with Equilibrium Constraints,'', Nonconvex Optimization and its Applications, (1998). [17] L. Qi and Z. Wei, On the constant positive linear dependence condition and its applications to SQP methods,, SIAM Journal on Optimization, 10 (2000), 963. doi: 10.1137/S1052623497326629. [18] H. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity,, Mathematics of Operations Research, 25 (2000), 1. doi: 10.1287/moor.25.1.1.15213. [19] S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints,, SIAM Journal on Optimization, 11 (2001), 918. doi: 10.1137/S1052623499361233. [20] S. Steffensen and M. Ulbrich, A new relaxation scheme for mathematical programs with equilibrium constraints,, SIAM Journal on Optimization, 20 (2010), 2504. doi: 10.1137/090748883. [21] J. J. Ye, Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints,, SIAM Journal on Optimization, 10 (2000), 943. doi: 10.1137/S105262349834847X. [22] J. J. Ye and D. L. Zhu, Optimality conditions for bilevel programming problems,, Optimization, 33 (1995), 9. doi: 10.1080/02331939508844060.

show all references

##### References:
 [1] M. S. Bazaraa and C. M. Shetty, "Foundations of Optimization,'', Lecture Notes in Economics and Mathematical Systems, (1976). [2] Y. Chen and M. Florian, The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions,, Optimization, 32 (1995), 193. doi: 10.1080/02331939508844048. [3] A. V. Demiguel, M. P. Friedlander, F. J. Nogales and S. Scholtes, A two-sided relaxation scheme for mathematical programs with equilibrium constraints,, SIAM Journal on Optimization, 16 (2005), 587. doi: 10.1137/04060754x. [4] S. Dempe, "Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications,", 61 (2002), 61 (2002). [5] M. L. Flegel and C. Kanzow, On the Guignard constraint qualification for mathematical programs with equilibrium constraints,, Optimization, 54 (2005), 517. doi: 10.1080/02331930500342591. [6] M. L. Flegel and C. Kanzow, A direct proof for M-stationarity under MPEC-ACQ for mathematical programs with equilibrium constraints,, In, (2006), 111. doi: 10.1007/0-387-34221-4_6. [7] T. Hoheisel, C. Kanzow and A. Schwartz, Convergence of a local regularization approach for mathematical programs with complementarity or vanishing constraints,, Preprint 293, (2010). [8] T. Hoheisel, C. Kanzow and A. Schwartz, Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints,, Preprint 299, (2010). [9] A. Kadrani, J. P. Dussault and A. Benchakroun, A new regularization scheme for mathematical programs with complementarity constraints,, SIAM Journal on Optimization, 20 (2009), 78. doi: 10.1137/070705490. [10] C. Kanzow and A. Schwartz, A new regularization method for mathematical programs with complementarity constraints with strong convergence properties,, Preprint 296, (2010). [11] S. Leyffer, MacMPEC: AMPL collection of MPECs,, , (2000). [12] G. H. Lin and M. Fukushima, A modified relaxation scheme for mathematical programs with complementarity constraints,, Annals of Operations Research, 133 (2005), 63. doi: 10.1007/s10479-004-5024-z. [13] , www.netlib.org/ampl/solvers, /examples/amplfunc.c, (). [14] Z. Q. Luo, J. S. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints,'', Cambridge University Press, (1996). [15] O. L. Mangasarian, "Nonlinear Programming,'', McGraw-Hill, (1969). [16] J. V. Outrata, M. Kočvara and J. Zowe, "Nonsmooth Approach to Optimization Problems with Equilibrium Constraints,'', Nonconvex Optimization and its Applications, (1998). [17] L. Qi and Z. Wei, On the constant positive linear dependence condition and its applications to SQP methods,, SIAM Journal on Optimization, 10 (2000), 963. doi: 10.1137/S1052623497326629. [18] H. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity,, Mathematics of Operations Research, 25 (2000), 1. doi: 10.1287/moor.25.1.1.15213. [19] S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints,, SIAM Journal on Optimization, 11 (2001), 918. doi: 10.1137/S1052623499361233. [20] S. Steffensen and M. Ulbrich, A new relaxation scheme for mathematical programs with equilibrium constraints,, SIAM Journal on Optimization, 20 (2010), 2504. doi: 10.1137/090748883. [21] J. J. Ye, Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints,, SIAM Journal on Optimization, 10 (2000), 943. doi: 10.1137/S105262349834847X. [22] J. J. Ye and D. L. Zhu, Optimality conditions for bilevel programming problems,, Optimization, 33 (1995), 9. doi: 10.1080/02331939508844060.
 [1] Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086 [2] X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287 [3] Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153 [4] Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041 [5] Liping Pang, Na Xu, Jian Lv. The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints. Journal of Industrial & Management Optimization, 2019, 15 (1) : 59-79. doi: 10.3934/jimo.2018032 [6] Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial & Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99 [7] Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028 [8] Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951 [9] Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115 [10] 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 [11] Jie Zhang, Shuang Lin, Li-Wei Zhang. A log-exponential regularization method for a mathematical program with general vertical complementarity constraints. Journal of Industrial & Management Optimization, 2013, 9 (3) : 561-577. doi: 10.3934/jimo.2013.9.561 [12] Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064 [13] Liping Pang, Fanyun Meng, Jinhe Wang. Asymptotic convergence of stationary points of stochastic multiobjective programs with parametric variational inequality constraint via SAA approach. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-23. doi: 10.3934/jimo.2018116 [14] Adela Capătă. Optimality conditions for strong vector equilibrium problems under a weak constraint qualification. Journal of Industrial & Management Optimization, 2015, 11 (2) : 563-574. doi: 10.3934/jimo.2015.11.563 [15] Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030 [16] Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019044 [17] Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19 [18] Huijiang Zhao, Yinchuan Zhao. Convergence to strong nonlinear rarefaction waves for global smooth solutions of $p-$system with relaxation. Discrete & Continuous Dynamical Systems - A, 2003, 9 (5) : 1243-1262. doi: 10.3934/dcds.2003.9.1243 [19] 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 [20] 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

Impact Factor: