Strengthened Existence and Uniqueness Conditions for Search Directions in Semidefinite Programming

Levent Tuncel (ltuncelmath.uwaterloo.ca)
Henry Wolkowicz (hwolkowiczuwaterloo.ca)

Abstract: Primal-dual interior-point (p-d i-p) methods for Semidefinite Programming (SDP) are generally based on solving a system of matrix equations for a Newton type search direction for a symmetrization of the optimality conditions. These search directions followed the derivation of similar p-d i-p methods for linear programming (LP). Among these, a computationally interesting search direction is the AHO direction. However, in contrast to the LP case, existence and uniqueness of the AHO search direction is not guaranteed under the standard nondegeneracy assumptions. Two different sufficient conditions are known that guarantee the existence and uniqueness independent of the specific linear constraints. The first is given by Shida-Shindoh-Kojima and is based on the semidefiniteness of the symmetrization of the product $SX$ at the current iterate. The second is a centrality condition given by Monteiro-Zanj{\'a}como. In this paper, we revisit and strengthen both of the above mentioned sufficient conditions. We include characterizations for existence and uniqueness in the matrix equations arising from the linearization of the optimality conditions. As well, we present new results on the relationship between the Kronecker product and the {\em symmetric Kronecker product} that arise from these matrix equations. We conclude with a proof that the existence and uniqueness of the AHO direction is a generic property for every SDP problem and extend the results to the general Monteiro-Zhang family of search directions.

Keywords: Semidefinite programming, linear matrix equations, existence and uniqueness, Kronecker product, symmetric Kronecker product, linear operators.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: CORR 2003-20 Department of Combinatorics \& Optimization University of Waterloo Waterloo, Ontario, Canada July, 2003

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 07/24/2003
Entry Accepted: 07/24/2003
Entry Last Modified: 06/28/2004

Modify/Update this entry