Figure 1.
Convergence behavior of "gafni(1)" with p = 1.1
-
Previous Article
On fractional vector optimization over cones with support functions
- JIMO Home
- This Issue
- Next Article
April
2017, 13(2): 531-548.
doi: 10.3934/jimo.2016030
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.
Keywords:
Nonlinear complementarity problems,
merit function,
derivative-free descent method,
global convergence,
linear convergence.
Mathematics Subject Classification:
Primary: 90C33; Secondary: 65K10.
Citation:
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
![]()
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 $mathbb{R}^{N}$-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. |
| [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 $mathbb{R}^{N}$-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. |
| [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. |
Figure 2.
Convergence behavior of "gafni(1)" with p = 10
Figure 3.
Convergence behavior of "gafni(1)" with p = 100
Figure 4.
Convergence behavior of "josephy(5)" with θ = 0
Figure 5.
Convergence behavior of "josephy(5)" with θ = 0.5
Figure 6.
Convergence behavior of "josephy(5)" with θ = 1
| [1] |
Gaohang Yu. A derivative-free method for solving large-scale nonlinear systems of equations. Journal of Industrial and Management Optimization, 2010, 6 (1) : 149-160. doi: 10.3934/jimo.2010.6.149 |
| [2] |
Dong-Hui Li, Xiao-Lin Wang. A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 71-82. doi: 10.3934/naco.2011.1.71 |
| [3] |
Yigui Ou, Wenjie Xu. A unified derivative-free projection method model for large-scale nonlinear equations with convex constraints. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021125 |
| [4] |
Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2553-2566. doi: 10.3934/jimo.2021080 |
| [5] |
A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial and Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319 |
| [6] |
Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050 |
| [7] |
Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial and Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153 |
| [8] |
Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911 |
| [9] |
Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507 |
| [10] |
Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169 |
| [11] |
Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial and Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381 |
| [12] |
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 |
| [13] |
Ugur G. Abdulla. On the optimal control of the free boundary problems for the second order parabolic equations. II. Convergence of the method of finite differences. Inverse Problems and Imaging, 2016, 10 (4) : 869-898. doi: 10.3934/ipi.2016025 |
| [14] |
Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic and Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1 |
| [15] |
Jahnabi Chakravarty, Ashiho Athikho, Manideepa Saha. Convergence of interval AOR method for linear interval equations. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 293-308. doi: 10.3934/naco.2021006 |
| [16] |
Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial and Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565 |
| [17] |
Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems and Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033 |
| [18] |
Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141 |
| [19] |
Ugur G. Abdulla. On the optimal control of the free boundary problems for the second order parabolic equations. I. Well-posedness and convergence of the method of lines. Inverse Problems and Imaging, 2013, 7 (2) : 307-340. doi: 10.3934/ipi.2013.7.307 |
| [20] |
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 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]