Minimum volume of Ellipse

1

I found this code from the library:
here’s the link also: https://bit.ly/3wN1bsX

% Section 8.4.1, Boyd & Vandenberghe “Convex Optimization”
% Almir Mutapcic - 10/05
% (a figure is generated)
%
% Given a finite set of points x_i in R^2, we find the minimum volume
% ellipsoid (described by matrix A and vector b) that covers all of
% the points by solving the optimization problem:
%
% maximize log det A
% subject to || A x_i + b || <= 1 for all i
%
% CVX cannot yet handle the logdet function, but this problem can be
% represented in an equivalent way as follows:
%
% maximize det(A)^(1/n)
% subject to || A x_i + b || <= 1 for all i
%
% The expression det(A)^(1/n) is SDP-representable, and is implemented
% by the MATLAB function det_rootn().

% Generate data
x = [ 0.55 0.0;
0.25 0.35
-0.2 0.2
-0.25 -0.1
-0.0 -0.3
0.4 -0.2 ]’;
[n,m] = size(x);

% Create and solve the model
cvx_begin
variable A(n,n) symmetric
variable b(n)
maximize( det_rootn( A ) )
subject to
norms( A * x + b * ones( 1, m ), 2 ) <= 1;
cvx_end

% Plot the results
clf
noangles = 200;
angles = linspace( 0, 2 * pi, noangles );
ellipse = A \ [ cos(angles) - b(1) ; sin(angles) - b(2) ];
plot( x(1,:), x(2,:), ‘ro’, ellipse(1,:), ellipse(2,:), ‘b-’ );
axis off

But A matrix and b vector doesn’t match to find the rotation angle and major and minor axis of the ellipse. Can you give me any idea for that? I need to get the rotation angle, major and minor axis…

3

Note that the optimization is solving for the inverse of the matrix specifying the ellipsoid.

That is just straightforward math, not a CVX matter, and can be computed using the eigenvalues and eigenvectors of inv(A). The vector b is the center of the ellipsoid. Each sqrt(eigenvalue(inv(A))) is the half length of the ellipsoid axis whose orientation is that of the corresponding eigenvector of inv(A).

If you don’t understand those basics of ellipsoid matrix math and eigenvalue/vectors, then https://math.stackexchange.com/ is a more appropriate place to seek further help

Edit: Whoops. That should be he vector -inv(A)*b is the center of the ellipsoid, as pointed out below by @Michal_Adamaszek

1 Like
4

thanks for the reply. But vector b cannot be the center of the ellipsoid. Checked it practically, even it was outside of the ellipsoid.

5

Let D be the standard unit disk. Your ellipsoid is \{x~:~Ax+b\in D\}, in other words A^{-1}(D-b), so the center is A^{-1}(-b) and the major axes are given by eigenvectors of A^{-1} as @Mark_L_Stone wrote.

1 Like
6

@Michal_Adamaszek Thanks for the correction on the center of the ellipse. I have edited my previous post accordingly.

1 Like