On Commutative Class of Search Directions for Linear Programming over Symmetric Cones

Masakazu Muramatsu

The Commutative Class of search directions for semidefinite programming is first proposed by Monteiro and Zhang. In this paper, we investigate the corresponding class of search directions for linear programming over symmetric cones, which is a class of convex optimization problems including linear programming, second-order cone programming, and semidefinite programming as special cases. Complexity results are established for short, semi-long, and long step algorithms. We then propose a subclass of Commutative Class of search directions which has polynomial complexity even in semi-long and long step settings. The last subclass still contains the NT and HRVW/KSH/M directions. An explicit formula to calculate any member of the class is also given.

Report CS-00-02, Dept. of Computer Science, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu-shi, Tokyo, 182-8585 Japan.

Contact: muramatu@cs.uec.ac.jp