I'm trying to find a numerical solution to the following optimization problem
$$
\text{maximize } f(M) = \frac{1}{2} \log \det(M) + \log \sum_{i=1}^n \exp \left\{ – \frac{1}{2} x_i^T M x_i + a_i \right\} \\
\text{subject to } M \preceq A,
$$
where $A, x_i, a_i$ are all given. Unfortunately, log-det is concave and log-sum-exp is convex.
Edit: I think some background might help. The origin of the objective function is the following function
$$
f(V) = \sum_{i=1}^n w_i \, \mathcal{N}(x_i | \, 0, V)
$$
where $\mathcal{N}(x_i| \, 0, V)$ is the density of a multivariate normal distribution with mean 0 and covariance matrix $V$ (then I took the log to see if that helped). I basically want to find $V$ that maximizes the expression above subject to a constraint.
Any pointers or references to any algorithm or heuristic would be much appreciated, thanks!
Best Answer
You made mistake taking logariphm from multivariate likelihood. $\log(\det(M)$ should go with the minus sign.Thus everything is convex.Derivative of $\log(det(M)^\prime_M=M^{-1}$. Additionally it must be mulitplier $N$ here. Derivative of $\sum_i x_i^TMx=\sum x_ix_i^T$. So you final optimal solution will be $M= (\sum x_ix_i^T/N)^{-1}$ - the inverse of covariance matrix as it should be.
EDITION. I made mistake because forgot that $M$ is inverse of covariance matrix. So $\log(det(M)$ comes with the correct sign. However, likelihood is a product of exponents and loglikelihood is logarihtm of product of exponents rather the logarithm of sum exponents. So fianlly you jave concave + linear function which has the perfect maximum.
This is a wrong idea to make summation of logarithm of distributions. We have to take the logarithm of product with leads to sum of logarithms.
More precisely the correct way to look for optimal covariance matrix is try to maximize of $\Sigma$ the following mulitvariate loglikelihood $$ \prod_i \frac{1}{\sqrt{(2\pi)^k|\boldsymbol\Sigma|}} \exp\left(-\frac{1}{2}{\mathbf x_i}^T{\boldsymbol\Sigma}^{-1}{\mathbf x_i} \right), $$ If your have weights then $$ \prod_i \frac{1}{\sqrt{(2\pi)^k|\boldsymbol\Sigma|^{w_i}}} \exp\left(-w_i\frac{1}{2}{\mathbf x_i}^T{\boldsymbol\Sigma}^{-1}{\mathbf x_i} \right), $$ Taking logarithm you will get the weighted loglikelihood.