Ellipsoidal calculus


Let us solve a determinant maximization problem. Given two ellipsoids

E1 = {x | xTP1x1}

E2 = {x | xTP2x1}

Find the ellipsoid E = {x | xTPx≤1} with smallest possible volume that contain the union of E1 and E2. By using the fact that the volume of the ellipsoid is proportional to -det P and applying the S-procedure, it can be shown that this problem can be written as

The objective function -det P (which is minimized) is not convex, but monotonic transformations can render this problem convex. One alternative is the logarithmic transform, leading to minimization of -log det P instead. This operator was used in previous version of YALMIP, but is not recommended any more.

Instead, YALMIP uses -(det P)1/m where m is the smallest power of 2 larger than or equal to the dimension of P (hence, for matrices with dimension equal to a power of two, the function gives the geometric mean of the eigenvalues of P). The function (det P)1/m, called geomean2 in YALMIP, can be modelled using semidefinite and second order cones, see [Nesterov and Nemirovskii] for details.

n = 2;
P1 = randn(2);P1 = P1*P1'; % Generate random ellipsoid
P2 = randn(2);P2 = P2*P2'; % Generate random ellipsoid
t = sdpvar(2,1);
P = sdpvar(n,n);
F = set(1 > t > 0);
F = F + set(t(1)*P1-P > 0);
F = F + set(t(2)*P2-P > 0);
sol = solvesdp(F,-geomean2(P));
ellipplot(double(P));hold on;
ellipplot(double(P1));
ellipplot(double(P2));

If you have MAXDET installed and which to use this solver, you must use the dedicated command logdet .This command can not be used any other construction than as an objective function, compared to the detinv operator that can be used as any other variable in YALMIP, since it a so called extended operator. Note that if you use the logdet command, if MAXDET not is installed, YALMIP will use -(det P)1/m as objective function instead. MAXDET and the logdet command will most likely be removed from future versions of YALMIP.

solvesdp(F,-logdet(P));
ellipplot(double(P));hold on;
ellipplot(double(P1));
ellipplot(double(P2));