A smoothing conjugate gradient algorithm for nonlinear complementarity problems

Abstract

A PRP-type smoothing conjugate gradient method for solving large scale nonlinear complementarity problems (NCP( F )) is proposed. At each iteration, two Armijo line searches are performed, which guarantees the positive property of the smoothing parameter and minimizes the merit function formed by Fischer-Burmeister function, respectively. Global convergence is studied when F: R ⁿ → R ⁿ is a continuously differentiable P ₀+R ₀ function. Numerical results show that the method is efficient.

Keywords

Nonlinear complementarity / conjugate gradient / global convergence / Fischer-Burmeister function

References

[1] Ahn B.H.. Iterative methods for linear complementarity problem with upperbounds and lowerbounds. Mathematical Programming, 1983, 26: 265-315.

[2] Chen B., Harker P.T.. A non-interior-point continuation method for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications, 1993, 14(4): 1168-1190.

[3] Chen C., Mangasarian O.L.. A class of smoothing functions for nonlinear and mixed complementarity problems. Computational Optimization and Applications, 1996, 5(2): 97-138.

[4] Chen X., Ye Y.. On homotopy-smoothing methods for boxconstrained variational inequalities. SIAM Journal on Control and Optimization, 1999, 37: 589-616.

[5] Chen X., Ye Y.. On smoothing methods for the P ₀-matrix linear complementarity problem. SIAM Journal on Optimization, 2000, 11: 341-363.

[6] Deluca T., Facchinei F., Kanzow C.. A semismooth equation approach to the solution of nonlinear complementarity problems. Mathmatical Programming, 1996, 75(3): 407-439.

[7] Ferris M.C., Kanzow C., Munson T.S.. Feasible descent algorithms for mixed complementarity problems. Mathematical Programming, 1999, 86(3): 475-497.

[8] Fischer A.. A special Newton-type optimization method. Optimization, 1992, 24(3): 269-284.

[9] Geiger C., Kanzow C.. On the resolution of monotone complementarity problems. Computational Optimization and Applications, 1996, 5(2): 155-173.

[10] Harker P.T., Pang J.S.. A damped-Newton method for the linear complementarity problem. Lectures in Applied Mathematics, 1990, 26: 265-284.

[11] He S.L., Xu C.X.. Infeasible-interior-point algorithm for a class of nonmonotone complementarity problems and its computational complexity. Science in China (Series A ), 2001, 44(3): 338-344.

[12] Ji J., Potra F.A., Huang S.. A predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence. Technical Report 18, 1991, Iowa City: Department of Mathematics, University of Iowa

[13] Kanzow C.. Strictly feasible equation-based methods for mixed complementarity problems. Numerische Mathematik, 2001, 89(1): 135-160.

[14] Kanzow C.. Some noninterior continuation methods for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications, 1996, 17(4): 851-868.

[15] Pardalos P.M., Ye Y., Han C.G., Kaliski J.A.. Solution of P ₀ -matrix linear complementarity problems using a potential reduction algorithm. SIAM Journal on Matrix Analysis and Applications, 1993, 14: 1048-1060.

[16] Ulji, Chen G.Q.. New simple smooth merit function for box constrained variational inequalities and damped Newton type method. Applied Mathematics and Mechanics, 2005, 26(8): 1083-1092.

[17] Xu S., Burke J.V.. A polynomialtime interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques. Mathematical Programming, 1999, 86(1): 91-103.

[18] Xu H., Chang X.W.. Approximate Newton methods for nonsmooth equations. Journal of Optimization Theory and Applications, 1997, 93(2): 373-394.

[19] Xu H., Glover B.M.. New version of the Newton method for nonsmooth equations. Journal of Optimization Theory and Applications, 1997, 93: 395-415.

[20] Xiu N., Zhang J.. Some recent advances in projection-type methods for variational inequalities. Journal of Computational and Applied Mathematics, 2003, 152(1): 559-585.

[21] Yamashita N., Fukushima M.. Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems. Mathematical Programming, 1997, 76(3): 469-491.