A P*-Nonlinear Complementarity Problem as a generalization of the P*-Linear Complementarity Problem is considered. We show that the long-step version of the homogeneous self-dual interior-point algorithm could be used to solve such a problem. | Yugoslav Journal of Operations Research 12 (2002), Number 1, 17-48 LONGHOMOGENEOUS S INTERIORLONG-STEP HOMOGENEOU INTERIOR-POINT ALGORITHM FOR THE P* -NONLINEAR COMPLEMENTARITY PROBLEMS PROBLEMS* Goran LE[AJA Department of Mathematics and Computer Science Georgia Southern University Statesboro, USA Abstract: A P* -Nonlinear Complementarity Problem as a generalization of the P* Linear Complementarity Problem is considered. We show that the long-step version of the homogeneous self-dual interior-point algorithm could be used to solve such a problem. The algorithm achieves linear global convergence and quadratic local convergence under the following assumptions: the function satisfies a modified scaled Lipschitz condition, the problem has a strictly complementary solution, and certain submatrix of the Jacobian is nonsingular on some compact set. Keywords: P* -nonlinear complementarity problem, homogeneous interior-point algorithm, wide neighborhood of the central path, polynomial complexity, quadratic convergence. 1. INTRODUCTION The nonlinear complementarity problem (NCP), as described in the next section, is a framework which can be applied to many important mathematical programming problems. The Karush-Kuhn-Tucker (KKT) system for the convex optimization problems is a monotone NCP. Also, the variational inequality problem can be formulated as a mixed NCP (see Farris and Pang [6]). The linear complementarity problem (LCP), a special case of NCP, has been studied extensively. For a comprehensive treatment of LCP see the monograph of Cottle et al. [4]. * Some results contained in this paper were first published in the author's . thesis. Further research on this topic was supported in part by Georgia Southern Faculty Research Subcommittee Faculty Research Grant. AMS subject classification: 90C05, 65K05. 18 G. Le{aja / Long-Step Homogeneous Interior-Point Algorithm The interior-point methods, originally developed for the linear programming problem (LP), have
