On Primal-Dual Interior Point Methods for Semidefinite Programming

Ming Gu

We discuss a number of issues related to primal-dual interior-point methods based on the Monteiro and Zhang (MZ) family of search directions. This family includes a number of important search directions, such as the AHO direction of Alizadeh, Haeberly and Overton, two HKM directions proposed by several groups of researchers, and the NT direction of Nesterov and Todd.

We first consider a subset in the MZ family to be referred to as the TTT family. The associated Schur complements for directions in the TTT family are symmetric positive definite. We discuss interesting properties of directions in this family and show that these directions include the HKM and the NT directions and can be computed as efficiently.

We then analyze the computation of the AHO direction and directions in the TTT family in finite precision arithmetic. This analysis resolves a number of computational issues related to these methods. Most importantly, it indicates that, with the Schur complement approach, methods based on the AHO direction and the TTT family of directions could be numerically stable if certain coefficient matrices associated with the search directions are well-conditioned, but UNSTABLE otherwise. We present results from our numerical experiments that support this analysis.

CAM report97-12, Department of Mathematics, University of California, Los Angeles, CA 90095-1555, March, 1997

Contact: [email protected]

[PS] [IP PAGE] [SEARCH AGAIN]