HOMOTOPY CONTINUATION METHODS FOR NONLINEAR COMPLEMENTARITY-PROBLEMS

• 成果类型: Article
• 署名作者: KOJIMA, M; MEGIDDO, N; NOMA, T
• 署名单位: International Business Machines (IBM); IBM USA; Tel Aviv University; Institute of Science Tokyo; Tokyo Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.16.4.754
• 发表日期: 1991
• 页码: 754-774
• 关键词: polynomial-time algorithm; primal-dual algorithms

摘要

A complementarity problem with a continuous mapping f from R(n) into itself can be written as the system of equations F(x,y) = 0 and (x,y) greater-than-or-equal-to 0. Here F is the mapping from R2n into itself defined by F(x,y) = (x1y1, x2y2,...,x(n)y(n),y-f(x)). Under the assumption that the mapping f is a P0-function, we study various aspects of homotopy continuation methods that trace a trajectory consisting of solutions of the family of systems of equations F(x,y) = t(a,b) and (x,y) greater-than-or-equal-to 0 until the parameter t greater-than-or-equal-to 0 attains 0. Here (a,b) denotes a 2n-dimensional constant positive vector. We establish the existence of a trajectory which leads to a solution of the problem, and then present a numerical method for tracing the trajectory. We also discuss the global and local convergence of the method.