American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Rank-one and sparse matrix decomposition for dynamic MRI
  • NACO Home
  • This Issue
  • Next Article
    Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term
2015, 5(2): 115-126. doi: 10.3934/naco.2015.5.115

A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints

Jianling Li 1, , Chunting Lu 1, and  Youfang Zeng 1,

1. 

College of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, 530004, China, China, China

Received  November 2014 Revised  May 2015 Published  June 2015

In this paper, a smooth QP-free algorithm without a penalty function or a filter is proposed for a special kind of mathematical programs with complementarity constraints (MPCC for short). Firstly, the investigated problem is transformed into sequential parametric standard nonlinear programs by perturbed techniques and a generalized complementarity function. Then the trial step, at each iteration, is accepted such that either the value of the objective function or the measure of the constraint violation is sufficiently reduced. Finally, it is shown that every limit point of the iterative sequence is feasible, and there exists a limit point that is a KKT point for the problem under mild conditions.
Keywords: penalty-function-free, global convergence., Mathematical programs, complementarity constraints, QP-free, filter-free.
Mathematics Subject Classification: 90C30, 65K0.
Citation: 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
References:
[1]

R. W. Cottle, J. S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press: Boston, 1992.

[2]

F. Facchinei, H. Y. Jiang and L. Q. Qi, A smoothing method for mathematical programs with equilibrium constraints, Math. Program, 85 (1999), 107-134. doi: 10.1007/s101070050048.

[3]

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.

[4]

Z. Y. Gao, G. P. He and F. Wu, A sequential systems of linear equations method with arbitrary initial point, SCI China Ser A, 27 (1997), 24-33. doi: 10.1007/BF02876059.

[5]

Z. Y. Gao, G. P. He and F. Wu, Sequential systems of linear equations algorithm for nonlinear optimization problems with general constraints, J. Optimi. Theory Appl., 95 (1997), 371-397. doi: 10.1023/A:1022639306130.

[6]

H. W. Ge and Z. W. Chen, A penalty-free method with line search for nonlinear equality constrained optimization, Appl. Math. Model., 37 (2013), 9934-9949. doi: 10.1016/j.apm.2013.05.037.

[7]

J. B. Jian, A superlinearly convergent implicit smooth SQP algorithm for mathematical programs with nonlinear complementarity constraints, Comput. Optim. Appl., 31 (2005), 335-361. doi: 10.1007/s10589-005-3230-5.

[8]

J. B. Jian, J. L. Li and X. D. Mo, A strongly and superlinearly convergent SQP algorithm for optimization problems with linear complementarity constraints, Appl. Math. Optim.,54 (2006), 17-46. doi: 10.1007/s00245-005-0848-8.

[9]

J. B. Jian, Fast Algorithms for Smooth Constrained Optimization: Theoretical Analysis and Numerical Experiments, Science Press, 2010.

[10]

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.

[11]

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.

[12]

C. Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal., 17 (1996), 851-868. doi: 10.1137/S0895479894273134.

[13]

J. L. Li and J. B. Jian, A superlinearly convergent SSLE algorithm for optimization problems with linear complementarity constraints, J. Global Optim., 33 (2005), 477-510. doi: 10.1007/s10898-004-2708-5.

[14]

G. H. Lin and M. Fukushima, A modified relaxation scheme for mathematical programs with complementarity constraints, Ann. Oper. Res., 133 (2005), 63-84. doi: 10.1007/s10479-004-5024-z.

[15]

X. Liu and Y. Yuan, A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization, SIAM J. Optim., 21 (2011), 545-571. doi: 10.1137/080739884.

[16]

W. A. Liu, C. G. Shen, X. J. Zhu and D. G. Pu, An infeasible QP-free algorithm without a penalty function or a filter for nonlinear inequality constrained optimization, Optim. Method Softw., 29 (2014), 1238-1260. doi: 10.1080/10556788.2013.879587.

[17]

Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996. doi: 10.1017/CBO9780511983658.

[18]

H. Z. Luo, X. L. Sun and Y. F. Xu, Convergence properties of modified partially augmented Lagrangian methods for mathematical programs with complementarity constraints, J. Optimi. Theory Appl., 145 (2010), 489-506. doi: 10.1007/s10957-009-9642-0.

[19]

H. Z. Luo, X. L. Sun, Y. F. Xu and H. X. Wu, On the convergence properties of modified augmented lagrangian methods for Mathematical Programming with Complementarity Constraints, J. Global Optim, 46 (2010), 217-232. doi: 10.1007/s10898-009-9419-x.

[20]

J. Outrata, M. Kocvara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results, Springer, 1998. doi: 10.1007/978-1-4757-2825-5.

[21]

E. R. Panier, A. L. Tits and J. N. Herskovits, A QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM J. Optim., 26 (1988), 788-811. doi: 10.1137/0326046.

[22]

H. D. Qi and L. Q. Qi, A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM J. Optimi., 11 (2000), 113-132. doi: 10.1137/S1052623499353935.

[23]

Hoheisel Tim, Kanzow Christian and Schwartz Alexandra, Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Math. Program., Ser. A, 137 (2013), 257-288. doi: 10.1007/s10107-011-0488-5.

[24]

Y. F. Yang, D. H. Li and L. Q. Qi, A feasible sequential linear equation method for inequality constrained optimization, SIAM J. Optim., 13, (2003), 1222-1244. doi: 10.1137/S1052623401383881.

[25]

Z. B. Zhu and K. C. Zhang, A superlinearly convergent SQP algorithm for mathematical programs with linear complementarity constraints, Appl. Math. Comput., 172 (2006), 222-244. doi: 10.1016/j.amc.2005.01.141.

show all references

References:
[1]

R. W. Cottle, J. S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press: Boston, 1992.

[2]

F. Facchinei, H. Y. Jiang and L. Q. Qi, A smoothing method for mathematical programs with equilibrium constraints, Math. Program, 85 (1999), 107-134. doi: 10.1007/s101070050048.

[3]

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.

[4]

Z. Y. Gao, G. P. He and F. Wu, A sequential systems of linear equations method with arbitrary initial point, SCI China Ser A, 27 (1997), 24-33. doi: 10.1007/BF02876059.

[5]

Z. Y. Gao, G. P. He and F. Wu, Sequential systems of linear equations algorithm for nonlinear optimization problems with general constraints, J. Optimi. Theory Appl., 95 (1997), 371-397. doi: 10.1023/A:1022639306130.

[6]

H. W. Ge and Z. W. Chen, A penalty-free method with line search for nonlinear equality constrained optimization, Appl. Math. Model., 37 (2013), 9934-9949. doi: 10.1016/j.apm.2013.05.037.

[7]

J. B. Jian, A superlinearly convergent implicit smooth SQP algorithm for mathematical programs with nonlinear complementarity constraints, Comput. Optim. Appl., 31 (2005), 335-361. doi: 10.1007/s10589-005-3230-5.

[8]

J. B. Jian, J. L. Li and X. D. Mo, A strongly and superlinearly convergent SQP algorithm for optimization problems with linear complementarity constraints, Appl. Math. Optim.,54 (2006), 17-46. doi: 10.1007/s00245-005-0848-8.

[9]

J. B. Jian, Fast Algorithms for Smooth Constrained Optimization: Theoretical Analysis and Numerical Experiments, Science Press, 2010.

[10]

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.

[11]

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.

[12]

C. Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal., 17 (1996), 851-868. doi: 10.1137/S0895479894273134.

[13]

J. L. Li and J. B. Jian, A superlinearly convergent SSLE algorithm for optimization problems with linear complementarity constraints, J. Global Optim., 33 (2005), 477-510. doi: 10.1007/s10898-004-2708-5.

[14]

G. H. Lin and M. Fukushima, A modified relaxation scheme for mathematical programs with complementarity constraints, Ann. Oper. Res., 133 (2005), 63-84. doi: 10.1007/s10479-004-5024-z.

[15]

X. Liu and Y. Yuan, A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization, SIAM J. Optim., 21 (2011), 545-571. doi: 10.1137/080739884.

[16]

W. A. Liu, C. G. Shen, X. J. Zhu and D. G. Pu, An infeasible QP-free algorithm without a penalty function or a filter for nonlinear inequality constrained optimization, Optim. Method Softw., 29 (2014), 1238-1260. doi: 10.1080/10556788.2013.879587.

[17]

Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996. doi: 10.1017/CBO9780511983658.

[18]

H. Z. Luo, X. L. Sun and Y. F. Xu, Convergence properties of modified partially augmented Lagrangian methods for mathematical programs with complementarity constraints, J. Optimi. Theory Appl., 145 (2010), 489-506. doi: 10.1007/s10957-009-9642-0.

[19]

H. Z. Luo, X. L. Sun, Y. F. Xu and H. X. Wu, On the convergence properties of modified augmented lagrangian methods for Mathematical Programming with Complementarity Constraints, J. Global Optim, 46 (2010), 217-232. doi: 10.1007/s10898-009-9419-x.

[20]

J. Outrata, M. Kocvara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results, Springer, 1998. doi: 10.1007/978-1-4757-2825-5.

[21]

E. R. Panier, A. L. Tits and J. N. Herskovits, A QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM J. Optim., 26 (1988), 788-811. doi: 10.1137/0326046.

[22]

H. D. Qi and L. Q. Qi, A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM J. Optimi., 11 (2000), 113-132. doi: 10.1137/S1052623499353935.

[23]

Hoheisel Tim, Kanzow Christian and Schwartz Alexandra, Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Math. Program., Ser. A, 137 (2013), 257-288. doi: 10.1007/s10107-011-0488-5.

[24]

Y. F. Yang, D. H. Li and L. Q. Qi, A feasible sequential linear equation method for inequality constrained optimization, SIAM J. Optim., 13, (2003), 1222-1244. doi: 10.1137/S1052623401383881.

[25]

Z. B. Zhu and K. C. Zhang, A superlinearly convergent SQP algorithm for mathematical programs with linear complementarity constraints, Appl. Math. Comput., 172 (2006), 222-244. doi: 10.1016/j.amc.2005.01.141.

[1]

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

Guodong Ma, Jinbao Jian. A QP-free algorithm of quasi-strongly sub-feasible directions for inequality constrained optimization. Journal of Industrial and Management Optimization, 2015, 11 (1) : 307-328. doi: 10.3934/jimo.2015.11.307
[3]

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

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

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

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

David Jerison, Nikola Kamburov. Free boundaries subject to topological constraints. Discrete and Continuous Dynamical Systems, 2019, 39 (12) : 7213-7248. doi: 10.3934/dcds.2019301
[9]

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

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

Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391
[12]

Luca Consolini, Alessandro Costalunga, Manfredi Maggiore. A coordinate-free theory of virtual holonomic constraints. Journal of Geometric Mechanics, 2018, 10 (4) : 467-502. doi: 10.3934/jgm.2018018
[13]

Antonio Fasano, Mario Primicerio, Andrea Tesi. A mathematical model for spaghetti cooking with free boundaries. Networks and Heterogeneous Media, 2011, 6 (1) : 37-60. doi: 10.3934/nhm.2011.6.37
[14]

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

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

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

Tong Yang, Fahuai Yi. Global existence and uniqueness for a hyperbolic system with free boundary. Discrete and Continuous Dynamical Systems, 2001, 7 (4) : 763-780. doi: 10.3934/dcds.2001.7.763
[18]

Zhi-Min Chen. Straightforward approximation of the translating and pulsating free surface Green function. Discrete and Continuous Dynamical Systems - B, 2014, 19 (9) : 2767-2783. doi: 10.3934/dcdsb.2014.19.2767
[19]

Jinzhi Wang, Yuduo Zhang. Solving the seepage problems with free surface by mathematical programming method. Numerical Algebra, Control and Optimization, 2015, 5 (4) : 351-357. doi: 10.3934/naco.2015.5.351
[20]

Xinfu Chen, Bei Hu, Jin Liang, Yajing Zhang. Convergence rate of free boundary of numerical scheme for American option. Discrete and Continuous Dynamical Systems - B, 2016, 21 (5) : 1435-1444. doi: 10.3934/dcdsb.2016004

 Impact Factor: 

Tools

Metrics

  • PDF downloads (67)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy