# Determine if a certain convex set is a polytope for algorithmic purposes.

The constraint $$\begin{equation} 1\geq x\land x\geq y\land y\geq z\land z\geq -x-y-z+1\geq 0\land x-z\leq 2 \sqrt{y (-x-y-z+1)} \end{equation}$$ determines a three-dimensional convex set JohnstonAnswer

ConvexSet

The volume of the set is known to be VolumeFormula $$\begin{equation} \frac{1}{576} \left(8-6 \sqrt{2}-9 \sqrt{2} \pi +24 \sqrt{2} \cos ^{-1}\left(\frac{1}{3}\right)\right) \approx 0.00227243, \end{equation}$$ with the boundary area being six times larger.

I would like to know whether or not this set qualifies as a polytope for the purpose of determining the (John) ellipsoids JohnEllipsoids of minimal and maximal volume circumscribing and inscribing the set.

This is because the Mosek python code pythoncode "Inner and outer Löwner-John Ellipsoids" requires the input convex set to be a polytope.

The constraint given at the outset is equivalent to the positive-semidefiniteness of the $$6 \times 6$$ matrix

$$\begin{equation} P= \left( \begin{array}{cccccc} 2 (-x-y-z+1) & z-x & 0 & 0 & 0 & 0 \\ z-x & 2 y & 0 & 0 & 0 & 0 \\ 0 & 0 & 1-x & 0 & 0 & 0 \\ 0 & 0 & 0 & x-y & 0 & 0 \\ 0 & 0 & 0 & 0 & y-z & 0 \\ 0 & 0 & 0 & 0 & 0 & x+y+2 z-1 \\ \end{array} \right) , \end{equation}$$ which appears to be the form required by the python code.

Michal Adamaszek has commented AdamaszekComment that "The Mosek code is intended for the ellipsoid inscribed in a polytope P. If P is convex but not a polytope than it may or may not be possible, depending on if you can rewrite the "for all u" part into something more manageable. It seems that your set has an SDP representation, so at the very least you can get an approximation by sampling sufficiently many u and constraining the corresponding Cu+d to lie in P."

• The description of the set includes a quadratic bound and it can be seen from the plot you attached that it has one curved face, so it is not a polytope. It looks like maybe you can approximate it with a polytope by using the "corners" seen in the plot and it will be good enough for the outer ellipsoid. Nov 20, 2020 at 9:28