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

Yu-Lin Chang; Jein-Shan Chen; Jia Wu

doi:10.3934/jimo.2013.9.153

Article Contents

2013, Volume 9, Issue 1: 153-169. Doi: 10.3934/jimo.2013.9.153

This issue Previous Article Scalarization of approximate solution for vector equilibrium problems Next Article A perturbation approach for an inverse linear second-order cone programming

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
2.
School of Mathematical Sciences, Dalian University of Technology, Dalian 116024

Received: May 2011

Revised: May 2012

Published: January 2013

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 49K30, 65K05, 90C33.

Citation:

Related Papers

Cited by

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 $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-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.