| 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 us a finite solution. (d) If the original problem is strongly infeasible, then, under the assumption of Lipschitz continuity, any 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 for quantifying a scaled Lipschitz property of a function, we obtain the following results: (e1) The (infeasible) NT method takes O(√r (1+ √r ; θ) log ε-1) iterations for the short-step, and ε iterations for the semi-long- and long-step variants. (e2) The (infeasible) xy method or yx method takes O(√r (1+ √r ; θ) log ε-1) iterations for the short-step, O(√r (1+ √r ; θ) log ε-1) iterations for the semi-long-step, and O(√r 1.5(1+ √r ; θ) log ε-1) iterations for the long-step variant. If the original complementarity problem is linear then θ = 0 and the above results achieve the best iteration-complexity bounds known so far for linear or convex quadratic optimization problems over symmetric cones. |
|
