Implementation of Primal-Dual Methods for Semidefinite Programming Based on Monteiro and Tsuchiya Newton Directions and their Variants

Renato D. C. Monteiro and Paulo R. Zanjacomo

Monteiro and Tsuchiya \cite{MoTs96-2} have proposed two primal-dual Newton directions for semidefinite programming, referred to as the MT directions, and established polynomial convergence of path following methods based on them. This paper reports some computational results on the performance of interior-point predictor-corrector methods based on the MT directions and a variant of these directions, called the S-Ch-MT direction. We discuss how to compute these directions efficiently and derive their corresponding computational complexities. A main feature of our analysis is that computational formulae for these directions are derived from a unified point of view which entirely avoids the use of Kronecker product. Using this unified approach, we also show that the Alizadeh-Haeberly-Overton (AHO) direction can be computed substantially faster than previously reported in the literature. Our computational results are quite promising. We have observed that the method based on one of the MT directions is as robust as the one based on the AHO direction and that the method based on the S-Ch-MT direction is faster (in terms of flops required to reduce the duality gap below $10^{-6}$) than methods based on the MT directions, the Nesterov-Todd direction, the AHO direction and the HRVW/KSH/M direction.

Several changes were made in the revised version of August, 1997: We have obtained new computational complexities for the S-Ch-MT, the NT and the HRVW/KSH/M directions. To summarize them in what follows, we only list the coefficients $a$ and $b$ that appear in their complexities, which are of the form

a mn^3 + b m^2 n^2.
We have:
            |  a  |  b  |
            |     |     |
S-Ch-MT     | 5/3 |  1  |
            |     |     |
NT          |  1  | 0.5 | 
            |     |     |
HRVW/KSH/M  |  2  |  1  |

The old complexities for these directions were:

            |  a  |  b  |
            |     |     |
S-Ch-MT     |  2  |  1  |
            |     |     |
NT          |  3  | 0.5 |
            |     |     |
HRVW/KSH/M  |  4  | 0.5 |

Note that the NT direction has the fastest complexity among all the directions derived so far!

Contact: [email protected]

School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332. Original version: July, 1997. Revised version: August, 1997.


 [DVI]  [POSTSCRIPT]  [IP PAGE]  [SEARCH AGAIN]