
-
Previous Article
On fractional vector optimization over cones with support functions
- JIMO Home
- This Issue
- Next Article
The linear convergence of a derivative-free descent method for nonlinear complementarity problems
1. | Department of Mathematics, School of Science, Tianjin University, Tianjin 300072, China |
2. | Department of Mathematics, School of Science, Tianjin University of Technology, Tianjin 300384, China |
Recently, Hu, Huang and Chen [Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math. 230 (2009): 69-82] introduced a family of generalized NCP-functions, which include many existing NCP-functions as special cases. They obtained several favorite properties of the functions; and by which, they showed that a derivative-free descent method is globally convergent under suitable assumptions. However, no result on convergent rate of the method was reported. In this paper, we further investigate some properties of this family of generalized NCP-functions. In particular, we show that, under suitable assumptions, the iterative sequence generated by the descent method discussed in their paper converges globally at a linear rate to a solution of the nonlinear complementarity problem. Some preliminary numerical results are reported, which verify the theoretical results obtained.
References:
[1] |
S. C. Billups, S. P. Drikse and M. C. Soares,
A comparison of algorithm for large scale mixed complementartiy problems, Comput. Optim. Appl., 7 (1977), 3-25.
doi: 10.1023/A:1008632215341. |
[2] |
J.-S. Chen,
The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem, J. Global Optim., 36 (2006), 565-580.
doi: 10.1007/s10898-006-9027-y. |
[3] |
J.-S. Chen, Z. H. Huang and C.-Y. She,
A new class of penalized NCP-functions and its properties, Comput. Optim. Appl., 50 (2011), 49-73.
doi: 10.1007/s10589-009-9315-9. |
[4] |
J.-S. Chen and S. H. Pan,
A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for $P_0$-NCPs, J. Comput. Appl. Math., 220 (2008), 464-479.
doi: 10.1016/j.cam.2007.08.020. |
[5] |
J.-S. Chen and S. H. Pan,
A family of NCP-functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl., 40 (2008), 389-404.
doi: 10.1007/s10589-007-9086-0. |
[6] |
J.-S. Chen, H.-T. Gao and S. H. Pan,
An $R$-linearly convergent derivative-free algorithm for nonlinear complementarity problems based on the generalized Fisher-Burmeister merit function, Comput. Optim. Appl., 232 (2009), 455-471.
doi: 10.1016/j.cam.2009.06.022. |
[7] |
F. Facchinei and J. S. Pang, Finite-dimensional variational inequalities and complementarity problems, Springer Verlag, New York, 2003. Google Scholar |
[8] |
F. Facchinei and J. Soares,
A new merit function for nonlinear complementarity problems and a related algorithm, SIAM J. Optim., 7 (1997), 225-247.
doi: 10.1137/S1052623494279110. |
[9] |
M. C. Ferris and J. S. Pang,
Engineering and economic applications of complementarity problems, SIAM Rev., 39 (1997), 669-713.
doi: 10.1137/S0036144595285963. |
[10] |
C. Geiger and C. Kanzow,
On the resolution of monotone complementarity problems, Comput. Optim. Appl., 5 (1996), 155-173.
doi: 10.1007/BF00249054. |
[11] |
P. T. Harker and J. S. Pang,
Finite dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and applications, Math. Program., 48 (1990), 161-220.
doi: 10.1007/BF01582255. |
[12] |
S. L. Hu, Z. H. Huang and J.-S. Chen,
Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math., 230 (2009), 69-82.
doi: 10.1016/j.cam.2008.10.056. |
[13] |
S. L. Hu, Z. H. Huang and N. Lu,
Smoothness of a class of generalized merit functions for the second-order cone complementarity problem, Pacific J. Optim., 6 (2010), 551-571.
|
[14] |
Z. H. Huang,
The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP, IMA J. Numer. Anal., 25 (2005), 670-684.
doi: 10.1093/imanum/dri008. |
[15] |
Z. H. Huang, L. Qi and D. Sun,
Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$-and monotone LCP, Math. Program., 99 (2004), 423-441.
doi: 10.1007/s10107-003-0457-8. |
[16] |
H. Y. Jiang, M. Fukushima and L. Qi,
A trust region method for solving generalized complementarity problems, SIAM. J. Optim., 8 (1998), 140-157.
doi: 10.1137/S1052623495296541. |
[17] |
C. Kanzow and H. Kleinmichel,
A new class of semismooth Newton method for nonlinear complementarity problems, Comput. Optim. Appl., 11 (1998), 227-251.
doi: 10.1023/A:1026424918464. |
[18] |
L. Y. Lu, Z. H. Huang and S. L. Hu,
Properties of a family of merit functions and a merit function method for the NCP, Appl. Math. – J. Chinese Univ., 25 (2010), 379-390.
doi: 10.1007/s11766-010-2179-z. |
[19] |
Z. Q. Luo and P. Tseng, A new class of merit functions for the nonlinear complementarity problem, in Complementarity and Variational Problems: State of the Art, eds. M. C. Ferris and J. -S. Pang, SIAM, Philadelphia, (1997), 204–225. |
[20] |
O. L. Mangasarian and M. V. Solodov,
A linearly convergent derivative-free descent method for strongly monotone complementarity problems, Comput. Optim. Appl., 14 (1999), 5-16.
doi: 10.1023/A:1008752626695. |
[21] |
J. S. Pang,
A posteriori error bounds for the linearly-constrained variational inequality problem, Math. Oper. Res., 12 (1987), 474-484.
doi: 10.1287/moor.12.3.474. |
[22] |
J. M. Ortega and W. Rheinboldt,
Iterative Solution of Nonlinear Equations in Several Variables, SIAM, Philadelphia, 2000.
doi: 10.1137/1.9780898719468. |
[23] |
L. Qi, D. Sun and L. G. Zhou,
A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. Program., 87 (2000), 1-35.
|
[24] |
K. Yamada, N. Yamashita and M. Fukushima, A new derivative-free descent method for the nonlinear complementarity problem, in Nonlinear Optimization and Related Topics(eds. G. D. Pillo and F. Giannessi), Kluwer Academic, Dordrecht, 36 (2000), 463–489.
doi: 10.1007/978-1-4757-3226-9_25. |
show all references
References:
[1] |
S. C. Billups, S. P. Drikse and M. C. Soares,
A comparison of algorithm for large scale mixed complementartiy problems, Comput. Optim. Appl., 7 (1977), 3-25.
doi: 10.1023/A:1008632215341. |
[2] |
J.-S. Chen,
The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem, J. Global Optim., 36 (2006), 565-580.
doi: 10.1007/s10898-006-9027-y. |
[3] |
J.-S. Chen, Z. H. Huang and C.-Y. She,
A new class of penalized NCP-functions and its properties, Comput. Optim. Appl., 50 (2011), 49-73.
doi: 10.1007/s10589-009-9315-9. |
[4] |
J.-S. Chen and S. H. Pan,
A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for $P_0$-NCPs, J. Comput. Appl. Math., 220 (2008), 464-479.
doi: 10.1016/j.cam.2007.08.020. |
[5] |
J.-S. Chen and S. H. Pan,
A family of NCP-functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl., 40 (2008), 389-404.
doi: 10.1007/s10589-007-9086-0. |
[6] |
J.-S. Chen, H.-T. Gao and S. H. Pan,
An $R$-linearly convergent derivative-free algorithm for nonlinear complementarity problems based on the generalized Fisher-Burmeister merit function, Comput. Optim. Appl., 232 (2009), 455-471.
doi: 10.1016/j.cam.2009.06.022. |
[7] |
F. Facchinei and J. S. Pang, Finite-dimensional variational inequalities and complementarity problems, Springer Verlag, New York, 2003. Google Scholar |
[8] |
F. Facchinei and J. Soares,
A new merit function for nonlinear complementarity problems and a related algorithm, SIAM J. Optim., 7 (1997), 225-247.
doi: 10.1137/S1052623494279110. |
[9] |
M. C. Ferris and J. S. Pang,
Engineering and economic applications of complementarity problems, SIAM Rev., 39 (1997), 669-713.
doi: 10.1137/S0036144595285963. |
[10] |
C. Geiger and C. Kanzow,
On the resolution of monotone complementarity problems, Comput. Optim. Appl., 5 (1996), 155-173.
doi: 10.1007/BF00249054. |
[11] |
P. T. Harker and J. S. Pang,
Finite dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and applications, Math. Program., 48 (1990), 161-220.
doi: 10.1007/BF01582255. |
[12] |
S. L. Hu, Z. H. Huang and J.-S. Chen,
Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math., 230 (2009), 69-82.
doi: 10.1016/j.cam.2008.10.056. |
[13] |
S. L. Hu, Z. H. Huang and N. Lu,
Smoothness of a class of generalized merit functions for the second-order cone complementarity problem, Pacific J. Optim., 6 (2010), 551-571.
|
[14] |
Z. H. Huang,
The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP, IMA J. Numer. Anal., 25 (2005), 670-684.
doi: 10.1093/imanum/dri008. |
[15] |
Z. H. Huang, L. Qi and D. Sun,
Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$-and monotone LCP, Math. Program., 99 (2004), 423-441.
doi: 10.1007/s10107-003-0457-8. |
[16] |
H. Y. Jiang, M. Fukushima and L. Qi,
A trust region method for solving generalized complementarity problems, SIAM. J. Optim., 8 (1998), 140-157.
doi: 10.1137/S1052623495296541. |
[17] |
C. Kanzow and H. Kleinmichel,
A new class of semismooth Newton method for nonlinear complementarity problems, Comput. Optim. Appl., 11 (1998), 227-251.
doi: 10.1023/A:1026424918464. |
[18] |
L. Y. Lu, Z. H. Huang and S. L. Hu,
Properties of a family of merit functions and a merit function method for the NCP, Appl. Math. – J. Chinese Univ., 25 (2010), 379-390.
doi: 10.1007/s11766-010-2179-z. |
[19] |
Z. Q. Luo and P. Tseng, A new class of merit functions for the nonlinear complementarity problem, in Complementarity and Variational Problems: State of the Art, eds. M. C. Ferris and J. -S. Pang, SIAM, Philadelphia, (1997), 204–225. |
[20] |
O. L. Mangasarian and M. V. Solodov,
A linearly convergent derivative-free descent method for strongly monotone complementarity problems, Comput. Optim. Appl., 14 (1999), 5-16.
doi: 10.1023/A:1008752626695. |
[21] |
J. S. Pang,
A posteriori error bounds for the linearly-constrained variational inequality problem, Math. Oper. Res., 12 (1987), 474-484.
doi: 10.1287/moor.12.3.474. |
[22] |
J. M. Ortega and W. Rheinboldt,
Iterative Solution of Nonlinear Equations in Several Variables, SIAM, Philadelphia, 2000.
doi: 10.1137/1.9780898719468. |
[23] |
L. Qi, D. Sun and L. G. Zhou,
A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. Program., 87 (2000), 1-35.
|
[24] |
K. Yamada, N. Yamashita and M. Fukushima, A new derivative-free descent method for the nonlinear complementarity problem, in Nonlinear Optimization and Related Topics(eds. G. D. Pillo and F. Giannessi), Kluwer Academic, Dordrecht, 36 (2000), 463–489.
doi: 10.1007/978-1-4757-3226-9_25. |






[1] |
Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185 |
[2] |
Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 |
[3] |
Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709 |
[4] |
J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 |
[5] |
Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053 |
[6] |
Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29 |
[7] |
Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133 |
[8] |
Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206 |
[9] |
Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213 |
[10] |
Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020210 |
[11] |
Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065 |
[12] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
[13] |
Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002 |
[14] |
Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263 |
[15] |
Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069 |
[16] |
Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196 |
[17] |
Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184 |
[18] |
Jian Yang, Bendong Lou. Traveling wave solutions of competitive models with free boundaries. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 817-826. doi: 10.3934/dcdsb.2014.19.817 |
[19] |
Mingxin Wang, Qianying Zhang. Dynamics for the diffusive Leslie-Gower model with double free boundaries. Discrete & Continuous Dynamical Systems - A, 2018, 38 (5) : 2591-2607. doi: 10.3934/dcds.2018109 |
[20] |
Yizhuo Wang, Shangjiang Guo. A SIS reaction-diffusion model with a free boundary condition and nonhomogeneous coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1627-1652. doi: 10.3934/dcdsb.2018223 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]