- 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/2003Entry Accepted: 07/24/2003Entry Last Modified: 06/28/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.