Nonsymmetric Search Directions for Semidefinite Programming

Rongqin Sheng and Florian A. Potra

Two nonsymmetric search directions for semidefinite programming, the XZ and ZX search directions, are proposed. They are derived from a nonsymmetric formulation of the semidefinite programming problem. The XZ direction corresponds to the direct linearization of the central path equation $XZ = \nu I,$ while the ZX direction corresponds to $ZX = \nu I$. The XZ and ZX directions are well defined if both $X$ and $Z$ are positive definite matrices, where $X$ may be nonsymmetric. We present an algorithm using the XZ and ZX directions alternately following the Mehrotra predictor-corrector framework. Numerical results show that the XZ/ZX algorithm is, in most cases, faster than the XZ+ZX method of Alizadeh, Overton, and Haeberly (AHO) while achieving similar accuracy.

Preprint ANL/MCS-P692-0997, Mathematics and Computer Science Division, Argonne National Laboratory, September 1997.