Symmetric Kronecker Products and
Uniqueness and Existence of search directions for semidefinite programming (SDP)
Levent Tuncel and Henry Wolkowicz (speaker)
Dept. Combinatorics and Optimization
University of Waterloo
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 matrix product
SX at the current iterate.
The second is a centrality condition given first
by Monteiro-Zanjacomo and then improved by Monteiro-Todd.
In this talk, 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 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.