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. 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: SSM Discussion Paper Series 1197, University of Tsukuba

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 03/05/2008
Entry Accepted: 03/05/2008
Entry Last Modified: 03/05/2008

Modify/Update this entry