Convex Problems?

Question

Which of the following are convex problems?

• Minimum volume ellipsoid that encloses a convex-hull
• Minimum volume ellipsoid that encloses a polyhedron
• Maximum volume ellipsoid inscribed in a convex-hull
• Maximum volume ellipsoid inscribed in a polyhedron

I know that first and second options are standard convex problem and can be solved with the Lowner-Ellipsoid algorithm. I am wondering about the last two options. I found that they are called John Ellipsoids.

Answer 1

You should be more specific than 'is it a convex problem'. Convexity is often about the specific formulation of a problem. I think you are asking whether there is a known convex formulation of the listed problems.

Slide 3 here answers that question for the last two sets. Parameterize the ellipsoid as $\{Bu+d : ||u||_2 \leq 1 \}$ where $B$ is symmetric positive definite (wlog). For a generic convex set $C$, the maximum volume ellipsoid inscribed in $C$ can be found by solving: $$\max_{B,d} \{ \log \det B : Bu+d \in C \quad \forall u : ||u||_2 \leq 1\} $$ or, with an indicator constraint: $$\max_{B,d} \{ \log \det B : \sup_{||u||_2 \leq 1} I_C(Bu+d) \leq 0 $$ This is a convex problem. The next question is whether this problem can be solved practically. That requires finding a "simple" constraint set where the difficulties are not hidden in an abstract function $I_C$.

The formulation for the maximum volume ellipsoid inscribed in a polyhedron defined by $Ax \leq b$ is given on the slides (log det objective and second order cone constraint).

If $C$ is the convex hull of a finite number of points $c_i$, the feasible set is the polytope $\{(x,\lambda) : x=\sum_i \lambda_i c_i, \; \lambda \geq 0, \; e^T\lambda=1\}$. The constraint $Bu+d \in C \; \forall u : ||u||_2 \leq 1$ is intuitively difficult because for each $u$ it needs to find a matching $\lambda$. There are three solutions that I can think of:

1. Find an H-representation of the convex hull.
2. Replace the unit ball with a finite number of extreme points of the unit ball as an approximation. For an accurate representation, you need more points as the dimension increases.
3. Parameterize $\lambda = Eu+f$, which results in the constraints $Bu+d = \sum_i (Eu+f)_i c_i \; \forall u \in B$, $Eu+f \geq 0 \; \forall u \in B$ and $e^T(Eu+f) = 1 \; \forall u \in B$. You may be getting better results by lifting $\lambda$ to a higher dimension.