zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Using vector divisions in solving the linear complementarity problem. (English) Zbl 1238.65053
Summary: The linear complementarity problem LCP(M,q) is to find a vector z in n satisfying z T (Mz+q)=0, Mz+q0, z0, where M=(m ij ) n×n and q n are given. In this paper, we use the fact that solving LCP(M,q) is equivalent to solving the nonlinear equation F(x)=0 where F is a function from n into itself defined by F(x)=(M+I)x+(M-I)x+(M-I)|x|+q. We build a sequence of smooth functions F ˜(p,x) which is uniformly convergent to the function F(x). We show that, an approximation of the solution of the LCP(M,q) (when it exists) is obtained by solving F ˜(p,x)=0 for a parameter p large enough. Then we give a globally convergent hybrid algorithm which is based on vector divisions and the secant method for solving LCP(M,q). We close our paper with some numerical simulations to illustrate our theoretical results, and to show that this method can solve efficiently large-scale linear complementarity problems.
MSC:
65K05Mathematical programming (numerical methods)
90C33Complementarity and equilibrium problems; variational inequalities (finite dimensions)
65H10Systems of nonlinear equations (numerical methods)
References:
[1]Lemke, C. E.; Howson, J. J. T.: Equilibrium points of bimatrix games, SIAM J. Appl. math. 12, 413-423 (1964) · Zbl 0128.14804 · doi:10.1137/0112033
[2]Ferris, M. C.; Pang, J. S.: Engineering and economic applications of complementarity problems, SIAM rev. 39, 669-713 (1997) · Zbl 0891.90158 · doi:10.1137/S0036144595285963
[3]Rambeerich, N.; Tangman, D. Y.; Bhuruth, A.: Exponential time integration for fast element solution of some financial engineering problems, J. comput. Appl. math. 224, 668-678 (2009) · Zbl 1154.91472 · doi:10.1016/j.cam.2008.05.047
[4]Cottle, R. W.; Dantzig, G. B.: A life in mathematical programming, Math. program. 105, 1-8 (2006)
[5]Lemke, C. E.: Bimatrix equilibrium points and mathematical programming, Manage. sci. 11, 681-689 (1965) · Zbl 0139.13103
[6]Samelson, H.; Thrall, R. M.; Wesler, O.: A partition theorem for Euclidean n-space, Proc. amer. Math. soc. 9, 805-807 (1958) · Zbl 0117.37901 · doi:10.2307/2033091
[7]Ingleton, A. W.: A problem in linear inequalities, Proc. lond. Math. soc. (3) 16, 519-536 (1966) · Zbl 0166.03005 · doi:10.1112/plms/s3-16.1.519
[8]Murty, K. G.: On a characterization of P-matrices, SIAM J. Appl. math. 20, 378-383 (1971) · Zbl 0224.90034 · doi:10.1137/0120041
[9]Murty, K. G.: On the number of solutions to the complementarity problem and spanning properties of complementary cones, Linear algebra appl. 5, 65-108 (1972) · Zbl 0241.90046 · doi:10.1016/0024-3795(72)90019-5
[10]L.T. Watson, A variational approach to the linear complementarity problem, Doctoral Dissertation, Dept. of Mathematics, University of Michigan, Ann Arbor, MI, 1974.
[11]Kelly, L. M.; Watson, L. T.: Q-matrices and spherical geometry, Linear algebra appl. 25, 175-189 (1979) · Zbl 0421.90071 · doi:10.1016/0024-3795(79)90017-X
[12]Cottle, R. W.; Pang, J. S.; Stone, R. E.: The linear complementarity problem, (1992) · Zbl 0757.90078
[13]Fiedler, M.; Ptak, V.: On matrices with non-positive off-diagonal elements and positive principal minors, Czechoslovak math. J. 12, 382-400 (1962) · Zbl 0131.24806
[14]Harker, P. T.; Pang, J. S.: Finite-dimensional variational inequality and nonlinear complementarity problems, a survey of theory, algorithms and applications, Math. program. 48, 161-220 (1990) · Zbl 0734.90098 · doi:10.1007/BF01582255
[15]Kojima, M.; Megido, N.; Noma, T.; Yoshise, A.: A unified approach to interior point algorithms for linear complementarity problems, Lecture notes in computer science 538 (1991) · Zbl 0766.90077
[16]Cho, G. M.; Kim, M. K.; Lee, Y. H.: Complexity of large-update interior point algorithm for P*(κ) linear complementarity problems, Comput. math. Appl. 53, 101-128 (2007) · Zbl 1135.90410 · doi:10.1016/j.camwa.2006.12.004
[17]Cho, G. M.: A new large-update interior point algorithm for P*(κ) linear complementarity problems, J. comput. Appl. math. 216, 265-278 (2008) · Zbl 1140.90043 · doi:10.1016/j.cam.2007.05.007
[18]Wang, G. Q.; Bai, Y. Q.: Polynomial interior-point algorithms for P*(κ) linear complementarity problems, J. comput. Appl. math. 233, 248-263 (2009) · Zbl 1183.65072 · doi:10.1016/j.cam.2009.07.014
[19]Elfoutayeni, Y.; Khaladi, M.: A new interior point method for linear complementarity problem, Appl. math. Sci. 4, 3289-3306 (2010)
[20]Liu, L.; Li, S.: A new kind of simple kernel function yielding good iteration bounds for primal–dual interior-point methods, J. comput. Appl. math. 233, 2944-2955 (2011) · Zbl 1211.90288 · doi:10.1016/j.cam.2010.12.012
[21]Kim, M. K.; Cho, G. M.: Interior point algorithm for P* nonlinear complementarity problems, J. comput. Appl. math. 235, 3751-3759 (2011) · Zbl 1225.65065 · doi:10.1016/j.cam.2011.01.021
[22]Murty, K. G.: Linear complementarity, linear and nonlinear programming, (1988)
[23]Schafer, Uwe: On the modulus algorithm for the linear complementarity problem, Oper. res. Lett. 32, 350-354 (2004) · Zbl 1148.90343 · doi:10.1016/j.orl.2003.11.004
[24]Van Bokhoven, W. M. G.: Piecewise-linear modelling and analysis, (1981)
[25]Ortega, J. M.; Rheinboldt, W. C.: Iterative solution of nonlinear equations in several variables, Classics appl. Math. (2000)
[26]Shi, Yixun: Using vector divisions in solving nonlinear systems of equations, Int. J. Contemp. math. Sci. 3, 753-759 (2008) · Zbl 1162.65349 · doi:http://www.m-hikari.com/ijcms-password2008/13-16-2008/shiyixunIJCMS13-16-2008.pdf
[27]Harker, P. T.; Pang, J. S.: A damped-Newton method for the linear complementarity problem, Lect. appl. Math. 26, 265-284 (1990) · Zbl 0699.65054