American Institute of Mathematical Sciences

Advanced
April  2017, 13(2): 531-548. doi: 10.3934/jimo.2016030

The linear convergence of a derivative-free descent method for nonlinear complementarity problems

Wei-Zhe Gu 1, and  Li-Yong Lu 2,,

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

* Corresponding author: Li-Yong Lu

Received  November 2012 Revised  March 2016 Published  May 2016

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

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

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

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

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

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

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

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

[10]

C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems, Comput. Optim. Appl., 5 (1996), 155-173.  doi: 10.1007/BF00249054.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

[22]

J. M. Ortega and W. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, Philadelphia, 2000. doi: 10.1137/1.9780898719468.  Google Scholar

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

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

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

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

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

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

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

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

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

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

[10]

C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems, Comput. Optim. Appl., 5 (1996), 155-173.  doi: 10.1007/BF00249054.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

[22]

J. M. Ortega and W. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, Philadelphia, 2000. doi: 10.1137/1.9780898719468.  Google Scholar

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

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

p = 1.1">Figure 1.  Convergence behavior of "gafni(1)" with p = 1.1
Figure Options

Download full-size image

Download as PowerPoint slide

p = 10">Figure 2.  Convergence behavior of "gafni(1)" with p = 10
Figure Options

Download full-size image

Download as PowerPoint slide

p = 100">Figure 3.  Convergence behavior of "gafni(1)" with p = 100
Figure Options

Download full-size image

Download as PowerPoint slide

θ = 0">Figure 4.  Convergence behavior of "josephy(5)" with θ = 0
Figure Options

Download full-size image

Download as PowerPoint slide

θ = 0.5">Figure 5.  Convergence behavior of "josephy(5)" with θ = 0.5
Figure Options

Download full-size image

Download as PowerPoint slide

θ = 1">Figure 6.  Convergence behavior of "josephy(5)" with θ = 1
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Gaohang Yu. A derivative-free method for solving large-scale nonlinear systems of equations. Journal of Industrial & 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 & 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 & 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 & Management Optimization, 2021  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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Imaging, 2016, 10 (4) : 869-898. doi: 10.3934/ipi.2016025
[14]

Jahnabi Chakravarty, Ashiho Athikho, Manideepa Saha. Convergence of interval AOR method for linear interval equations. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021006
[15]

Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic & Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1
[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 & 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 & 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 & 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 & Imaging, 2013, 7 (2) : 307-340. doi: 10.3934/ipi.2013.7.307
[20]

Herbert Gajewski, Jens A. Griepentrog. A descent method for the free energy of multicomponent systems. Discrete & Continuous Dynamical Systems, 2006, 15 (2) : 505-528. doi: 10.3934/dcds.2006.15.505

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (137)
  • HTML views (471)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences