epigraphs for quadratic constraints

Question

I have a constraint of the following form \begin{equation} x^{\top}x + y^{\top}y \leq t \end{equation}

where x, y are vector variables and t is a scalar variable. I can augment the variables x and y, create a variable z and write it as a rotated second order cone constraint: $(1/2, t, z) \in \mathcal{Q}_r$. However, that is not the motivation, and I want to understand when it is alright to use an epigraph formulation with quadratic constraints, and so I will instead rewrite the constraint as follows \begin{equation} \begin{aligned} \theta_1 + \theta_2 &= t \newline x^{\top}x &\leq \theta_1 \newline y^{\top}y &\leq \theta_2 \newline \end{aligned} \end{equation}

If there exists a solution to the second system of equations, then the first inequality must hold. However, the second formulation is a relaxation of the first, where I have replaced equalities with inequalities. It is not clear if such $\theta_1, \theta_2$ where the quadratic inequalities bind, exist.

On a similar note I have a slightly different convex quadratic inequality with $t \neq 0$ \begin{equation} x^{\top}x + a^{\top}x + b \leq t \end{equation} where $a$ and $b$ are constants. I can write it as a rotated second order cone constraint: $(1/2, t -b - a^{\top} x, x) \in \mathcal{Q}_r$. However, once again that is not the motivation, and I want to understand when it is valid to use an epigraph formulation with simple and complex quadratic constraints, \begin{equation} \begin{aligned} \theta_3 + a^{\top}x + b &= t \newline x^{\top}x &\leq \theta_3 \end{aligned} \end{equation}

Answer 1

You can establish equivalence between two sets of constraints by showing that any solution to one set of constraints can be mapped to a solution of the other set of constraints. For instance, if I were to show equivalence of

$$ (1)\quad t \geq \theta_1 + \theta_2,\;\; \theta_1 \geq x^T x,\;\; \theta_2 \geq y^T y $$ and $$ (2)\quad t = \theta_1 + \theta_2,\;\; \theta_1 \geq x^T x,\;\; \theta_2 \geq y^T y $$

I would argue that a solution to (2) is always valid in (1), and that a solution to (1) can be mapped to a solution to (2) by following the search direction $\Delta \theta_1 = 1$ (this relies on $\theta_1$ not appearing anywhere else in the model and hence not affecting the objective function either).

The other ingredient you need to reformulate a constraint such as $t \geq x^T x + y^T y$ is that of function composition. First note that the following reformulation holds in general, $$ t \geq f(g(x)) \quad \Longleftrightarrow \quad t \geq f(\theta_1),\;\; \theta_1 = g(x), $$ and can be used on your example with $g(x) = x^T x$ and $f(g) = g + y^T y$. The issue with this reformulation is that it does not preserve convexity and hence is undesirable in practice. Fortunately, research has gone into characterizing convex relaxations of the decomposed nonconvex form. If, for example, you apply the MOSEK cookbook on function composition on your example, you find that $$t \geq f(\theta_1),\;\; \theta_1 \geq g(x)$$ is a convex relaxation because $f(\theta_1) = \theta_1 + y^T y$ and $g(x) = x^T x$ are convex functions, and that this relaxation is actually an exact representation because $f(\theta_1)$ is nondecreasing on the range of $g(x)$.