Is there a second-order conic relaxation method for the bilinear term $z=xy$?

Question

I hope to find a second-order conic (SOC) relaxation for $z = xy$, but it seems very hard.

Answer 1

The 3x3 moment matrix is $\begin{pmatrix} 1 & x & y\\x & x^2 & xy\\y & xy & y^2\end{pmatrix}$ which is psd and rank-1. Introduce relaxation variables and your semidefinite relaxation is $\begin{pmatrix} 1 & x & y\\x & X_{20} & X_{11}\\y & X_{11} & X_{02}\end{pmatrix}\succeq 0$ (with $z$ thus being $X_{11}$). For this to be psd, all minors have to be psd, so a necessary condition is (i.e. relaxation)

$$\begin{pmatrix} 1 & x\\x & X_{20}\end{pmatrix}\succeq 0,\begin{pmatrix} 1 & y\\y & X_{02}\end{pmatrix}\succeq 0, \begin{pmatrix} X_{20} & X_{11}\\X_{11} & X_{02}\end{pmatrix}\succeq 0$$

A 2x2 semidefinite constraint $\begin{pmatrix} a &b\\b & c\end{pmatrix}\succeq 0$ can be represented with an SOCP by looking at the minors and after an SOCP representation of the quadratic constraint you have $\left|\left|\begin{matrix}2b\\a-c\end{matrix}\right|\right|\leq a + c, a\geq 0, c\geq 0$