Optimization Online


A Homogeneous Model for $P_0$ and $P_*$ Nonlinear Complementarity Problems

Akiko Yoshise (yoshise***at***sk.tsukuba.ac.jp)

Abstract: The homogeneous model for linear programs is an elegant means of obtaining the solution or certificate of infeasibility and has importance regardless of the method used for solving the problem, interior-point methods or other methods. In 1999, Andersen and Ye generalized this model to monotone complementarity problems (CPs) and showed that most of the desirable properties can be inherited as long as the problem is monotone. However, the strong dependence on monotonicity prevents the model from being extended to more general problems, such as $\Pzero$ or $\Pstar$ CPs. This paper presents a new homogeneous model and corresponding algorithm with the following features: (a) the homogeneous model preserves the $\Pzero$ ($\Pstar$) property if the original problem is a $\Pzero$ ($\Pstar$) CP, (b) the algorithm can be applied to $\Pzero$ CPs starting at a positive point near the central trajectory and does not require any big-${\cal M}$ penalty parameter, (c) the algorithm generates a sequence that approaches feasibility and optimality simultaneously for any $\Pstar$ CP having a complementary solution, and (d) the algorithm solves $\Pstar$ CPs with a strictly feasible point.

Keywords: $P_0$ and $P_*$ complementarity problem, homogeneous algorithm, existence of trajectory, global convergence

Category 1: Complementarity and Variational Inequalities

Citation: Discussion Paper Series No.1059, Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan, September, 2003

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 09/30/2003
Entry Accepted: 09/30/2003
Entry Last Modified: 05/01/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society