×

A new continuation method for complementarity problems with uniform P- functions. (English) Zbl 0673.90084

This paper formulates the (nonlinear) complementarity problem relative to a continuous mapping f as a problem of solving a system of equations defined by a particular mapping F from \(R_+^{2n}\) to \(R^ n_+\times R^ n\). It is shown that when f is a uniform P-function, the mapping F is a homeomorphism of \(R_+^{2n}\) to \(R^ n_+\times R^ n\). This forms the foundation of a continuation method for tracing the solution curve of the one-parameter family of systems of equations \(F(x,y)=tF(x^ 0,y^ 0)\) from an arbitrary point \((x^ 0,y^ 0)\in R_+^{2n}\) and \(t=1\) to \(t=0\).
Reviewer: R.Cottle

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Allgower and K. Georg, ”Simplicial and continuation methods for approximating fixed points and solution to systems of equations,”SIAM Review 22 (1980) 28–85. · Zbl 0432.65027 · doi:10.1137/1022003
[2] R.W. Cottle, ”Nonlinear programs with positively bounded Jacobians,”SIAM Journal on Applied Mathematics 14 (1966) 147–158. · Zbl 0158.18903 · doi:10.1137/0114012
[3] G.B. Dantzig and R.W. Cottle, ”Positive (semi-definite) matrices and mathematical programming,” Report ORC 63-18, (RR) 13, University of Berkeley (California, 1963). · Zbl 0178.22801
[4] B.C. Eaves, ”The linear complementarity problem,”Management Science 17 (1971) 612–634. · Zbl 0228.15004 · doi:10.1287/mnsc.17.9.612
[5] S. Eilenberg and N. Steenrod,Foundation of Algebraic Topology (Princeton University Press, Princeton, New Jersey, 1952). · Zbl 0047.41402
[6] A.V. Fiacco and G.P. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (John Wiley, New York, 1968). · Zbl 0193.18805
[7] M. Kojima, ”A Unification of the existence theorems of the nonlinear complementarity problem,”Mathematical Programming 9 (1975) 257–277. · Zbl 0347.90039 · doi:10.1007/BF01681350
[8] M. Kojima, S. Mizuno and A. Yoshise, ”A primal-dual interior point algorithm for linear programming,” to appear in: N. Megiddo, ed.,Research Issues in Linear Programming: Proceedings of the Asilomar Conference (Springer-Verlag, Berlin). · Zbl 0708.90049
[9] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementarity problems,” to appear inMathematical Programming. · Zbl 0676.90087
[10] C.E. Lemke, ”Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1965) 681–689. · Zbl 0139.13103 · doi:10.1287/mnsc.11.7.681
[11] L. McLinden, ”The complementarity problem for maximal monotone multifunctions,” Chapter 17 in: R.W. Cottle, F. Giannessi and J.L. Lions, eds.,Variational Inequalities and complementarity problems (John Wiley & Sons, New York, 1980) pp. 251–270. · Zbl 0499.90073
[12] L. McLinden, ”An analog of Moreau’s proximation theorem (with application to the nonlinear complementarity problem,”Pacific Journal of Mathematics 88 (1980) 101–161. · Zbl 0403.90081
[13] N. Megiddo, ”Pathways to the optimal set in linear programming,”Proceedings of the 6th Mathematical Programming Symposium of Japan (Nagoya, Japan, 1986) 1–35.
[14] J.J. Moré, ”Coercivity conditions in nonlinear complementarity problems,”SIAM Review 16 (1974) 1–15. · Zbl 0272.65041 · doi:10.1137/1016001
[15] J.J. Moré, ”Class of functions and feasibility conditions in nonlinear complementarity problem,”Mathematical Programming 6 (1974) 327–338. · Zbl 0291.90059 · doi:10.1007/BF01580248
[16] J.M. Ortega and W.C. Rheinboldt,Iterative Solutions of Nonlinear Equations of Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046
[17] K. Tanabe, ”Complementarity-enforcing centered Newton method for linear programming: Global method,” inNew Method for Linear Programming, The Institute of Statistical Mathematics Cooperative Research Reprt 5, The Institute of Statistical Mathematics (Tokyo, 1987).
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.