[Math] Finding the maximum volume inscribed ellipsoid using CVX

convex optimizationcvxellipsoidsMATLABoptimization

I am trying to use the CVX package in Matlab to find the largest inscribed ellipsoid for a convex set of points. I was also able to get the example from this link running.

[Step 1] This is how the optimization problem is formulated in the sample Matlab code: 

% formulate and solve the problem  
cvx_begin  
    variable B(n,n) symmetric  
    variable d(n)  
    maximize( det_rootn( B ) )  
    subject to  
       for i = 1:m  
           norm( B*A(i,:)', 2 ) + A(i,:)*d <= b(i);  
       end
cvx_end

[Step 2] To plot the inner ellipsoid the sample MATLAB code suggests:

% make the plots
noangles = 200;
angles   = linspace( 0, 2 * pi, noangles );
ellipse_inner  = B * [ cos(angles) ; sin(angles) ] + d * ones(1, noangles);
plot( ellipse_inner(1,:), ellipse_inner(2,:), 'r--' );

My question is, how can I change the formulation in [Step 1] so that the ellipsoid matrix 'B' directly captures the orientation and shape of the inscribed ellipsoid without requiring (what I think is) an affine transformation from step [Step 2]?

As of now, if I plot an ellipsoid using the variable 'B' directly (using the Ellipse_plot tool from Matlab File Exchange), it is not aligned with the convex polygon!
Misaligned ellipsoid image link

Best Answer

$B$ is not the matrix $Q$ in a form $(x-d)^TQ^{-1}(x-d)\leq 1$ but a factor of it. This transformation (or something similiar) is required to arrive at a convex problem.

You want $a^Tx \leq b$ for all $(x-d)^TQ^{-1}(x-d)\leq 1$ which is equivalent to $a^T(z+d) \leq b$ for all $z^TQ^{-1}z\leq 1$ which is equivalent to $a^T(B^Ty+d) \leq b$ for all $y^Ty\leq 1$ where $Q = BB^T$. Now maximize over $y$ and the constraint ends up at $\||Ba\|| + a^Td \leq b$

Related Question