zbMATH — the first resource for mathematics

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.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
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)
The linear complementarity problem as a separable bilinear program. (English) Zbl 0835.90102
Summary: The nonmonotone linear complementarity problem (LCP) is formulated as a bilinear program with separable constraints and an objective function that minimizes a natural error residual for the LCP. A linear- programming-based algorithm applied to the bilinear program terminates in a finite number of steps at a solution or stationary point of the problem. The bilinear algorithm solved 80 consecutive cases of the LCP formulation of the knapsack feasibility problem ranging in size between 10 and 3000, with almost constant average number of major iterations equal to four.

90C33Complementarity and equilibrium problems; variational inequalities (finite dimensions)
90C20Quadratic programming
MINOS; Matlab
Full Text: DOI
[1] K. P. Bennett and O. L. Mangasarian (1993), Bilinear separation of two sets inn-space,Computational Optimization & Applications 2: 207-227. · Zbl 0795.90060 · doi:10.1007/BF01299449
[2] S.-J. Chung (1989), NP-completeness of the linear complementarity problem,Journal of Optimization Theory and Applications 60: 393-399. · Zbl 0632.90072 · doi:10.1007/BF00940344
[3] S.-J. Chung and K. G. Murty (1981), Polynomially bounded ellipsoid algorithms for convex quadratic programming, in O. L. Mangasarian, R. R. Meyer, and S. M. Robinson (eds),Nonlinear Programming 4, pages 439-485, New York, Academic Press. · Zbl 0535.90068
[4] R. W. Cotle, J.-S. Pang, and R. E. Stone (1992).The Linear Complementarity Problem, Academic Press, New York.
[5] J. T. J. Van Eijndhoven (1986), Solving the linear complementarity problem in circuit simulation.SIAM Journal on Control and Optimization,24: 1050-1062. · Zbl 0613.90093 · doi:10.1137/0324062
[6] R. Horst, P. Pardalos, and N. V. Thoai (1994),Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht, Netherlands. · Zbl 0836.90134
[7] R. Horst and H. Tuy (1993),Global Optimization, Springer-Verlag, Berlin. (Second, Revised Edition). · Zbl 0704.90057
[8] Z.-Q. Luo and P. Tseng (1992), Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem.SIAM Journal on Optimization,2: 43-54. · Zbl 0777.49010 · doi:10.1137/0802004
[9] O. L. Mangasarian (1964), Nonlinear programming problems with stochastic objective functions.Management Science,10: 353-359. · Zbl 0995.90603 · doi:10.1287/mnsc.10.2.353
[10] O. L. Mangasarian (1979), Simplified characterization of linear complementarity problems solvable as linear programs.Mathematics of Operations Research,4: 268-273. · Zbl 0443.90106 · doi:10.1287/moor.4.3.268
[11] O. L. Mangasarian and J.-S. Pang (1993), The extended linear complementarity problem.SIAM Journal on Matrix Analysis and Applications 16(2), January 1995. · Zbl 0835.90103
[12] O. L. Mangasarian and J. Ren (1994), New improved error bounds for the linear complementarity problem,Mathematical Programming 66, 1994, 241-255. · Zbl 0829.90124 · doi:10.1007/BF01581148
[13] S. Martello and P. Toth (1987), Algorithms for knapsack problems, in S. Martello, G. Laporte, M. Minoux, and C. Ribeiro (eds.),Surveys in Combinatorial Optimization, Annals of Discrete Mathematics 31, North-Holland, Amsterdam. · Zbl 0611.90078
[14] MathWorks, inc. (1991),PRO-MATLAB for UNIX Computers, The Math Works, Inc., South Natick, MA 01760.
[15] B. A. Murtagh and M. A. Saunders (1983), MINOS 5.0 user’s guide. Technical Report SOL 83.20, Stanford University, December 1983. MINOS 5.4 Release Notes, December 1992.
[16] K. G. Murty (1988),Linear Complementarity, Linear and Nonlinear Programming, Helderman-Verlag, Berlin. · Zbl 0634.90037
[17] J. M. Ortega (1972),Numerical Analysis, A Second Course. Academic Press. · Zbl 0248.65001
[18] J.-S. Pang (1986), Inexact Newton methods for the nonlinear complementarity problem.Mathematical Programming,36(1): 54-71. · Zbl 0613.90097 · doi:10.1007/BF02591989
[19] J.-S. Pang, J. C. Trinkle, and G. Lo (1994), A complementarity approach to a quasistatic rigid body motion problem. Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MD 21218.