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.
Citation
Discussion Paper Series No.1059, Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan, September, 2003