Kronecker Product Constraints for Semidefinite Optimization

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.



View Kronecker Product Constraints for Semidefinite Optimization