HOMOGENEOUS ALGORITHMS FOR MONOTONE COMPLEMENTARITY PROBLEMS OVER SYMMETRIC CONES

In [24], the author proposed a homogeneous model for standard monotone nonlinear complementarity problems over symmetric cones and show that the following properties hold: (a) There is a path that is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions. (b) Any accumulation point of the path is a solution of the homogeneous model. (c) If the original problem is solvable, then every accumulation point of the path gives (is a finite solution. (d) If the original problem is strongly infeasible, then, under the assumption of Lipschitz continuity, ally accumulation point of the path gives us a finite certificate proving infeasibility. In this paper, we propose a class of algorithms for numerically tracing the path in (a) above. Let r be the rank of the intended Euclidian Jordan algebra. By introducing a parameter 0 >= 0 for quantifying a scaled Lipschitz property of a function, we obtain the following results: (el) The (infeasible) NT method takes O(root r(1 + root r theta) log epsilon(-1)) iterations for tire short-step, and O(r(1 + root r theta) log epsilon(-1)) iterations for the semi-long-arid long-step variants. (e2) The (infeasible) xy method or yx method takes O(root r(1 + root r theta) log epsilon(-1)) iterations for the short-step, O(r(1 + root r theta) log epsilon(-1)) iterations for the semi-long-step, and O(r(1.5)(1 + root r theta) log epsilon(-1)) iterations for the long-step variant. If the original complementarity problem is linear then theta = 0 and the above results achieve the best iteration-complexity bounds known so far for linear or convex quadratic optimization problems over symmetric cones.