# Find a point inside non-empty difference of ellipsoids

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

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.

• I may be wrong, but at a first glance I see that the method described in lecture 12 of the provided link, solves the optimization problem, but the result is the minimum value of $-g_2$ on $g_1 \leq 0$, not the point for which this happens. Is this correct? Apr 22 '20 at 9:18
• If $V$ is this optimal value, and $V < 0$, then I think you can show there exists a point you are interested in with $g_1(x)=0$ and $g_2(x)=-V$. That is, the point is in the intersection of two ellipsoids. I imagine there exist alghorithms for this, but I have no experience here. Apr 22 '20 at 12:57
• Isn't finding such a point the "point" of the question? The approaches in my answer, although unfortunately non-convex, do that. Apr 22 '20 at 15:50
• The approach above allows you to answer the question of existence in polynomial time. Finding a feasible point is reduced to solving a system of two quadratic equality constraints. I am guessing that this would be easier than dealing with two non-convex inequalities, but I have to admit I don't know. Apr 22 '20 at 17:04
• Thank you for your time! What I am not very sure thou, is how easy is this (fiding a point) in $\mathbb{R}^n$. Indeed those optimality conditions force 2 quadratic equalities and an inequality, which may be dificult to solve in general ... I think Apr 27 '20 at 18:01

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).

• Testing ellipsoid containment is a convex problem according to Boyds book. Therefore, it can be decided solving a convex optimization problem whether one ellipsoid is contained in the other. I was wondering if in case, say, $\mathcal{E}_1$ is not included in $\mathcal{E}_2$ is easy, in the same spirit, to obtain a point which proves this. Apr 21 '20 at 16:39
• Convexity doesn't know "spirit" and can be a cruel mistress. The (nontrivial) complement of a nonlinear convex region is gernerally non-convex. You are trying to find a feasible point in a non-convex region, that is a non-convex problem. Apr 21 '20 at 16:48