# Minimum volume ellipsoid covering a finite set

Jump to: Source code Text output Plots Library index

    % 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

    Calling sedumi: 39 variables, 24 equality constraints
    ------------------------------------------------------------
    SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
    Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
    Put 2 free variables in a quadratic cone
    eqs m = 24, order n = 27, dim = 48, blocks = 10
    nnz(A) = 66 + 0, nnz(ADA) = 354, nnz(L) = 189
     it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
      0 :            1.05E+00 0.000
      1 :   4.83E-02 3.88E-01 0.000 0.3694 0.9000 0.9000   3.93  1  1  8.7E-01
      2 :  -6.52E-01 1.49E-01 0.000 0.3837 0.9000 0.9000   1.02  1  1  4.1E-01
      3 :  -2.07E+00 4.01E-02 0.000 0.2693 0.9000 0.9000   0.22  1  1  1.7E-01
      4 :  -2.66E+00 2.82E-03 0.000 0.0703 0.9900 0.9900   0.83  1  1  1.3E-02
      5 :  -2.68E+00 5.87E-04 0.000 0.2083 0.9000 0.9000   1.00  1  1  2.7E-03
      6 :  -2.68E+00 2.73E-05 0.000 0.0465 0.9900 0.9900   1.00  1  1  1.4E-04
      7 :  -2.68E+00 7.85E-07 0.000 0.0287 0.9905 0.9900   1.00  1  1  1.0E-05
      8 :  -2.68E+00 1.91E-08 0.000 0.0243 0.9900 0.9820   1.00  1  1  2.4E-07
      9 :  -2.68E+00 3.95E-10 0.000 0.0207 0.9901 0.9900   1.00  2  2  5.2E-09

    iter seconds digits       c*x               b*y
      9      0.1   Inf -2.6839853868e+00 -2.6839853740e+00
    |Ax-b| =   4.4e-09, [Ay-c]_+ =   2.6E-09, |x|=  1.0e+01, |y|=  2.5e+00

    Detailed timing (sec)
       Pre          IPM          Post
    1.000E-02    5.000E-02    1.000E-02
    Max-norms: ||b||=1, ||c|| = 1,
    Cholesky |add|=0, |skip| = 0, ||L.L|| = 61.2392.
    ------------------------------------------------------------
    Status: Solved
    Optimal value (cvx_optval): +2.68399