0

There is a matlab script for finding maximum volume ellipsoid in a polytope described by a number of inequality. However I don't understand what information does the $E$ matrix contains and how can I extract it. To be honest, I don't even understand these 2 ellipsoid equations. I couldn't find any information on this.

Find the maximum volume ellipsoid
$$Ell = \{\,v:\quad v = x + Es, ||s|| \leq 1\}$$
or $$Ell = \{\,v:\quad ||E^{-1}(v-x)|| \leq 1\}$$
inscribing a full-dimensional polytope
$$\{\,v:\quad Av \leq b\}$$
Input: A, b --- defining the polytope
(Optional x0 --- interior point, A*x0 < b)
Output:
x --- center of the ellipsoid, and
E --- matrix defining ellipsoid

user128576
  • 357
  • just in case anyone interested in the script: https://www.mathworks.com/matlabcentral/fileexchange/59395-a-maximum-volume-ellipsoid-finder – user128576 Sep 06 '19 at 16:49
  • 1
    Try https://en.wikipedia.org/wiki/Quadric as a starting point. – amd Sep 06 '19 at 18:51

1 Answers1

0

https://www.math.uni-bielefeld.de/documenta/vol-ismp/24_henk-martin.pdf

Top of page3 explains the equation exactly.
$s$ is the unit ball(centered at origin), and we get the ellipsoid from that using an affine transformation( $E$ ), and we also have to move it's center from origin, so we add $x$.
The $v$ points of the ellipsoid must be in the polytope, so they must satisfy $Av\leq b$.

user128576
  • 357