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

[2]

Y. Chen and M. Florian, The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions,, Optimization, 32 (1995), 193.  doi: 10.1080/02331939508844048.  Google Scholar

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

[4]

S. Dempe, "Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications,", 61 (2002), 61 (2002).   Google Scholar

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

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

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

[8]

T. Hoheisel, C. Kanzow and A. Schwartz, Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints,, Preprint 299, (2010).   Google Scholar

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

[10]

C. Kanzow and A. Schwartz, A new regularization method for mathematical programs with complementarity constraints with strong convergence properties,, Preprint 296, (2010).   Google Scholar

[11]

S. Leyffer, MacMPEC: AMPL collection of MPECs,, , (2000).   Google Scholar

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

[13]

, www.netlib.org/ampl/solvers, /examples/amplfunc.c, ().   Google Scholar

[14]

Z. Q. Luo, J. S. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints,'', Cambridge University Press, (1996).   Google Scholar

[15]

O. L. Mangasarian, "Nonlinear Programming,'', McGraw-Hill, (1969).   Google Scholar

[16]

J. V. Outrata, M. Kočvara and J. Zowe, "Nonsmooth Approach to Optimization Problems with Equilibrium Constraints,'', Nonconvex Optimization and its Applications, (1998).   Google Scholar

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

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

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

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

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

[22]

J. J. Ye and D. L. Zhu, Optimality conditions for bilevel programming problems,, Optimization, 33 (1995), 9.  doi: 10.1080/02331939508844060.  Google Scholar

show all references

References:
[1]

M. S. Bazaraa and C. M. Shetty, "Foundations of Optimization,'', Lecture Notes in Economics and Mathematical Systems, (1976).   Google Scholar

[2]

Y. Chen and M. Florian, The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions,, Optimization, 32 (1995), 193.  doi: 10.1080/02331939508844048.  Google Scholar

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

[4]

S. Dempe, "Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications,", 61 (2002), 61 (2002).   Google Scholar

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

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

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

[8]

T. Hoheisel, C. Kanzow and A. Schwartz, Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints,, Preprint 299, (2010).   Google Scholar

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

[10]

C. Kanzow and A. Schwartz, A new regularization method for mathematical programs with complementarity constraints with strong convergence properties,, Preprint 296, (2010).   Google Scholar

[11]

S. Leyffer, MacMPEC: AMPL collection of MPECs,, , (2000).   Google Scholar

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

[13]

, www.netlib.org/ampl/solvers, /examples/amplfunc.c, ().   Google Scholar

[14]

Z. Q. Luo, J. S. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints,'', Cambridge University Press, (1996).   Google Scholar

[15]

O. L. Mangasarian, "Nonlinear Programming,'', McGraw-Hill, (1969).   Google Scholar

[16]

J. V. Outrata, M. Kočvara and J. Zowe, "Nonsmooth Approach to Optimization Problems with Equilibrium Constraints,'', Nonconvex Optimization and its Applications, (1998).   Google Scholar

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

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

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

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

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

[22]

J. J. Ye and D. L. Zhu, Optimality conditions for bilevel programming problems,, Optimization, 33 (1995), 9.  doi: 10.1080/02331939508844060.  Google Scholar

[1]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[2]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[3]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[4]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[5]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446

[6]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[7]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219

[8]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[9]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082

[10]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345

[11]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[12]

Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081

[13]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHum approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[14]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[15]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[16]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[17]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[18]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[19]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[20]

Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243

 Impact Factor: 

Metrics

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

[Back to Top]