• 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

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

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

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

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003

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

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

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

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

[9]

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

[10]

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

[11]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[12]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[13]

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

[14]

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

[15]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344

[16]

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

[17]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[18]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[19]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[20]

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

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]