American Institute of Mathematical Sciences

Advanced
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

Chunlin Hao 1, and  Xinwei Liu 2,

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.
Keywords: filter-SQP, Mathematical program with linear complementarity constraints, trust-region method..
Mathematics Subject Classification: Primary: 90C30, 90C51; Secondary: 65K0.
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-182. 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-659. 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-269. 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-59. 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-34. 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-681. 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-739. 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-38. 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-170.  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-59.  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-808. 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-103. doi: 10.1137/070705490.  Google Scholar

[15]

S. Leyffer, Complementarity constraints as nonlinear equations: Theory and numerical experience, in "Optimization with Multivalued Mappings," 2, Springer, New York, (2006), 169-208.  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-116. 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-33. 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-261. 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-307. 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, Cambridge, 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-750. doi: 10.1137/S1052623403429081.  Google Scholar

[23]

D. Ralph, Sequential quadratic programming for mathematical programs with linear complementarity constraints, in "Computational Techniques and Applications: CTAC95" (eds. R. L. May and A. K. Easton), World Scientific Publ., River Edge, NJ, (1996), 663-668.  Google Scholar

[24]

S. Schöltes, Convergence properties of regularization scheme for mathematical programs with complementarity constraints, SIAM J.Optim., 11 (2001), 918-936. 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-652. 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-2217. 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-48. 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-31. 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-558. 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-182. 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-659. 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-269. 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-59. 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-34. 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-681. 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-739. 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-38. 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-170.  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-59.  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-808. 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-103. doi: 10.1137/070705490.  Google Scholar

[15]

S. Leyffer, Complementarity constraints as nonlinear equations: Theory and numerical experience, in "Optimization with Multivalued Mappings," 2, Springer, New York, (2006), 169-208.  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-116. 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-33. 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-261. 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-307. 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, Cambridge, 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-750. doi: 10.1137/S1052623403429081.  Google Scholar

[23]

D. Ralph, Sequential quadratic programming for mathematical programs with linear complementarity constraints, in "Computational Techniques and Applications: CTAC95" (eds. R. L. May and A. K. Easton), World Scientific Publ., River Edge, NJ, (1996), 663-668.  Google Scholar

[24]

S. Schöltes, Convergence properties of regularization scheme for mathematical programs with complementarity constraints, SIAM J.Optim., 11 (2001), 918-936. 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-652. 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-2217. 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-48. 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-31. 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-558. doi: 10.1007/s00211-004-0542-9.  Google Scholar

[1]

Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919
[2]

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
[3]

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 & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[4]

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
[5]

Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial & Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321
[6]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223
[7]

Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117
[8]

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
[9]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[10]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117
[11]

Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial & Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733
[12]

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
[13]

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
[14]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237
[15]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309
[16]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
[17]

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
[18]

Michal Kočvara, Jiří V. Outrata. Inverse truss design as a conic mathematical program with equilibrium constraints. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1329-1350. doi: 10.3934/dcdss.2017071
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy