# How to find the largest ellipsoid which fits within a convex hull?

I am looking for a mathematical realization of finding the largest ellipsoid which fits within a convex hull. Let's say the ellipsoid is defined as

$$E = \left\{ By+d \mid \left \| y \right \|_2\ \leq 1 \right\}$$

where $$d$$ is the center of the ellipsoid. For a given set of points, corresponding convex hull can be calculated in H-Ref (hyperplane representation), i.e., $$Ax \leq b$$. Thus, the idea is to find the ellipsoid which satisfied these two type of constraints minimizing the volume of the ellipsoid, i.e., $$-\log(\det(A))$$.

Here the problem is I still can't understand the way constraints set should be defined?

In other words,

• You want to minimizes the volume? Surely the infimum is 0 (because once you fit one you can always scale it by any factor $r\in(0,1)$) but is not achievable. Commented Feb 17, 2021 at 12:32
• Downvoteers, please correct me something wrong, otherwise, why would I come here? Commented Feb 17, 2021 at 12:59
• @user10354138 minimizing volume is one constraint but it should maximize the ellipsoid subject to Ax =b Commented Feb 17, 2021 at 13:01
• Take a look at slide 10 of Boyd's presentation. Commented Feb 17, 2021 at 13:05
• @RodrigodeAzevedo thank you so much, that's what I was looking for Commented Feb 17, 2021 at 15:49

Note: thanks to @RodrigodeAzevedo and @ Dominic for sharing valuable information. The answer is based on this

Let's say you are given a set of inequalities that describes by a polytope:

$$$$P = \{ x \in \mathbb{R}^n \mid a_i^Tx \leq b_i, \; i=1,...,m\}$$$$ So intention is to find inscribed ellipsoid with maximum volume. Let $$\varepsilon$$ be the ellipsoid that is to be estimated: $$$$E = \{x \mid x = By + d, y \in \mathbb{R}^n, \left \| y \right \|_2 \leq 1, \; B= B^T \succ 0\}.$$$$ In order to maximize the volume, the condition $$E \subseteq P$$ should be satisfied; this condition can be formed as the following way as a set of inequalities: $$$$\left \| Ba_i \right \| + a_i^Td \leq b_i, \; i=0,...,m$$$$

Now we are ready to find the inscribed ellipsoid. \label{max_volume} \begin{aligned} \min_{B,d} \quad & -\log \det(B)\\ \textrm{s.t.} \quad &\left \| Ba_i \right \| + a_i^Td \leq b_i, \; i=0,...,m \\ & B \succeq 0\\ \end{aligned}

In python, this can be written as follows:

B = cp.Variable((dim,dim), PSD=True)
d = cp.Variable(dim)
constraints = [cp.norm(B@A[i],2)+A[i]@d<=b[i] for i in range(len(A))]
prob = cp.Problem(cp.Minimize(-cp.log_det(B)), constraints)
optval = prob.solve()


For example,