# 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 & 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. doi: 10.1007/s10107-002-0349-3. Google Scholar [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. doi: 10.1023/A:1008632215341. Google Scholar [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. doi: 10.1007/s10898-006-9027-y. Google Scholar [4] J-.S. Chen, On some NCP-function based on the generalized Fischer-Burmeister function,, Asia-Pacific Journal of Operational Research, 24 (2007), 401. Google Scholar [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. doi: 10.1007/s10589-007-9086-0. Google Scholar [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. doi: 10.1016/j.cam.2007.08.020. Google Scholar [7] J.-S. Chen, H.-T. Gao and S.-H. Pan, An $R$-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. doi: 10.1016/j.cam.2009.06.022. Google Scholar [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. doi: 10.1016/j.cam.2010.01.004. Google Scholar [9] X. Chen and H. Qi, Cartesian $P$-property and its applications to the semidefinite linear complementarity problem,, Mathematical Programming, 106 (2006), 177. doi: 10.1007/s10107-005-0601-8. Google Scholar [10] F. H. Clarke, "Optimization and Nonsmooth Analysis,", John Wiley and Sons, (1983). Google Scholar [11] E. D. Dolan and J. J. More, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. Google Scholar [12] F. Facchinei, Structural and stability properties of $P_0$ nonlinear complementarity problems,, Mathematics of Operations Research, 23 (1998), 735. doi: 10.1287/moor.23.3.735. Google Scholar [13] F. Facchinei and C. Kanzow, Beyond monotonicity in regularization methods for nonlinear complementarity problems,, SIAM Journal on Control and Optimization, 37 (1999), 1150. doi: 10.1137/S0363012997322935. Google Scholar [14] F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Springer Verlag, (2003). Google Scholar [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. doi: 10.1137/S1052623494279110. Google Scholar [16] M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems,, SIAM J. Rev., 39 (1997), 669. doi: 10.1137/S0036144595285963. Google Scholar [17] A. Fischer, Solution of monotone complementarity problems with locally Lipschitzian functions,, Mathematical Programming, 76 (1997), 513. doi: 10.1007/BF02614396. Google Scholar [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. doi: 10.1007/BF01582255. Google Scholar [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. doi: 10.1093/imanum/dri008. Google Scholar [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. doi: 10.1007/s00245-007-9004-y. Google Scholar [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. doi: 10.1007/s10107-003-0457-8. Google Scholar [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. doi: 10.1137/S1052623495296541. Google Scholar [23] C. Kanzow and H. Kleinmichel, A new class of semismooth Newton method for nonlinear complementarity problems,, Computational Optimization and Applications, 11 (1998), 227. doi: 10.1023/A:1026424918464. Google Scholar [24] C. Kanzow, N. Yamashita and M. Fukushima, New NCP-functions and their properties,, Journal of Optimization Theory and Applications, 94 (1997), 115. doi: 10.1023/A:1022659603268. Google Scholar [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. doi: 10.1007/BF02592192. Google Scholar [26] F. J. Luque, Asymptotic convergence analysis of the proximal point algorithm,, SIAM Journal on Control and Optimization, 22 (1984), 277. doi: 10.1137/0322019. Google Scholar [27] B. Martinet, Perturbation des méthodes d'opimisation,, RAIRO Anal. Numér., 12 (1978), 153. Google Scholar [28] R. Mifflin, Semismooth and semiconvex functions in constrained optimization,, SIAM Journal on Control and Optimization, 15 (1997), 957. Google Scholar [29] J.-S. Pang, A posteriori error bounds for the linearly-constrained variational inequality problem,, Mathematics of Operations Research, 12 (1987), 474. doi: 10.1287/moor.12.3.474. Google Scholar [30] J.-S. Pang, Complementarity problems,, in, (1994), 271. Google Scholar [31] J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms,, SIAM Journal on Optimization, 3 (1993), 443. doi: 10.1137/0803021. Google Scholar [32] L. Qi, A convergence analysis of some algorithms for solving nonsmooth equations,, Mathematics of Operations Research, 18 (1993), 227. doi: 10.1287/moor.18.1.227. Google Scholar [33] L. Qi and J. Sun, A nonsmooth version of Newton's method,, Mathematical Programming, 58 (1993), 353. doi: 10.1007/BF01581275. Google Scholar [34] S. M. Robinson, Strongly regular generalized equations,, Mathematics of Operations Research, 5 (1980), 43. doi: 10.1287/moor.5.1.43. Google Scholar [35] R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM Journal on Control and Optimization, 14 (1976), 877. doi: 10.1137/0314056. Google Scholar [36] R. T. Rockafellar and R. J-B. Wets, "Variational Analysis,", Springer-Verlag Berlin Heidelberg, (1998). doi: 10.1007/978-3-642-02431-3. Google Scholar [37] D. Sun and L. Qi, On NCP-functions,, Computational Optimization and Applications, 13 (1999), 201. doi: 10.1023/A:1008669226453. Google Scholar [38] D. Sun and J. Sun, Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions,, Mathematical Programming, 103 (2005), 575. doi: 10.1007/s10107-005-0577-4. Google Scholar [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. Google Scholar [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. doi: 10.1007/BF02191990. Google Scholar [41] N. Yamashita and M. Fukushima, Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems,, Mathematical Programming, 76 (1997), 469. Google Scholar [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. doi: 10.1137/S105262349935949X. Google Scholar [43] N. Yamashita, J. Imai and M. Fukushima, The proximal point algorithm for the $P_0$ complementarity problem,, in, (2001), 361. Google Scholar

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. doi: 10.1007/s10107-002-0349-3. Google Scholar [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. doi: 10.1023/A:1008632215341. Google Scholar [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. doi: 10.1007/s10898-006-9027-y. Google Scholar [4] J-.S. Chen, On some NCP-function based on the generalized Fischer-Burmeister function,, Asia-Pacific Journal of Operational Research, 24 (2007), 401. Google Scholar [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. doi: 10.1007/s10589-007-9086-0. Google Scholar [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. doi: 10.1016/j.cam.2007.08.020. Google Scholar [7] J.-S. Chen, H.-T. Gao and S.-H. Pan, An $R$-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. doi: 10.1016/j.cam.2009.06.022. Google Scholar [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. doi: 10.1016/j.cam.2010.01.004. Google Scholar [9] X. Chen and H. Qi, Cartesian $P$-property and its applications to the semidefinite linear complementarity problem,, Mathematical Programming, 106 (2006), 177. doi: 10.1007/s10107-005-0601-8. Google Scholar [10] F. H. Clarke, "Optimization and Nonsmooth Analysis,", John Wiley and Sons, (1983). Google Scholar [11] E. D. Dolan and J. J. More, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. Google Scholar [12] F. Facchinei, Structural and stability properties of $P_0$ nonlinear complementarity problems,, Mathematics of Operations Research, 23 (1998), 735. doi: 10.1287/moor.23.3.735. Google Scholar [13] F. Facchinei and C. Kanzow, Beyond monotonicity in regularization methods for nonlinear complementarity problems,, SIAM Journal on Control and Optimization, 37 (1999), 1150. doi: 10.1137/S0363012997322935. Google Scholar [14] F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Springer Verlag, (2003). Google Scholar [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. doi: 10.1137/S1052623494279110. Google Scholar [16] M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems,, SIAM J. Rev., 39 (1997), 669. doi: 10.1137/S0036144595285963. Google Scholar [17] A. Fischer, Solution of monotone complementarity problems with locally Lipschitzian functions,, Mathematical Programming, 76 (1997), 513. doi: 10.1007/BF02614396. Google Scholar [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. doi: 10.1007/BF01582255. Google Scholar [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. doi: 10.1093/imanum/dri008. Google Scholar [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. doi: 10.1007/s00245-007-9004-y. Google Scholar [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. doi: 10.1007/s10107-003-0457-8. Google Scholar [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. doi: 10.1137/S1052623495296541. Google Scholar [23] C. Kanzow and H. Kleinmichel, A new class of semismooth Newton method for nonlinear complementarity problems,, Computational Optimization and Applications, 11 (1998), 227. doi: 10.1023/A:1026424918464. Google Scholar [24] C. Kanzow, N. Yamashita and M. Fukushima, New NCP-functions and their properties,, Journal of Optimization Theory and Applications, 94 (1997), 115. doi: 10.1023/A:1022659603268. Google Scholar [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. doi: 10.1007/BF02592192. Google Scholar [26] F. J. Luque, Asymptotic convergence analysis of the proximal point algorithm,, SIAM Journal on Control and Optimization, 22 (1984), 277. doi: 10.1137/0322019. Google Scholar [27] B. Martinet, Perturbation des méthodes d'opimisation,, RAIRO Anal. Numér., 12 (1978), 153. Google Scholar [28] R. Mifflin, Semismooth and semiconvex functions in constrained optimization,, SIAM Journal on Control and Optimization, 15 (1997), 957. Google Scholar [29] J.-S. Pang, A posteriori error bounds for the linearly-constrained variational inequality problem,, Mathematics of Operations Research, 12 (1987), 474. doi: 10.1287/moor.12.3.474. Google Scholar [30] J.-S. Pang, Complementarity problems,, in, (1994), 271. Google Scholar [31] J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms,, SIAM Journal on Optimization, 3 (1993), 443. doi: 10.1137/0803021. Google Scholar [32] L. Qi, A convergence analysis of some algorithms for solving nonsmooth equations,, Mathematics of Operations Research, 18 (1993), 227. doi: 10.1287/moor.18.1.227. Google Scholar [33] L. Qi and J. Sun, A nonsmooth version of Newton's method,, Mathematical Programming, 58 (1993), 353. doi: 10.1007/BF01581275. Google Scholar [34] S. M. Robinson, Strongly regular generalized equations,, Mathematics of Operations Research, 5 (1980), 43. doi: 10.1287/moor.5.1.43. Google Scholar [35] R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM Journal on Control and Optimization, 14 (1976), 877. doi: 10.1137/0314056. Google Scholar [36] R. T. Rockafellar and R. J-B. Wets, "Variational Analysis,", Springer-Verlag Berlin Heidelberg, (1998). doi: 10.1007/978-3-642-02431-3. Google Scholar [37] D. Sun and L. Qi, On NCP-functions,, Computational Optimization and Applications, 13 (1999), 201. doi: 10.1023/A:1008669226453. Google Scholar [38] D. Sun and J. Sun, Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions,, Mathematical Programming, 103 (2005), 575. doi: 10.1007/s10107-005-0577-4. Google Scholar [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. Google Scholar [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. doi: 10.1007/BF02191990. Google Scholar [41] N. Yamashita and M. Fukushima, Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems,, Mathematical Programming, 76 (1997), 469. Google Scholar [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. doi: 10.1137/S105262349935949X. Google Scholar [43] N. Yamashita, J. Imai and M. Fukushima, The proximal point algorithm for the $P_0$ complementarity problem,, in, (2001), 361. Google Scholar
 [1] Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control & 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 & Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381 [3] Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure & Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791 [4] Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 [5] Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283 [6] Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153 [7] Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 [8] Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79 [9] 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 [10] Liuyang Yuan, Zhongping Wan, Qiuhua Tang. A criterion for an approximation global optimal solution based on the filled functions. Journal of Industrial & Management Optimization, 2016, 12 (1) : 375-387. doi: 10.3934/jimo.2016.12.375 [11] Marek Rychlik. The Equichordal Point Problem. Electronic Research Announcements, 1996, 2: 108-123. [12] Pilar Bayer, Dionís Remón. A reduction point algorithm for cocompact Fuchsian groups and applications. Advances in Mathematics of Communications, 2014, 8 (2) : 223-239. doi: 10.3934/amc.2014.8.223 [13] Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743 [14] Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008 [15] Pierre Frankel. Alternating proximal algorithm with costs-to-move, dual description and application to PDE's. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 545-557. doi: 10.3934/dcdss.2012.5.545 [16] Laetitia Paoli. A proximal-like algorithm for vibro-impact problems with a non-smooth set of constraints. Conference Publications, 2011, 2011 (Special) : 1186-1195. doi: 10.3934/proc.2011.2011.1186 [17] Jie Shen, Jian Lv, Fang-Fang Guo, Ya-Li Gao, Rui Zhao. A new proximal chebychev center cutting plane algorithm for nonsmooth optimization and its convergence. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1143-1155. doi: 10.3934/jimo.2018003 [18] Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145 [19] Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259 [20] Mengmeng Zheng, Ying Zhang, Zheng-Hai Huang. Global error bounds for the tensor complementarity problem with a P-tensor. Journal of Industrial & Management Optimization, 2019, 15 (2) : 933-946. doi: 10.3934/jimo.2018078

2018 Impact Factor: 1.025