What is the convex hull of such a matrix cone?

Question

A matrix cone is in the following form

$$M := \begin{pmatrix} 1 \\ x\end{pmatrix}\begin{pmatrix}1 & x^T\end{pmatrix}$$

where $x \in F := \{x : x \in [l,u]^n \}$. How to express the convex hull of $M$?

Answer 1

Since you didn't provide any context, this is guesswork.

I assume $x = (x_1,\dots,x_n)^T$, where $x_i\in[l,u]$ are real numbers. Then $$ M = \pmatrix{1\\x}\pmatrix{1 & x^T} = \pmatrix{1\\x_1\\\vdots\\x_n}\pmatrix{1&x_1&\cdots&x_n} = \pmatrix{ 1&x_1&x_2&\cdots&x_n \\ x_1 &x_1^2 & x_1 x_2 &\cdots&x_1 x_n \\ x_2 &x_2 x_1 & x_2^2 & \cdots&x_2 x_n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_n& x_n x_1 & x_n x_2 & \cdots &x_n^2 } $$ Now the convex hull of $M$ is probably the convex hull of the columns of this matrix.

Answer 2

The convex hull of the set of rank 1 symmetric matrices is the whole positive semidefinite cone.

Note that $\left[\begin{matrix}1 & x^T \\ x & xx^T\end{matrix}\right] \succeq 0 \iff xx^T-x^TxI\succeq 0$. Additionally, $tr(xx^T) = x^Tx$. So the first condition is $xx^T-tr(xx^T)I\succeq 0$.

A tight relaxation often used in this case is $\{X \mid X\succeq tr(X) I\}$.

However, I am not sure if this is the exact convex hull, and also I am not sure how to incorporate $F$, (since in general $conv(M\cap F) \neq conv(M)\cap conv(F)$).

Answer 3

The convex hull of $C:=\left\{\begin{bmatrix}1 \\ x\end{bmatrix}\begin{bmatrix} 1 \\ x\end{bmatrix}^\top \; : \; x\in\mathbb{R}^n, \; 0\le x \le e \right\}$ is characterized using the completely positive cone. See "On the copositive representation of binaryand continuous nonconvex quadratic programs", Sam Burer, Mathematical Programming, (2009) 120:479–495. https://faculty.fuqua.duke.edu/~psun/Burer.2009.pdf

In a related paper (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.3256&rep=rep1&type=pdf), Burer also characterized the convex hull of $C$ in lower dimensions $n=2,3$, which can be represented using positive semidefinite matrices and reformulation-linearization techniques. These representations are computable, while the convex hull of $C$ in higher dimensions need the completely positive cone, which is computationally hard to optimize over.