October  2011, 7(4): 1041-1055. doi: 10.3934/jimo.2011.7.1041

A trust-region filter-SQP method for mathematical programs with linear complementarity constraints

1. 

Department of Applied Mathematics, Beijing University of Technology, Beijing 100124, China

2. 

Department of Applied Mathematics, Hebei University of Technology, Tianjin 300401, China

Received  October 2010 Revised  July 2011 Published  August 2011

A trust-region filter-SQP method for mathematical programs with linear complementarity constraints (MPLCCs) is presented. The method is similar to that proposed by Liu, Perakis and Sun [Computational Optimization and Applications, 34, 5-33, 2006] but it solves the trust-region quadratic programming subproblems at each iteration and uses the filter technique to promote the global convergence. As a result, the method here is more robust since it admits the use of Lagrangian Hessian information and its performance is not affected by any penalty parameter. The preliminary numerical results on test problems generated by the QPECgen generator show that the presented method is effective.
Citation: 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
References:
[1]

H. Benson, A. Sen, D. F. Shanno and R. J. Vanderbei, Interior-point algorithms, penalty methods and equilibrium problems,, Comput. Optim. Appl., 34 (2006), 155.  doi: 10.1007/s10589-005-3908-8.  Google Scholar

[2]

L. Chen and D. Goldfarb, An active set method for mathematical programs with linear complementarity constraints,, Available from: \url{http://www.corc.ieor.columbia.edu/reports/techreports/tr-2007-02.pdf}, (): 2007.   Google Scholar

[3]

R. Fletcher, N. I. M. Gould, S. Leyffer, P. L. Toint and A. Wächter, Global convergence of trust-region SQP-filter algorithms for general nonlinear programming,, SIAM J. Optim., 13 (2002), 635.  doi: 10.1137/S1052623499357258.  Google Scholar

[4]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Math. Program Ser. A, 91 (2002), 239.  doi: 10.1007/s101070100244.  Google Scholar

[5]

R. Fletcher, S. Leyffer and C. Shen, Nonmonotone filter method for nonlinear optimization,, Available from: \url{http://wiki.mcs.anl.gov/leyffer/images/archive/c/c4/20091014223041!Nfilter.pdf}, ().   Google Scholar

[6]

R. Fletcher, S. Leyffer and P. L. Toint, On the global convergence of a filter-SQP algorithm,, SIAM J. Optim., 13 (2002), 44.  doi: 10.1137/S105262340038081X.  Google Scholar

[7]

M. Fukushima, Z. Q. Luo and J. S. Pang, A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints,, Comput. Optim. Appl., 10 (1998), 5.  doi: 10.1023/A:1018359900133.  Google Scholar

[8]

M. Fukushima and J. S. Pang, Some feasibility issues in mathematical programs with equilibrium constraints,, SIAM J. Optim., 8 (1998), 673.  doi: 10.1137/S105262349731577X.  Google Scholar

[9]

M. Fukushima and P. Tseng, An implementable active-set algorithm for computing a B-stationary point of a mathematical program with linear complementarity constraints,, SIAM J. Optim., 12 (2002), 724.  doi: 10.1137/S1052623499363232.  Google Scholar

[10]

N. I. M. Gould, S. Leyffer and P. L. Toint, A multidimensional filter algorithm for nonlinear equations and nonlinear least squares,, SIAM J. Optim., 15 (2004), 17.  doi: 10.1137/S1052623403422637.  Google Scholar

[11]

Z. Huang and J. Sun, A smoothing Newton algorithm for mathematical programs with complementarity constraints,, J. Ind. Man. Optim., 1 (2005), 153.   Google Scholar

[12]

H. Jiang and D. Ralph, QPECgen: A MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints, Computational Optimization-A Tribute to Olvi Magasarian, Part II,, Comput. Optim. Appl., 13 (1999), 25.   Google Scholar

[13]

H. Y. Jiang and D. Ralph, Smooth SQP methods for mathematical programs with nonlinear complementarity constraints,, SIAM J. Optim., 10 (2000), 779.  doi: 10.1137/S1052623497332329.  Google Scholar

[14]

A. Kadrani, J.-P. Dussault and A. Benchakroun, A new regularization scheme for mathematical programs with complementarity constraints,, SIAM J. Optim., 20 (2009), 78.  doi: 10.1137/070705490.  Google Scholar

[15]

S. Leyffer, Complementarity constraints as nonlinear equations: Theory and numerical experience,, in, 2 (2006), 169.   Google Scholar

[16]

S. Leyffer and T. S. Munson, A global convergent filter method for MPECs,, Available from: \url{http://www.mcs.anl.gov/~leyffer/papers/slpec.pdf}, ().   Google Scholar

[17]

G. Lin and M. Fukushima, New relaxation method for mathematical programs with complementarity constraints,, J. Optim. Theory Appl., 118 (2003), 81.  doi: 10.1023/A:1024739508603.  Google Scholar

[18]

X.-W. Liu, G. Perakis and J. Sun, A robust SQP method for mathematical programs with linear complementarity constraints,, Comput. Optim. Appl., 34 (2006), 5.  doi: 10.1007/s10589-005-3075-y.  Google Scholar

[19]

X.-W. Liu and J. Sun, Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints,, Math. Program., 101 (2004), 231.  doi: 10.1007/s10107-004-0543-6.  Google Scholar

[20]

J. Long and S. Zeng, A projection-filter method for solving nonlinear complementarity problems,, Appl. Math. Comput., 216 (2010), 300.  doi: 10.1016/j.amc.2010.01.063.  Google Scholar

[21]

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

[22]

A. Raghunathan and L. T. Biegler, An interior point method for mathematical programs with complementarity constraints (MPCCs),, SIAM J. Optim., 15 (2005), 720.  doi: 10.1137/S1052623403429081.  Google Scholar

[23]

D. Ralph, Sequential quadratic programming for mathematical programs with linear complementarity constraints,, in, (1996), 663.   Google Scholar

[24]

S. Schöltes, Convergence properties of regularization scheme for mathematical programs with complementarity constraints,, SIAM J.Optim., 11 (2001), 918.  doi: 10.1137/S1052623499361233.  Google Scholar

[25]

S. Schöltes and M. Stöhr, Exact penalization of mathematical programs with equilibrium constraints,, SIAM J. Control Optim., 37 (1999), 617.  doi: 10.1137/S0363012996306121.  Google Scholar

[26]

C. Shen, W. Xue and D. Pu, A globally convergent trust region multidimensional filter SQP algorithm for nonlinear programming,, Int. J. Comput. Math., 86 (2009), 2201.  doi: 10.1080/00207160802702400.  Google Scholar

[27]

A. Wächter and L. Biegler, Line search filter methods for nonlinear programming: Local convergence,, SIAM J. Optim., 16 (2005), 32.  doi: 10.1137/S1052623403426544.  Google Scholar

[28]

A. Wächter and L. Biegler, Line search filter methods for nonlinear programming: Motivation and global convergence,, SIAM J. Optim., 16 (2005), 1.  doi: 10.1137/S1052623403426556.  Google Scholar

[29]

J. Zhang, G. Liu and S. Wang, A globally convergent approximately active search algorithm for solving mathematical programs with linear complementarity constraints,, Numer. Math., 98 (2004), 539.  doi: 10.1007/s00211-004-0542-9.  Google Scholar

show all references

References:
[1]

H. Benson, A. Sen, D. F. Shanno and R. J. Vanderbei, Interior-point algorithms, penalty methods and equilibrium problems,, Comput. Optim. Appl., 34 (2006), 155.  doi: 10.1007/s10589-005-3908-8.  Google Scholar

[2]

L. Chen and D. Goldfarb, An active set method for mathematical programs with linear complementarity constraints,, Available from: \url{http://www.corc.ieor.columbia.edu/reports/techreports/tr-2007-02.pdf}, (): 2007.   Google Scholar

[3]

R. Fletcher, N. I. M. Gould, S. Leyffer, P. L. Toint and A. Wächter, Global convergence of trust-region SQP-filter algorithms for general nonlinear programming,, SIAM J. Optim., 13 (2002), 635.  doi: 10.1137/S1052623499357258.  Google Scholar

[4]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Math. Program Ser. A, 91 (2002), 239.  doi: 10.1007/s101070100244.  Google Scholar

[5]

R. Fletcher, S. Leyffer and C. Shen, Nonmonotone filter method for nonlinear optimization,, Available from: \url{http://wiki.mcs.anl.gov/leyffer/images/archive/c/c4/20091014223041!Nfilter.pdf}, ().   Google Scholar

[6]

R. Fletcher, S. Leyffer and P. L. Toint, On the global convergence of a filter-SQP algorithm,, SIAM J. Optim., 13 (2002), 44.  doi: 10.1137/S105262340038081X.  Google Scholar

[7]

M. Fukushima, Z. Q. Luo and J. S. Pang, A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints,, Comput. Optim. Appl., 10 (1998), 5.  doi: 10.1023/A:1018359900133.  Google Scholar

[8]

M. Fukushima and J. S. Pang, Some feasibility issues in mathematical programs with equilibrium constraints,, SIAM J. Optim., 8 (1998), 673.  doi: 10.1137/S105262349731577X.  Google Scholar

[9]

M. Fukushima and P. Tseng, An implementable active-set algorithm for computing a B-stationary point of a mathematical program with linear complementarity constraints,, SIAM J. Optim., 12 (2002), 724.  doi: 10.1137/S1052623499363232.  Google Scholar

[10]

N. I. M. Gould, S. Leyffer and P. L. Toint, A multidimensional filter algorithm for nonlinear equations and nonlinear least squares,, SIAM J. Optim., 15 (2004), 17.  doi: 10.1137/S1052623403422637.  Google Scholar

[11]

Z. Huang and J. Sun, A smoothing Newton algorithm for mathematical programs with complementarity constraints,, J. Ind. Man. Optim., 1 (2005), 153.   Google Scholar

[12]

H. Jiang and D. Ralph, QPECgen: A MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints, Computational Optimization-A Tribute to Olvi Magasarian, Part II,, Comput. Optim. Appl., 13 (1999), 25.   Google Scholar

[13]

H. Y. Jiang and D. Ralph, Smooth SQP methods for mathematical programs with nonlinear complementarity constraints,, SIAM J. Optim., 10 (2000), 779.  doi: 10.1137/S1052623497332329.  Google Scholar

[14]

A. Kadrani, J.-P. Dussault and A. Benchakroun, A new regularization scheme for mathematical programs with complementarity constraints,, SIAM J. Optim., 20 (2009), 78.  doi: 10.1137/070705490.  Google Scholar

[15]

S. Leyffer, Complementarity constraints as nonlinear equations: Theory and numerical experience,, in, 2 (2006), 169.   Google Scholar

[16]

S. Leyffer and T. S. Munson, A global convergent filter method for MPECs,, Available from: \url{http://www.mcs.anl.gov/~leyffer/papers/slpec.pdf}, ().   Google Scholar

[17]

G. Lin and M. Fukushima, New relaxation method for mathematical programs with complementarity constraints,, J. Optim. Theory Appl., 118 (2003), 81.  doi: 10.1023/A:1024739508603.  Google Scholar

[18]

X.-W. Liu, G. Perakis and J. Sun, A robust SQP method for mathematical programs with linear complementarity constraints,, Comput. Optim. Appl., 34 (2006), 5.  doi: 10.1007/s10589-005-3075-y.  Google Scholar

[19]

X.-W. Liu and J. Sun, Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints,, Math. Program., 101 (2004), 231.  doi: 10.1007/s10107-004-0543-6.  Google Scholar

[20]

J. Long and S. Zeng, A projection-filter method for solving nonlinear complementarity problems,, Appl. Math. Comput., 216 (2010), 300.  doi: 10.1016/j.amc.2010.01.063.  Google Scholar

[21]

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

[22]

A. Raghunathan and L. T. Biegler, An interior point method for mathematical programs with complementarity constraints (MPCCs),, SIAM J. Optim., 15 (2005), 720.  doi: 10.1137/S1052623403429081.  Google Scholar

[23]

D. Ralph, Sequential quadratic programming for mathematical programs with linear complementarity constraints,, in, (1996), 663.   Google Scholar

[24]

S. Schöltes, Convergence properties of regularization scheme for mathematical programs with complementarity constraints,, SIAM J.Optim., 11 (2001), 918.  doi: 10.1137/S1052623499361233.  Google Scholar

[25]

S. Schöltes and M. Stöhr, Exact penalization of mathematical programs with equilibrium constraints,, SIAM J. Control Optim., 37 (1999), 617.  doi: 10.1137/S0363012996306121.  Google Scholar

[26]

C. Shen, W. Xue and D. Pu, A globally convergent trust region multidimensional filter SQP algorithm for nonlinear programming,, Int. J. Comput. Math., 86 (2009), 2201.  doi: 10.1080/00207160802702400.  Google Scholar

[27]

A. Wächter and L. Biegler, Line search filter methods for nonlinear programming: Local convergence,, SIAM J. Optim., 16 (2005), 32.  doi: 10.1137/S1052623403426544.  Google Scholar

[28]

A. Wächter and L. Biegler, Line search filter methods for nonlinear programming: Motivation and global convergence,, SIAM J. Optim., 16 (2005), 1.  doi: 10.1137/S1052623403426556.  Google Scholar

[29]

J. Zhang, G. Liu and S. Wang, A globally convergent approximately active search algorithm for solving mathematical programs with linear complementarity constraints,, Numer. Math., 98 (2004), 539.  doi: 10.1007/s00211-004-0542-9.  Google Scholar

[1]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104

[2]

Qiang Fu, Xin Guo, Sun Young Jeon, Eric N. Reither, Emma Zang, Kenneth C. Land. The uses and abuses of an age-period-cohort method: On the linear algebra and statistical properties of intrinsic and related estimators. Mathematical Foundations of Computing, 2020  doi: 10.3934/mfc.2021001

[3]

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

[4]

Manuel de León, Víctor M. Jiménez, Manuel Lainz. Contact Hamiltonian and Lagrangian systems with nonholonomic constraints. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2021001

[5]

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

[6]

Philippe G. Ciarlet, Liliana Gratie, Cristinel Mardare. Intrinsic methods in elasticity: a mathematical survey. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 133-164. doi: 10.3934/dcds.2009.23.133

[7]

M. Dambrine, B. Puig, G. Vallet. A mathematical model for marine dinoflagellates blooms. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 615-633. doi: 10.3934/dcdss.2020424

[8]

Junkee Jeon. Finite horizon portfolio selection problems with stochastic borrowing constraints. Journal of Industrial & Management Optimization, 2021, 17 (2) : 733-763. doi: 10.3934/jimo.2019132

[9]

Nan Zhang, Linyi Qian, Zhuo Jin, Wei Wang. Optimal stop-loss reinsurance with joint utility constraints. Journal of Industrial & Management Optimization, 2021, 17 (2) : 841-868. doi: 10.3934/jimo.2020001

[10]

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

[11]

Urszula Ledzewicz, Heinz Schättler. On the role of pharmacometrics in mathematical models for cancer treatments. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 483-499. doi: 10.3934/dcdsb.2020213

[12]

Jakub Kantner, Michal Beneš. Mathematical model of signal propagation in excitable media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 935-951. doi: 10.3934/dcdss.2020382

[13]

Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110

[14]

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

[15]

Martin Kalousek, Joshua Kortum, Anja Schlömerkemper. Mathematical analysis of weak and strong solutions to an evolutionary model for magnetoviscoelasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 17-39. doi: 10.3934/dcdss.2020331

[16]

Sarra Nouaoura, Radhouane Fekih-Salem, Nahla Abdellatif, Tewfik Sari. Mathematical analysis of a three-tiered food-web in the chemostat. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020369

[17]

Tetsuya Ishiwata, Young Chol Yang. Numerical and mathematical analysis of blow-up problems for a stochastic differential equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 909-918. doi: 10.3934/dcdss.2020391

[18]

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

[19]

Xiaoxiao Li, Yingjing Shi, Rui Li, Shida Cao. Energy management method for an unpowered landing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020180

[20]

Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (55)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]