Optimization Online


Kronecker Product Constraints for Semidefinite Optimization

K.M. Anstreicher(kurt-anstreicher***at***uiowa.edu)

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.

Download: [PDF]

Entry Submitted: 06/06/2016
Entry Accepted: 06/06/2016
Entry Last Modified: 06/06/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society