New multiplier method for solving linear complementarity problems

Abstract

A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. By introducing a Lagrangian of LCP(q, M), a new smooth merit function ϑ(x, λ) for LCP(q, M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When M is a P-matrix, the sequence {ϑ(x^k, λ^k)} (where {(x^k, λ^k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations if the solution is degenerate. Numerical results suggest that the method is highly efficient and promising.

Keywords

linear complementarity problem / multiplier method / global linear convergence / finite convergence / 90C33

References

[1] Ferris M. C., Pang J. S. Engineering and economic applications of complementarity problems. SIAM J Review, 1997, 39(4): 669-713.

[2] Facchinei F., Pang J. S. Finite-dimensional Variational Inequalities and Complementarity Problems, 2003, New York: Springer-Verlag, 1-1234.

[3] Isac G. Complementarity Problem, 1992, Berlin: Springer-Verlag, 1-297.

[4] Cottle R. W., Pang J. S., Stone R. E. The Linear Complementarity Problem, 1992, Boston: Academic Press, 1-762.

[5] Xiu N. H., Gao Z. Y. The new advances in methods for complementarity problems. Advances in Mathematics, 1999, 28(3): 193-210.

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

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

[8] Peng J. M., Lin Z. H. A non-interior continuation method for generalized linear complementarity problems. Mathematical Programming, 1999, 86(3): 533-563.

[9] Qi H. D., Liao L. Z. A smoothing Newton method for extended vertical linear complementarity problems. SIAM Journal of Matrix Analysis and Applications, 1999, 21(1): 45-66.

[10] Chen G. Q., Cao B. A new NCP-function for box constrained variational inequalities and a related Newton-type method. Mathematica Numerica Sinica, 2002, 24(1): 91-104.

[11] Eckstein J., Ferris M. C. Smooth methods of multipliers for complementarity problems. Mathematical Programming, 1999, 86(1): 65-90.

[12] Xiu N. H. One step quadratic convergence of noninterior continuation method for NCP. Chinese Science Bulletin, 1999, 44(20): 1858-1862.

[13] Clarke F. H. Optimization and Nonsmooth Analysis, 1983, New York: Wiley, 1-308.