Linear complementarity problems solvable by a single linear program.(English)Zbl 0355.90040
The principal result of this paper is, that the linear complementarity problem in \(\mathbb R^n\):\[Mz+q\geq 0,\;z\geq 0,\;z^T(Mz+q)=0\tag{1}\] has a solution, which can be obtained by solving the linear program \[\{p^Tz\mid Mz+q\geq 0,\;z\geq 0,\;p=r+M^Ts\}=\min! \tag{2}\] where \(M\) satisfies \(MZ_1=Z_2\), \(r^TZ_1+s^TZ_2>0\) and \(Z_1,Z_2\) are \((n,n)\)-matrices of Z-type (real square matrix with non-positive off-diagonal elements). Some earlier papers in this direction with smaller classes of matrices are reviewed, further hints are given, that a number of free boundary problems of fluid mechanics can be solved by solving a problem like (1) with \(M\) a Z-matrix. The paper concludes with two corollaries on finding the least element of a polyhedral set and solving certain quadratic programming problems (in connection with problems of type (1) and (2)).
Reviewer: W. Göpfert
MSC:
| 90C05 | Linear programming |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
Cite
References:
| [1] | L.M. Bregman, ”The method of successive projection for finding a common point of convex sets”,Soviet Mathematics Doklady (transl.) 6 (1965) 688–692. ·Zbl 0142.16804 |
| [2] | L.M. Bregman, ”The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming”,USSR Computational Mathematics and Mathematical Physics (transl.) 7 (1967) 200–217. ·Zbl 0186.23807 ·doi:10.1016/0041-5553(67)90040-7 |
| [3] | R. Chandrasekaran, ”A special case of the complementary pivot problem”,Opsearch 7 (1970) 263–268. |
| [4] | R.W. Cottle, Private communication (April 8, 1975). |
| [5] | R.W. Cottle and R.S. Sacher, ”On the solution of large, structured linear complementarity problems: I”, Tech. Rept. 73-4, Department of Operations Research, Stanford University (1973). ·Zbl 0375.90048 |
| [6] | R.W. Cottle, G.H. Golub and R.S. Sacher, ”On the solution of large, structured linear complementarity problems: III”, Tech. Rept. 74-439, Computer Science Department, Stanford University (1974). ·Zbl 0391.90087 |
| [7] | R.W. Cottle and G.B. Dantzig, ”Complementary pivot theory of mathematical programming”,Linear Algebra and its Applications 1 (1968) 103–125. ·Zbl 0155.28403 ·doi:10.1016/0024-3795(68)90052-9 |
| [8] | R.W. Cottle and A.F. Veinott, ”Polyhedral sets having a least element”,Mathematical Programming 3 (1969) 238–249. ·Zbl 0245.90015 ·doi:10.1007/BF01584992 |
| [9] | C.W. Cryer, ”The method of Christopherson for solving free boundary problems for infinite journal bearings by means of finite differences”,Mathematics Computation 25 (1971) 435–443. ·Zbl 0223.65044 ·doi:10.1090/S0025-5718-1971-0298961-7 |
| [10] | C.W. Cryer, ”The solution of a quadratic programming problem using systematic overrelaxation”,SIAM Journal on Control 9 (1971) 385–392. ·Zbl 0216.54603 ·doi:10.1137/0309028 |
| [11] | C.W. Cryer,Free boundary problems, to appear. ·Zbl 0454.65050 |
| [12] | G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, N.J., 1963). ·Zbl 0108.33103 |
| [13] | I.I. Eremin, ”The relaxation method of solving systems of inequalities with convex functions on the left sides”,Soviet Mathematics Doklady (transl.) 6 (1965) 219–222. ·Zbl 0144.30601 |
| [14] | M. Fiedler and V. Pták, ”On matrices with nonpositive off-diagonal elements and positive principal minors”, CzechoslovakMathematical Journal 12 (1962) 382–400. ·Zbl 0131.24806 |
| [15] | C.E. Lemke, ”Recent results on complementarity problems”, in: J.B. Rosen, O.L. Mangasarian and K. Ritter, eds.,Nonlinear Programming (Academic Press, New York, 1970) pp. 349–384. ·Zbl 0227.90043 |
| [16] | O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New York, 1969). |
| [17] | T.S. Motzkin and I.J. Schoenberg, ”The relaxation method for linear inequalities”,Canadian Journal on Math. 6 (1954) 393–404. ·Zbl 0055.35002 ·doi:10.4153/CJM-1954-038-x |
| [18] | K.G. Murty, ”On the number of solutions to the complementarity problems and spanning properties of complementary cones”,Linear Algebra and its Applications 5 (1972) 65–108. ·Zbl 0241.90046 ·doi:10.1016/0024-3795(72)90019-5 |
| [19] | R. Sacher, ”On the solution of large, structured linear complementarity problems: II”, Tech. Rept. 73-5. Department of Operations Research, Stanford University (1973). |
| [20] | R. Saigal, ”A note on a special linear complementarity problem”,Opsearch 7 (1970) 175–183. |
| [21] | R. Saigal, ”Lemke’s algorithm and a special linear complementarity problem”,Opsearch 8 (1971) 201–208. |
| [22] | R. Saigal, ”On the class of complementary cones and Lemke’s algorithm”,SIAM Journal on Applied Mathematics 23 (1972) 46–60. ·Zbl 0237.90040 ·doi:10.1137/0123006 |
| [23] | A. Tamir, ”Minimality and complementarity properties associated with Z-functions”,Mathematical Programming 7 (1974) 17–31. ·Zbl 0291.90057 ·doi:10.1007/BF01585501 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
