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

[2]

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

[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.  doi: 10.1023/A:1018359900133.  Google Scholar

[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.  doi: 10.1007/BF02876059.  Google Scholar

[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.  doi: 10.1023/A:1022639306130.  Google Scholar

[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.  doi: 10.1016/j.apm.2013.05.037.  Google Scholar

[7]

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

[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.  doi: 10.1007/s00245-005-0848-8.  Google Scholar

[9]

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

[10]

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

[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.  doi: 10.1137/070705490.  Google Scholar

[12]

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

[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.  doi: 10.1007/s10898-004-2708-5.  Google Scholar

[14]

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

[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.  doi: 10.1137/080739884.  Google Scholar

[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.  doi: 10.1080/10556788.2013.879587.  Google Scholar

[17]

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

[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.  doi: 10.1007/s10957-009-9642-0.  Google Scholar

[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.  doi: 10.1007/s10898-009-9419-x.  Google Scholar

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

[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.  doi: 10.1137/0326046.  Google Scholar

[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.  doi: 10.1137/S1052623499353935.  Google Scholar

[23]

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

[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.  doi: 10.1137/S1052623401383881.  Google Scholar

[25]

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

show all references

References:
[1]

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

[2]

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

[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.  doi: 10.1023/A:1018359900133.  Google Scholar

[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.  doi: 10.1007/BF02876059.  Google Scholar

[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.  doi: 10.1023/A:1022639306130.  Google Scholar

[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.  doi: 10.1016/j.apm.2013.05.037.  Google Scholar

[7]

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

[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.  doi: 10.1007/s00245-005-0848-8.  Google Scholar

[9]

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

[10]

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

[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.  doi: 10.1137/070705490.  Google Scholar

[12]

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

[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.  doi: 10.1007/s10898-004-2708-5.  Google Scholar

[14]

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

[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.  doi: 10.1137/080739884.  Google Scholar

[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.  doi: 10.1080/10556788.2013.879587.  Google Scholar

[17]

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

[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.  doi: 10.1007/s10957-009-9642-0.  Google Scholar

[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.  doi: 10.1007/s10898-009-9419-x.  Google Scholar

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

[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.  doi: 10.1137/0326046.  Google Scholar

[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.  doi: 10.1137/S1052623499353935.  Google Scholar

[23]

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

[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.  doi: 10.1137/S1052623401383881.  Google Scholar

[25]

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

[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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - A, 2019, 39 (12) : 7213-7248. doi: 10.3934/dcds.2019301
[9]

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

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

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
[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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - A, 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 & 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 & 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 & Continuous Dynamical Systems - B, 2016, 21 (5) : 1435-1444. doi: 10.3934/dcdsb.2016004

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences