• Previous Article
    Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions
  • NACO Home
  • This Issue
  • Next Article
    CVaR-based formulation and approximation method for stochastic variational inequalities
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 and 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, Springer-Verlag, Berlin/Heidelberg, 1976.

[2]

Y. Chen and M. Florian, The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions, Optimization, 32 (1995), 193-209. 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-609. doi: 10.1137/04060754x.

[4]

S. Dempe, "Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications," 61 (2002), Kluwer Academic Publishers, Dordrecht, The Netherlands .

[5]

M. L. Flegel and C. Kanzow, On the Guignard constraint qualification for mathematical programs with equilibrium constraints, Optimization, 54 (2005), 517-534. 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 "Optimization with Multivalued Mappings: Theory, Applications and Algorithms''(eds. S. Dempe and V. Kalashnikov), Springer-Verlag, New York, 2006, 111-122. 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, Institute of Mathematics, University of Würzburg, Würzburg, February 2010.

[8]

T. Hoheisel, C. Kanzow and A. Schwartz, Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Preprint 299, Institute of Mathematics, University of Würzburg, Würzburg, September 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-103. 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, Institute of Mathematics, University of Würzburg, Würzburg, June 2010.

[11]

S. Leyffer, MacMPEC: AMPL collection of MPECs, www.mcs.anl.go/~leyffer/MacMPEC, 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-84. 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, Cambridge, New York, Melbourne, 1996.

[15]

O. L. Mangasarian, "Nonlinear Programming,'' McGraw-Hill, New York, NY, 1969 (reprinted by SIAM, Philadelphia, PA, 1994).

[16]

J. V. Outrata, M. Kočvara and J. Zowe, "Nonsmooth Approach to Optimization Problems with Equilibrium Constraints,'' Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 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-981. 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-22. 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-936. 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-2539. 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-962. doi: 10.1137/S105262349834847X.

[22]

J. J. Ye and D. L. Zhu, Optimality conditions for bilevel programming problems, Optimization, 33 (1995), 9-27. 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, Springer-Verlag, Berlin/Heidelberg, 1976.

[2]

Y. Chen and M. Florian, The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions, Optimization, 32 (1995), 193-209. 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-609. doi: 10.1137/04060754x.

[4]

S. Dempe, "Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications," 61 (2002), Kluwer Academic Publishers, Dordrecht, The Netherlands .

[5]

M. L. Flegel and C. Kanzow, On the Guignard constraint qualification for mathematical programs with equilibrium constraints, Optimization, 54 (2005), 517-534. 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 "Optimization with Multivalued Mappings: Theory, Applications and Algorithms''(eds. S. Dempe and V. Kalashnikov), Springer-Verlag, New York, 2006, 111-122. 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, Institute of Mathematics, University of Würzburg, Würzburg, February 2010.

[8]

T. Hoheisel, C. Kanzow and A. Schwartz, Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Preprint 299, Institute of Mathematics, University of Würzburg, Würzburg, September 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-103. 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, Institute of Mathematics, University of Würzburg, Würzburg, June 2010.

[11]

S. Leyffer, MacMPEC: AMPL collection of MPECs, www.mcs.anl.go/~leyffer/MacMPEC, 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-84. 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, Cambridge, New York, Melbourne, 1996.

[15]

O. L. Mangasarian, "Nonlinear Programming,'' McGraw-Hill, New York, NY, 1969 (reprinted by SIAM, Philadelphia, PA, 1994).

[16]

J. V. Outrata, M. Kočvara and J. Zowe, "Nonsmooth Approach to Optimization Problems with Equilibrium Constraints,'' Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 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-981. 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-22. 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-936. 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-2539. 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-962. doi: 10.1137/S105262349834847X.

[22]

J. J. Ye and D. L. Zhu, Optimality conditions for bilevel programming problems, Optimization, 33 (1995), 9-27. 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 and 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 and 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 and 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 and 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 and 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 and 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 and Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028

[8]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050

[9]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951

[10]

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 and Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

[11]

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

[12]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030

[13]

Jie Zhang, Shuang Lin, Li-Wei Zhang. A log-exponential regularization method for a mathematical program with general vertical complementarity constraints. Journal of Industrial and Management Optimization, 2013, 9 (3) : 561-577. doi: 10.3934/jimo.2013.9.561

[14]

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 and Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064

[15]

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 and Management Optimization, 2019, 15 (4) : 1653-1675. doi: 10.3934/jimo.2018116

[16]

Adela Capătă. Optimality conditions for strong vector equilibrium problems under a weak constraint qualification. Journal of Industrial and Management Optimization, 2015, 11 (2) : 563-574. doi: 10.3934/jimo.2015.11.563

[17]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021080

[18]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[19]

Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044

[20]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19

 Impact Factor: 

Metrics

  • PDF downloads (104)
  • HTML views (0)
  • Cited by (4)

[Back to Top]