ON A NEW HOMOTOPY CONTINUATION TRAJECTORY FOR NONLINEAR COMPLEMENTARITY PROBLEMS

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

21 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)119-146
Journal / PublicationMathematics of Operations Research
Volume26
Issue number1
Online published1 Feb 2001
Publication statusPublished - Feb 2001
Externally publishedYes

Abstract

Most known continuation methods for P0 complementarity problems require some restrictive assumptions, such as the strictly feasible condition and the properness condition, to guarantee the existence and the boundedness of certain homotopy continuation trajectory. To relax such restrictions, we propose a new homotopy formulation for the complementarity problem based on which a new homotopy continuation trajectory is generated. For P0 complementarity problems, the most promising feature of this trajectory is the assurance of the existence and the boundedness of the trajectory under a condition that is strictly weaker than the standard ones used widely in the literature of continuation methods. Particularly, the often-assumed strictly feasible condition is not required here. When applied to P* complementarity problems, the boundedness of the proposed trajectory turns out to be equivalent to the solvability of the problem, and the entire trajectory converges to the (unique) least element solution provided that it exists. Moreover, for monotone complementarity problems, the whole trajectory always converges to a least 2-norm solution provided that the solution set of the problem is nonempty. The results presented in this paper can serve as a theoretical basis for constructing a new path-following algorithm for solving complementarity problems, even for the situations where the solution set is unbounded.

Research Area(s)

  • Complementarity problems, Continuation methods, Homolopy continuation trajectories, P*-functions, P0-functions, Strictly feasible condition