In \cite{aYOSHISE06}, 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 $\theta \geq 0$ for quantifying a scaled Lipschitz property of a function, we obtain the following results: (e1) The (infeasible) NT method takes $O(\sqrt{r}(1+\sqrt{r}\;\theta)\log \epsilon^{-1})$ iterations for the short-step, and $O(r(1+\sqrt{r}\;\theta)\log \epsilon^{-1})$ iterations for the semi-long- and long-step variants. (e2) The (infeasible) $xy$ method or $yx$ method takes $O(\sqrt{r}(1+\sqrt{r}\;\theta)\log \epsilon^{-1})$ iterations for the short-step, $O(r(1+\sqrt{r}\;\theta)\log \epsilon^{-1})$ iterations for the semi-long-step, and $O(r^{1.5}(1+\sqrt{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.
Citation
Pacific Journal of Optimization 5(2009)313-337
Article
View Homogeneous algorithms for monotone complementarity problems over symmetric cones