We consider semidefinite optimization problems that include constraints that G(x) and H(x) are positive semidefinite (PSD), where the components of the symmetric matrices G(x) and H(x) are affine functions of an n-vector x. In such a case we obtain a new constraint that a matrix K(x,X) is PSD, where the components of K(x,X) are affine functions of x and X, and X is an nxn matrix that is a relaxation of xx'. The constraint that K(x,X) is PSD is based on the fact that the Kronecker product of G(x) and H(x) must be PSD. This construction of a constraint based on the Kronecker product generalizes the construction of an RLT constraint from two linear inequality constraints, and also the construction of an SOC-RLT constraint from one linear inequality constraint and a second-order cone constraint. We show how the Kronecker product constraint obtained from two second-order cone constraints can be efficiently used to computationally strengthen the semidefinite programming relaxation of the two-trust-region subproblem.
Dept. of Management Sciences, University of Iowa, Iowa City, IA 52242, June, 2016.