-

 

 

 




Optimization Online





 

Homogeneous algorithms for monotone complementarity problems over symmetric cones

Yoshise Akiko (yoshise***at***sk.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/2008
Entry Accepted: 03/05/2008
Entry Last Modified: 04/13/2010

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
Mathematical Programming Society