3
$\begingroup$

I want to solve the following optimization problem

$$ \text{maximize } f(X) = - \log \mathrm{det}(X+Y) - a^T (X+Y)^{-1} a \\ \text{subject to } X \succeq W, $$ where the design variable $X$ is symmetric positive semidefinite, $W, Y$ are fixed symmetric positive semidefinite matrices, and $a$ is a given vector. The inequality $X \succeq W$ means that $X-W$ is symmetric positive semidefinite.

I was wondering if there's hope to find an analytical solution to either the constrained or unconstrained problem. And if there is none, could I use convex optimization techniques to solve this numerically?

$\endgroup$
  • 1
    $\begingroup$ Are you sure this is what you want to solve? Because $-\log\det(X+Y)$ is convex, and $-a^T(X+Y)^{-1}a$ is concave. So your model is not, in fact, a convex optimization problem. If you dropped the first minus sign, it would be, because that would make the objective function fully concave. $\endgroup$ – Michael Grant May 17 '14 at 19:31
  • $\begingroup$ Thanks! Unfortunately, I think that is what I want to solve. Does it help if write the determinant in terms of the inverse, i.e. $R = (X+Y)^{-1}$? I was thinking about writing $$\text{maximize } f(R) = \log \mathrm{det} R - a^T R a \\ \text{subject to } R \succeq W + Y$$, but I don't know if that would be correct... $\endgroup$ – user14559 May 17 '14 at 20:17
3
$\begingroup$

Make the substitution $Z = (X+Y)^{-1} \Leftrightarrow X = Z^{-1} - Y$, then the problem becomes convex:

$$\text{maximize } \log \mathrm{det}(Z) - a^T Z a \\ \text{subject to } 0 \prec Z \preceq (Y+W)^{-1} $$

$\endgroup$
  • $\begingroup$ Yes, that will do it; well done, @p.s.! I doubt there is an analytic solution to this, but it's readily solved using standard tools. Also, you don't need the $Z\succeq 0$ in there explicitly since the $\log\det$ term will implicitly enforce it. $\endgroup$ – Michael Grant May 17 '14 at 22:30
3
$\begingroup$

Now that @p.s. has shown us how this can be made convex, this can indeed be solved using standard semidefinite programming software.

For instance, this could be solved using my software CVX. Here's the CVX model:

cvx_begin sdp
    variable Z(n,n) symmetric
    maximize(log_det(Z)-a'*Z*a);
    Z <= inv(Y+W);
cvx_end
X = inv(Z) - Y;

This will in turn call an SDP solver, which by default is SDPT3.

Certainly, this will be easy to solve using CVX, but calling SDPT3 directly, if you don't mind a bit of extra coding effort, has a distinct advantage: it can handle the log det term natively. CVX doesn't take advantage of that capability, so it ends up using an iterative method to handle the logarithm. This will make CVX will several times slower even though it is using the same solver!

Another MATLAB-based system that can handle this is YALMIP. I'm not sure it can take advantage of the built-in log-det support of SDPT3.

$\endgroup$
  • $\begingroup$ No problem. The far more important step was to convert it to a convex form. It's downhill from there. $\endgroup$ – Michael Grant May 18 '14 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy