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.