Kronecker Product Constraints for Semidefinite Optimization
Abstract: 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.
Keywords: Semidefinite optimization, nonconvex quadratic programming, trust-region subproblem
Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Category 2: Nonlinear Optimization (Quadratic Programming )
Category 3: Global Optimization (Theory )
Citation: Dept. of Management Sciences, University of Iowa, Iowa City, IA 52242, June, 2016.
Entry Submitted: 06/06/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|