Journal article
Kronecker Product Constraints with an Application to the Two-Trust-Region Subproblem
SIAM journal on optimization, Vol.27(1), pp.368-378
01/2017
DOI: 10.1137/16M1078859
Abstract
We consider semidefinite optimization problems that include constraints of the form $G(x)\succeq 0$ and $H(x)\succeq 0$, where the components of the symmetric matrices $G(\cdot)$ and $H(\cdot)$ are affine functions of $x\in\mathbb{R}^n$. In such a case we obtain a new constraint $K(x,X)\succeq 0$, where the components of $K(\cdot,\cdot)$ are affine functions of $x$ and $X$, and $X$ is an $n\times n$ matrix that is a relaxation of $xx^T$. The constraint $K(x,X)\succeq 0$ is based on the fact that $G(x)\otimes H(x)\succeq 0$, where $\otimes$ denotes the Kronecker product. This construction of a constraint based on the Kronecker product generalizes the construction of a reformation-linearization technique (RLT) constraint from two linear inequality constraints, and also the construction of a second-order cone--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.
Details
- Title: Subtitle
- Kronecker Product Constraints with an Application to the Two-Trust-Region Subproblem
- Creators
- Kurt M Anstreicher
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.27(1), pp.368-378
- DOI
- 10.1137/16M1078859
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Language
- English
- Date published
- 01/2017
- Academic Unit
- Business Analytics; Industrial and Systems Engineering; Computer Science
- Record Identifier
- 9984065987202771
Metrics
7 Record Views