- A Homogeneous Model for $P_0$ and $P_*$ Nonlinear Complementarity Problems Akiko Yoshise (yoshisesk.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/2003Entry Accepted: 09/30/2003Entry Last Modified: 05/01/2005Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.