- Homogeneous algorithms for monotone complementarity problems over symmetric cones Yoshise Akiko (yoshisesk.tsukuba.ac.jp) Abstract: 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. Keywords: Complementarity problem, symmetric cone, homogeneous algorithm, interior point method, complexity analysis. Category 1: Linear, Cone and Semidefinite Programming (Other ) Citation: Pacific Journal of Optimization 5(2009)313-337 Download: [PDF]Entry Submitted: 03/05/2008Entry Accepted: 03/05/2008Entry Last Modified: 04/13/2010Modify/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.