0
$\begingroup$

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, enter image description here

$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 17, 2021 at 12:32
  • $\begingroup$ Downvoteers, please correct me something wrong, otherwise, why would I come here? $\endgroup$
    – GPrathap
    Feb 17, 2021 at 12:59
  • $\begingroup$ @user10354138 minimizing volume is one constraint but it should maximize the ellipsoid subject to Ax =b $\endgroup$
    – GPrathap
    Feb 17, 2021 at 13:01
  • $\begingroup$ Take a look at slide 10 of Boyd's presentation. $\endgroup$ Feb 17, 2021 at 13:05
  • 1
    $\begingroup$ @RodrigodeAzevedo thank you so much, that's what I was looking for $\endgroup$
    – GPrathap
    Feb 17, 2021 at 15:49

1 Answer 1

1
$\begingroup$

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:

\begin{equation} P = \{ x \in \mathbb{R}^n \mid a_i^Tx \leq b_i, \; i=1,...,m\} \end{equation} So intention is to find inscribed ellipsoid with maximum volume. Let $\varepsilon$ be the ellipsoid that is to be estimated: \begin{equation} E = \{x \mid x = By + d, y \in \mathbb{R}^n, \left \| y \right \|_2 \leq 1, \; B= B^T \succ 0\}. \end{equation} 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: \begin{equation} \left \| Ba_i \right \| + a_i^Td \leq b_i, \; i=0,...,m \end{equation}

Now we are ready to find the inscribed ellipsoid. \begin{equation}\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} \end{equation}

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,

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .