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: [email protected]