1
$\begingroup$

I would like to solve the following optimization problem for a matrix $X$ which is symmetric and positive-semidefinite: $$ \mathrm{maximize} \, \, \, f(X) = \log \mathrm{det} X - k_1 \log(k_2 + a^T X a) \\ \text{subject to} \, \, X \preceq W, $$ for a fixed matrix $W$ and known constants $k_1, k_2 > 0$.

I've tried to make it look like a convex optimization problem, but I haven't suceeded. If convex optimization doesn't work here, are there any kind of optimization algorithms that could be potentially helpful? I'm not an expert on optimization at all, so any kind of guidance or reference is much appreciated. Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ Note that $\log(\det (X)=\Tr(\log(X))$ and you can first formally make a derivative with respect to $X$. $\log(\det X)^\prime_X=X^{-1}$. Derivative $\log(k_2+a^TXa)^\prime_X)=\frac {aa^T}{k_2+a^TXa}$. I doubt the gradient=0 equation can be resolved analytically but you have the way to solve it numerically through some gradient methods. Note that the second term actually depends only on projection $X$ on $a$. So you can factorize $X$. $\endgroup$ – Alexander Vigodner Jul 17 '14 at 22:55
  • 1
    $\begingroup$ There's a simple reason why you can't make it look like a convex optimization problem: it's not convex. :-) But at least it's smooth, so you could conceivably try a projected gradient method, with no guarantee that it will converge to a global optimum. $\endgroup$ – Michael Grant Jul 18 '14 at 15:34
0
$\begingroup$

As I said above in my comment, this is not a convex problem; your objective is the difference between two concave functions. However, you might consider a successive convex approximation approach.

Here's what I mean. I'm going to assume that $W$ is strictly positive definite. It must be, actually, or else your model is infeasible. First set $X_0=W$, and for $i=0,1,2,\dots,...$ do this:

  1. Compute $V_i = \nabla_X k_1 \log (k_2+a^TX_ia) = \frac{k_1}{k_2+a^TX_ia} aa^T$.
  2. Set $X_{i+1}$ to be the solution to the linearized problem: $$\begin{array}{ll} \text{maximize} & \log\det X - \langle V_i, X \rangle \\ \text{subject to} & X \preceq W \end{array}$$
  3. Repeat until $\|X_i-X_{i+1}\|$ is small.

I doubt you can guarantee that this will reach the global optimum, but then again, you can't make such guarantees typically for nonconvex problems anyway. So perhaps this will give you results that are "good enough".

If you use a SDP framework like CVX (disclosure, I wrote this), then the SDP subproblem looks like this:

cvx_begin sdp
    variable X(n,n) symmetric
    maximize( log_det(X) - trace(V'*X) )
    subject to
        X <= W
cvx_end
$\endgroup$
  • $\begingroup$ Thanks! I think there's a very small typo in your gradient, which should be $V_i = k_1 a a^T/(k_2+a^T X_i a)$. Thanks so much for your help and writing CVX, which I've managed to use a few times without having a solid background on convex optimization. $\endgroup$ – user14559 Jul 18 '14 at 17:44
  • $\begingroup$ You're welcome! And thanks for the typo fix. I've edited the answer. $\endgroup$ – Michael Grant Jul 18 '14 at 17:47

Your Answer

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