Find a point inside non-empty difference of ellipsoids

Question

Given two ellipsoids \begin{align}\mathcal{E}_1 &= \{ X \mid X^\top A_1 X + 2B_1^\top X + C_1 \leq 0\}\\\mathcal{E}_2 &= \{ X \mid X^\top A_2 X + 2 B_2^\top X + C_2 \leq 0\}\end{align} are both non-empty, it is possible to test if $\mathcal{E}_1 \subseteq \mathcal{E}_2$. Indeed, by the use of the so called $S$-procedure, $\mathcal{E}_1 \subseteq \mathcal{E}_2\iff\exists \lambda > 0$ such that $$ \begin{bmatrix} A_2 &B_2\\ B_2^\top &C_2\end{bmatrix} \preceq \lambda \begin{bmatrix} A_1 &B_1 \\ B_1^\top &C_1\end{bmatrix}$$ See https://web.stanford.edu/~boyd/cvxbook/.

Question

Assume that $\mathcal{E}_1 \not\subseteq \mathcal{E}_2$. I want to find a point in $\mathcal{E}_1 \setminus \mathcal{E}_2$. How can I do that? I think one should follow the proof of the $S$-procedure (the necessity part) and eventually construct one on those lines. Can someone help?

Edit

This paper might have an answer: Ye, Y. (n.d.). Quadratic Programming Over an Ellipsoid. Encyclopedia of Optimization, 2112–2116. doi:10.1007/0-306-48332-7_408

Answer 1

Define quadratic functions $g_1(X)$ and $g_2(X)$ such that \begin{align}\mathcal{E}_1 &= \{ X \mid g_1(X) \le 0\}\\\mathcal{E}_2 &= \{ X \mid g_2(X) \le 0\}\end{align}

It follows from the definition that you can find a point in $\mathcal{E}_1 \setminus \mathcal{E}_2$ by solving $$\begin{align} \min &\quad -g_2(X)\\\text{s.t.} &\quad g_1(X) \le 0.\end{align}$$ Informally, you find the point in $\mathcal{E}_1$ with the maximum (scaled) distance from the center of $\mathcal{E}_2$. If the optimal value of $-g_2(X) < 0$, then this point is not in $\mathcal{E}_2$, as required.

The problem above is not obviously convex: if $g_1(X)$ is convex, then the objective $-g_1(X)$ is typically not convex.

However, in this special case (and under some technical assumptions) the S-lemma can be used to reformulate this problem as a convex problem!

For details, see Theorem 2.2 in the survey by Pólik and Terlaky, for example. I personally find the lecture notes of lecture 12 provided here very helpful.

---

Edit: As pointed out by C Marius and Mark L. Stone, the approach above does not actually result in a point $X \in \mathcal{E}_1 \setminus \mathcal{E}_2$. Instead, it answers whether such a point exists. I looked further into this, and it turns out you can actually recover a point $X$ after solving the reformulated problem.

In this paper, Tuy and Tuan present the S-lemma as a strong duality theorem for specific non-convex problems, including the one above. In this specific case, we have (ignoring some technical details):

$$\inf_{X\in \mathbb{R}^n} \sup_{\lambda\ge 0} \{-g_2(X) + \lambda g_1(X)\} = \sup_{\lambda\ge 0} \inf_{X\in \mathbb{R}^n} \{-g_2(X) + \lambda g_1(X)\}.$$

The left-hand side is the primal problem, which is equivalent to the optimization problem stated at the top ($g_1(X) \le 0$ is optimal, because otherwise $\lambda \rightarrow \infty$ would send the objective to $+\infty$). The right-hand side is the dual problem, which is equivalent to the convex reformulation mentioned above.

After solving the dual problem (the convex reformulation), we obtain an optimal dual value $\bar{\lambda}$. You then recover a primal solution in a similar way as for linear programming: by using the optimality conditions (Tuy and Tuan, Theorem 3):

$$-\nabla g_2(X) + \bar{\lambda} \nabla g_1(X) = 0 \wedge \bar{\lambda} g_1(X) = 0 \wedge g_1(X) \le 0.$$

---

Example: Consider two ellipses, given by $A_1 = I$, $B_1 = (-1, 0)^\top$, $C_1 = 0$ (blue circle), and $A_2 = I$, $B_1 = 0$, $C_2 = -1$ (red circle)

The dual is given by $$\begin{align} \max_{V, \lambda} &\quad V\\ \text{s.t.} &\quad \begin{bmatrix} \lambda A_1 - A_2 & \lambda B_1 - B_2 \\ (\lambda B_1 - B_2)^\top & \lambda C_1 - C_2 - V \end{bmatrix} \succeq 0 \\ ~&~\lambda \ge 0.\end{align}$$

Solving this SDP yields the solution $V = -3$ and $\bar{\lambda} = 2$. As $V < 0$, there exists an $X \in \mathcal{E}_1 \setminus \mathcal{E}_2$.

If we use the first of the optimality conditions, we have $$-\nabla g_2(X) + \bar{\lambda} \nabla g_1(X) = 2 (\bar{\lambda} A_1 - A_2)X + 2(\bar{\lambda} B_1 - B_2) = 2IX - (-4, 0)^\top = 0,$$ which solves for $\bar{X} = (2,0)^\top$. It is easy to check that the other conditions are also satisfied, which means that $\bar{X}$ is a primal optimal solution. Indeed, $\bar{X} \in \mathcal{E}_1 \setminus \mathcal{E}_2$.

In the picture, the yellow circle corresponds to the ellipse $g_2(X) = -V$. This ellipse intersects $\mathcal{E}_1$ at the maximum (weighted) distance from the center of $\mathcal{E}_2$. Their intersection is exactly the point $\bar{X}$.

I have omitted various technical details, for which I refer to the references.

Answer 2

This is a feasibility problem, find $X$ such that $$X^TA_1 X + 2B_1^TX + C_1 \leq 0, X^T A_2 X + 2 B_2^T X + C_2 \gt 0$$.In general it will be non-convex (although it is convex if $A_1$ is positive semidefinite and $A_2$ is negative semidefinite; however, given mention of "ellipsoid", it seems reasonable to presume that $A_1$ and $A_2$ are both positive semidefinite). It's also a bit tricky due to the strict inequality in the 2nd constraint. In practice, you will need to change that to $$X^T A_2 X + 2 B_2^T X + C_2 +\text{small_positive_number} \ge 0,$$and deal with the possibility of the only (what should be) feasible point requiring a smaller positive number. Alternatively, you could solve a QCQP which is to maximize the LHS (without small_positive_number) of the 2nd constraint, subject to the first constraint; and determine the original problem to be solved if this problem has positive optimal objective function - but this generally involves more computing than solving the original feasibility problem.

In the convex case ($A_1$ positive semidefinite and $A_2$ negative semidefinite, which given my previous remark, seems unlikely to occur, unless $A_2$ is degenerate), you can use a convex QCQP or SOCP solver, and can formulate the problem using a convex optimization tool.

In the non-convex case (which from a practical perspective, you should always be in), you can always try using a local optimizer, and if it succeeds, you're done. However, it could fail even when there truly is a feasible point. In order to "guarantee" finding a feasible value if one exists, you should use a global solver, such as BARON or Gurobi 9.x (which can find global optimum of non-convex quadratics) or CPLEX with optimalitytarget = 3 (if the alternative optimization formulation is used, because that moves the non-convexity from the constraints to the objective function, where it is allowed by CPLEX).