  


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 shortstep, and $O(r(1+\sqrt{r}\;\theta)\log \epsilon^{1})$ iterations for the semilong and longstep variants. (e2) The (infeasible) $xy$ method or $yx$ method takes $O(\sqrt{r}(1+\sqrt{r}\;\theta)\log \epsilon^{1})$ iterations for the shortstep, $O(r(1+\sqrt{r}\;\theta)\log \epsilon^{1})$ iterations for the semilongstep, and $O(r^{1.5}(1+\sqrt{r}\;\theta)\log \epsilon^{1})$ iterations for the longstep variant. If the original complementarity problem is linear then $\theta = 0$ and the above results achieve the best iterationcomplexity 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)313337 Download: [PDF] Entry Submitted: 03/05/2008 Modify/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  