# American Institute of Mathematical Sciences

January  2013, 9(1): 153-169. doi: 10.3934/jimo.2013.9.153

## Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function

 1 Department of Mathematics, National Taiwan Normal University, Taipei 11677, Taiwan 2 School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

Received  May 2011 Revised  May 2012 Published  December 2012

This paper is devoted to the study of the proximal point algorithm for solving monotone and nonmonotone nonlinear complementarity problems. The proximal point algorithm is to generate a sequence by solving subproblems that are regularizations of the original problem. After given an appropriate criterion for approximate solutions of subproblems by adopting a merit function, the proximal point algorithm is verified to have global and superlinear convergence properties. For the purpose of solving the subproblems efficiently, we introduce a generalized Newton method and show that only one Newton step is eventually needed to obtain a desired approximate solution that approximately satisfies the appropriate criterion under mild conditions. The motivations of this paper are twofold. One is analyzing the proximal point algorithm based on the generalized Fischer-Burmeister function which includes the Fischer-Burmeister function as special case, another one is trying to see if there are relativistic change on numerical performance when we adjust the parameter in the generalized Fischer-Burmeister.
Citation: 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
##### References:
 [1] E. D. Andersen, C. Roos and T. Terlaky, On implementing a primal-dual interior-point method for conic quadratic optimization, Mathematical Programming, 95 (2003), 249-277. doi: 10.1007/s10107-002-0349-3. [2] S. C. Billups, S. P. Dirkse and M. C. Soares, A comparison of algorithms for large scale mixed complementarity problems, Computational Optimization and Applications, 7 (1997), 3-25. doi: 10.1023/A:1008632215341. [3] J.-S. Chen, The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem, Journal of Global Optimization, 36 (2006), 565-580. doi: 10.1007/s10898-006-9027-y. [4] J-.S. Chen, On some NCP-function based on the generalized Fischer-Burmeister function, Asia-Pacific Journal of Operational Research, 24 (2007), 401-420. [5] J.-S. Chen and S.-H. Pan, A family of NCP functions and a desent method for the nonlinear complementarity problem, Computational Optimization and Applications, 40 (2008), 389-404. doi: 10.1007/s10589-007-9086-0. [6] J.-S. Chen and S.-H. Pan, A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for $P_0$-NCPs, Journal of Computational and Applied Mathematics, 220 (2008), 464-479. doi: 10.1016/j.cam.2007.08.020. [7] J.-S. Chen, H.-T. Gao and S.-H. Pan, An $\mathbb{R}^{N}$-linearly convergent derivative-free algorithm for the NCPs based on the generalized Fischer-Burmeister merit function, Journal of Computational and Applied Mathematics, 232 (2009), 455-471. doi: 10.1016/j.cam.2009.06.022. [8] J.-S. Chen, S.-H. Pan and C.-Y. Yang, Numerical comparison of two effective methods for mixed complementarity problems, Journal of Computational and Applied Mathematics, 234 (2010), 667-683. doi: 10.1016/j.cam.2010.01.004. [9] X. Chen and H. Qi, Cartesian $P$-property and its applications to the semidefinite linear complementarity problem, Mathematical Programming, 106 (2006), 177-201. doi: 10.1007/s10107-005-0601-8. [10] F. H. Clarke, "Optimization and Nonsmooth Analysis," John Wiley and Sons, New York, 1983. [11] E. D. Dolan and J. J. More, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213. [12] F. Facchinei, Structural and stability properties of $P_0$ nonlinear complementarity problems, Mathematics of Operations Research, 23 (1998), 735-745. doi: 10.1287/moor.23.3.735. [13] F. Facchinei and C. Kanzow, Beyond monotonicity in regularization methods for nonlinear complementarity problems, SIAM Journal on Control and Optimization, 37 (1999), 1150-1161. doi: 10.1137/S0363012997322935. [14] F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Springer Verlag, New York, 2003. [15] F. Facchinei and J. Soares, A new merit function for nonlinear complementarity problems and a related algorithm, SIAM Journal on Optimazation, 7 (1997), 225-247. doi: 10.1137/S1052623494279110. [16] M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems, SIAM J. Rev., 39 (1997), 669-713. doi: 10.1137/S0036144595285963. [17] A. Fischer, Solution of monotone complementarity problems with locally Lipschitzian functions, Mathematical Programming, 76 (1997), 513-532. doi: 10.1007/BF02614396. [18] P. T. Harker and J.-S. Pang, Finite dimensional variational inequality and nonlinear complementarity problem: a survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), 161-220. doi: 10.1007/BF01582255. [19] 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. [20] Z.-H. Huang and W.-Z. Gu, A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties, Appl. Math. Optim., 57 (2008), 17-29. doi: 10.1007/s00245-007-9004-y. [21] Z.-H. Huang, L. Qi and D. Sun, Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$- and monotone LCP, Mathematical Programming, 99 (2004), 423-441. doi: 10.1007/s10107-003-0457-8. [22] H.-Y. Jiang, M. Fukushima and L. Qietal., A trust region method for solving generalized complementarity problems, SIAM Journal on Control and Optimization, 8 (1998), 140-157. doi: 10.1137/S1052623495296541. [23] C. Kanzow and H. Kleinmichel, A new class of semismooth Newton method for nonlinear complementarity problems, Computational Optimization and Applications, 11 (1998), 227-251. doi: 10.1023/A:1026424918464. [24] C. Kanzow, N. Yamashita and M. Fukushima, New NCP-functions and their properties, Journal of Optimization Theory and Applications, 94 (1997), 115-135. doi: 10.1023/A:1022659603268. [25] T. De Luca, F. Facchinei and C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Mathematical Programming, 75 (1996), 407-439. doi: 10.1007/BF02592192. [26] F. J. Luque, Asymptotic convergence analysis of the proximal point algorithm, SIAM Journal on Control and Optimization, 22 (1984), 277-293. doi: 10.1137/0322019. [27] B. Martinet, Perturbation des méthodes d'opimisation, RAIRO Anal. Numér., 12 (1978), 153-171. [28] R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM Journal on Control and Optimization, 15 (1997), 957-972. [29] J.-S. Pang, A posteriori error bounds for the linearly-constrained variational inequality problem, Mathematics of Operations Research, 12 (1987), 474-484. doi: 10.1287/moor.12.3.474. [30] J.-S. Pang, Complementarity problems, in "Handbook of Global Optimization" (eds. R. Horst and P. Pardalos), Kluwer Academic Publishers, Boston, Massachusetts, (1994), 271-338. [31] J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms, SIAM Journal on Optimization, 3 (1993), 443-465. doi: 10.1137/0803021. [32] L. Qi, A convergence analysis of some algorithms for solving nonsmooth equations, Mathematics of Operations Research, 18 (1993), 227-244. doi: 10.1287/moor.18.1.227. [33] L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathematical Programming, 58 (1993), 353-367. doi: 10.1007/BF01581275. [34] S. M. Robinson, Strongly regular generalized equations, Mathematics of Operations Research, 5 (1980), 43-62. doi: 10.1287/moor.5.1.43. [35] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14 (1976), 877-898. doi: 10.1137/0314056. [36] R. T. Rockafellar and R. J-B. Wets, "Variational Analysis," Springer-Verlag Berlin Heidelberg, 1998. doi: 10.1007/978-3-642-02431-3. [37] D. Sun and L. Qi, On NCP-functions, Computational Optimization and Applications, 13 (1999), 201-220. doi: 10.1023/A:1008669226453. [38] D. Sun and J. Sun, Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions, Mathematical Programming, 103 (2005), 575-581. doi: 10.1007/s10107-005-0577-4. [39] J. Wu and J.-S. Chen, A proximal point algorithm for the monotone second-order cone complementarity problem, Computational Optimization and Applications, 51 (2012), 1037-1063. [40] N. Yamashita and M. Fukushima, On stationary points of the implicitm Lagrangian for nonlinear complementarity problems, Journal of Optimization Theory and Applications, 84 (1995), 653-663. doi: 10.1007/BF02191990. [41] N. Yamashita and M. Fukushima, Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems, Mathematical Programming, 76 (1997), 469-491. [42] N. Yamashita and M. Fukushima, The proximal point algorithm with genuine superlinear convergence for the monotone complementarity problem, SIAM Journal on Optimization, 11 (2000), 364-379. doi: 10.1137/S105262349935949X. [43] N. Yamashita, J. Imai and M. Fukushima, The proximal point algorithm for the $P_0$ complementarity problem, in "Complementarity: Applications, Algorithms and Extensions" (eds. M. C. Ferris et al.), Kluwer Academic Publisher, (2001), 361-379.

show all references

##### References:
 [1] E. D. Andersen, C. Roos and T. Terlaky, On implementing a primal-dual interior-point method for conic quadratic optimization, Mathematical Programming, 95 (2003), 249-277. doi: 10.1007/s10107-002-0349-3. [2] S. C. Billups, S. P. Dirkse and M. C. Soares, A comparison of algorithms for large scale mixed complementarity problems, Computational Optimization and Applications, 7 (1997), 3-25. doi: 10.1023/A:1008632215341. [3] J.-S. Chen, The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem, Journal of Global Optimization, 36 (2006), 565-580. doi: 10.1007/s10898-006-9027-y. [4] J-.S. Chen, On some NCP-function based on the generalized Fischer-Burmeister function, Asia-Pacific Journal of Operational Research, 24 (2007), 401-420. [5] J.-S. Chen and S.-H. Pan, A family of NCP functions and a desent method for the nonlinear complementarity problem, Computational Optimization and Applications, 40 (2008), 389-404. doi: 10.1007/s10589-007-9086-0. [6] J.-S. Chen and S.-H. Pan, A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for $P_0$-NCPs, Journal of Computational and Applied Mathematics, 220 (2008), 464-479. doi: 10.1016/j.cam.2007.08.020. [7] J.-S. Chen, H.-T. Gao and S.-H. Pan, An $\mathbb{R}^{N}$-linearly convergent derivative-free algorithm for the NCPs based on the generalized Fischer-Burmeister merit function, Journal of Computational and Applied Mathematics, 232 (2009), 455-471. doi: 10.1016/j.cam.2009.06.022. [8] J.-S. Chen, S.-H. Pan and C.-Y. Yang, Numerical comparison of two effective methods for mixed complementarity problems, Journal of Computational and Applied Mathematics, 234 (2010), 667-683. doi: 10.1016/j.cam.2010.01.004. [9] X. Chen and H. Qi, Cartesian $P$-property and its applications to the semidefinite linear complementarity problem, Mathematical Programming, 106 (2006), 177-201. doi: 10.1007/s10107-005-0601-8. [10] F. H. Clarke, "Optimization and Nonsmooth Analysis," John Wiley and Sons, New York, 1983. [11] E. D. Dolan and J. J. More, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213. [12] F. Facchinei, Structural and stability properties of $P_0$ nonlinear complementarity problems, Mathematics of Operations Research, 23 (1998), 735-745. doi: 10.1287/moor.23.3.735. [13] F. Facchinei and C. Kanzow, Beyond monotonicity in regularization methods for nonlinear complementarity problems, SIAM Journal on Control and Optimization, 37 (1999), 1150-1161. doi: 10.1137/S0363012997322935. [14] F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Springer Verlag, New York, 2003. [15] F. Facchinei and J. Soares, A new merit function for nonlinear complementarity problems and a related algorithm, SIAM Journal on Optimazation, 7 (1997), 225-247. doi: 10.1137/S1052623494279110. [16] M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems, SIAM J. Rev., 39 (1997), 669-713. doi: 10.1137/S0036144595285963. [17] A. Fischer, Solution of monotone complementarity problems with locally Lipschitzian functions, Mathematical Programming, 76 (1997), 513-532. doi: 10.1007/BF02614396. [18] P. T. Harker and J.-S. Pang, Finite dimensional variational inequality and nonlinear complementarity problem: a survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), 161-220. doi: 10.1007/BF01582255. [19] 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. [20] Z.-H. Huang and W.-Z. Gu, A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties, Appl. Math. Optim., 57 (2008), 17-29. doi: 10.1007/s00245-007-9004-y. [21] Z.-H. Huang, L. Qi and D. Sun, Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$- and monotone LCP, Mathematical Programming, 99 (2004), 423-441. doi: 10.1007/s10107-003-0457-8. [22] H.-Y. Jiang, M. Fukushima and L. Qietal., A trust region method for solving generalized complementarity problems, SIAM Journal on Control and Optimization, 8 (1998), 140-157. doi: 10.1137/S1052623495296541. [23] C. Kanzow and H. Kleinmichel, A new class of semismooth Newton method for nonlinear complementarity problems, Computational Optimization and Applications, 11 (1998), 227-251. doi: 10.1023/A:1026424918464. [24] C. Kanzow, N. Yamashita and M. Fukushima, New NCP-functions and their properties, Journal of Optimization Theory and Applications, 94 (1997), 115-135. doi: 10.1023/A:1022659603268. [25] T. De Luca, F. Facchinei and C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Mathematical Programming, 75 (1996), 407-439. doi: 10.1007/BF02592192. [26] F. J. Luque, Asymptotic convergence analysis of the proximal point algorithm, SIAM Journal on Control and Optimization, 22 (1984), 277-293. doi: 10.1137/0322019. [27] B. Martinet, Perturbation des méthodes d'opimisation, RAIRO Anal. Numér., 12 (1978), 153-171. [28] R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM Journal on Control and Optimization, 15 (1997), 957-972. [29] J.-S. Pang, A posteriori error bounds for the linearly-constrained variational inequality problem, Mathematics of Operations Research, 12 (1987), 474-484. doi: 10.1287/moor.12.3.474. [30] J.-S. Pang, Complementarity problems, in "Handbook of Global Optimization" (eds. R. Horst and P. Pardalos), Kluwer Academic Publishers, Boston, Massachusetts, (1994), 271-338. [31] J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms, SIAM Journal on Optimization, 3 (1993), 443-465. doi: 10.1137/0803021. [32] L. Qi, A convergence analysis of some algorithms for solving nonsmooth equations, Mathematics of Operations Research, 18 (1993), 227-244. doi: 10.1287/moor.18.1.227. [33] L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathematical Programming, 58 (1993), 353-367. doi: 10.1007/BF01581275. [34] S. M. Robinson, Strongly regular generalized equations, Mathematics of Operations Research, 5 (1980), 43-62. doi: 10.1287/moor.5.1.43. [35] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14 (1976), 877-898. doi: 10.1137/0314056. [36] R. T. Rockafellar and R. J-B. Wets, "Variational Analysis," Springer-Verlag Berlin Heidelberg, 1998. doi: 10.1007/978-3-642-02431-3. [37] D. Sun and L. Qi, On NCP-functions, Computational Optimization and Applications, 13 (1999), 201-220. doi: 10.1023/A:1008669226453. [38] D. Sun and J. Sun, Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions, Mathematical Programming, 103 (2005), 575-581. doi: 10.1007/s10107-005-0577-4. [39] J. Wu and J.-S. Chen, A proximal point algorithm for the monotone second-order cone complementarity problem, Computational Optimization and Applications, 51 (2012), 1037-1063. [40] N. Yamashita and M. Fukushima, On stationary points of the implicitm Lagrangian for nonlinear complementarity problems, Journal of Optimization Theory and Applications, 84 (1995), 653-663. doi: 10.1007/BF02191990. [41] N. Yamashita and M. Fukushima, Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems, Mathematical Programming, 76 (1997), 469-491. [42] N. Yamashita and M. Fukushima, The proximal point algorithm with genuine superlinear convergence for the monotone complementarity problem, SIAM Journal on Optimization, 11 (2000), 364-379. doi: 10.1137/S105262349935949X. [43] N. Yamashita, J. Imai and M. Fukushima, The proximal point algorithm for the $P_0$ complementarity problem, in "Complementarity: Applications, Algorithms and Extensions" (eds. M. C. Ferris et al.), Kluwer Academic Publisher, (2001), 361-379.
 [1] Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027 [2] Ram U. Verma. On the generalized proximal point algorithm with applications to inclusion problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381 [3] Guoyong Gu, Junfeng Yang. A unified and tight linear convergence analysis of the relaxed proximal point algorithm. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022107 [4] Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure and Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791 [5] Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066 [6] Wei Liu, Shiji Song, Ying Qiao, Han Zhao, Huachang Wang. The loss-averse newsvendor problem with quantity-oriented reference point under CVaR criterion. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2633-2650. doi: 10.3934/jimo.2021085 [7] Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283 [8] Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 [9] Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153 [10] Mohammad Eslamian, Ahmad Kamandi. A novel algorithm for approximating common solution of a system of monotone inclusion problems and common fixed point problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021210 [11] Tim Hoheisel, Maxime Laborde, Adam Oberman. A regularization interpretation of the proximal point method for weakly convex functions. Journal of Dynamics and Games, 2020, 7 (1) : 79-96. doi: 10.3934/jdg.2020005 [12] Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $O(n)$ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2579-2598. doi: 10.3934/jimo.2021082 [13] Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79 [14] Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 [15] Jian Sun, Haiyun Sheng, Yuefang Sun, Donglei Du, Xiaoyan Zhang. Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021116 [16] Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $k$-means problem†. Journal of Industrial and Management Optimization, 2022, 18 (1) : 411-426. doi: 10.3934/jimo.2020160 [17] Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $k$-means problem with penalty. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2277-2287. doi: 10.3934/jimo.2021067 [18] Jueyu Wang, Chao Gu, Guoqiang Wang. Penalized NCP-functions for nonlinear complementarity problems and a scaling algorithm. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021171 [19] 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 [20] Marek Rychlik. The Equichordal Point Problem. Electronic Research Announcements, 1996, 2: 108-123.

2021 Impact Factor: 1.411