# Maximum area ellipse that does not include a set of points

I'm interested in finding the maximum area ellipse that does not cover some points $\mathbf{p}_i$ and that is centered at the origin. Hence, ideally I'd like to solve this optimization problem: $$\begin{array}{rl} \operatorname{maximize} & \det \boldsymbol \Sigma \\ \operatorname{subject to} & \boldsymbol \Sigma \succeq \mathbf{0} \\ & \mathbf{p}_i^T \boldsymbol \Sigma^{-1} \mathbf{p}_i \ge 1 \quad \forall i \end{array}$$ The ellipse would be thus defined by the equation $\mathbf{p}_i^T \boldsymbol \Sigma^{-1} \mathbf{p}_i = 1$. Is there a known/reliable method to solve such a problem (with many $\mathbf{p}_i$)?

What I've tried: Substituting $\boldsymbol \Omega=\boldsymbol \Sigma^{-1}$ doesn't help: $$\begin{array}{rl} \operatorname{minimize} & \det \boldsymbol \Omega \\ \operatorname{subject to} & \boldsymbol \Omega \succeq \mathbf{0} \\ & \mathbf{p}_i^T \boldsymbol \Omega\,\mathbf{p}_i \ge 1 \quad \forall i \end{array}$$ The constraints are nice and convex (linear matrix inequality and a set of scalar linear inequalities), the problem is the objective function which is concave, hence no go.

You can give a sort of estimate to the solution by replacing the objective with $\operatorname{tr}\boldsymbol\Omega$; this would make the objective linear and would also be equivalent (at least in the 2D case) to maximizing $\displaystyle\frac{\det\boldsymbol\Sigma}{\operatorname{tr}\boldsymbol\Sigma}$, which is kind of similar, but not really the same.

Also, my gut tells me that the optimal ellipse should cross three of the $\mathbf{p}_i$ points. This implies that you could find the optimum by enumerating all sets of three points, fitting an ellipse through them (if possible), checking if all other points fall outside, and keeping the ellipse with the largest area. For pathological cases you could then also check all combinations of two points by fitting the maximum area ellipse passing through them...

The problem with this approach is that: (a) I don't know if it is in fact optimal, it's merely a gut feeling (b) I don't like it, it's sort of brute force and it has $\Theta(n^4)$ time complexity.

Any suggestions?

EDIT: As MvG pointed out, the solution to the problem is unbounded. So let us consider the additional constraint $\boldsymbol\Sigma\preceq\sigma\mathbf{I}$ (equivalently $\boldsymbol\Omega\succeq\frac{\mathbf{I}}{\sigma}$)

-

Hmmm, you are right. But I admit I'm not really interested in an unbounded solution, so let me change the problem a bit, let's assume you have a bound on the maximum axis length, i.e. a constraint of the form $\boldsymbol\Sigma \preceq \sigma \mathbf{I}$ how would that change matters? – horqat Jul 31 '14 at 20:43