# Maximize $\mathrm{logdet}(I+X\Sigma)$

$$\begin{array}{ll}\max\limits_{{X:\,\mathrm{tr}(X)\leq a\\}} \mathrm{logdet}(I+X\Sigma),\end{array}$$

where $$\Sigma=\mathrm{diag}\{\sigma_1,\ldots,\sigma_n\}$$, $$\sigma_i\geq0$$ and $$a>0$$ are given. And $$X\geq 0$$.

Here I am trying to maximize a concave function with a convex constraints. Any hints on how the problem can be solved?

• I've changed the title so that it fits better into the list of new questions. Could you provide a bit of context for this question? For instance: how did you encounter the problem? Have you tried anything yourself? Are there any methods that you expect will/won't work here? – Omnomnomnom Sep 19 '19 at 8:07
• I suspect that the maximizer will be another diagonal matrix in this case. I would try plugging in $$X = \pmatrix{x_1 \\ & \ddots \\ && x_n}$$ (where the blank entries are zero) and maximize using a method like Lagrange multipliers. – Omnomnomnom Sep 19 '19 at 8:11
• @Omnomnomnom, First I tried $n=2$ case for $\Sigma=I$, I can solve this problem using AM-GM, I believe it can be generalized to higher dimensions. When $\Sigma\neq I$, then we want to maximize $x_1\sigma_1+x_2\sigma_2+x_1x_2\sigma_1\sigma_2$ for $x_1+x_2\leq a$, from here I don't know how to solve. – Lee Sep 19 '19 at 10:05
• This seems to be analogous to finding the capacity of a Gaussian channel. I vote writing out the KKT conditions (cf. davidrosenberg.github.io/ml2015/docs/convex-optimization.pdf) and trying to solve. For a similar example, see example 5.2 in web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. Maybe look at chapter 9 in staff.ustc.edu.cn/~cgong821/…. – Travis C Cuvelier Sep 19 '19 at 17:31
• Also, a fun fact that is probably helpful is Hadamard's Inequality, which essentially tells you that you can assume a diagonal X, as @Omnomnomnom mentioned. – Travis C Cuvelier Sep 19 '19 at 17:33

Define the constrained matrix variable $$X$$ in terms of an unconstrained matrix $$Y$$ as follows $$X = \frac{\alpha Y}{{\rm Tr}(Y)} \implies {\rm Tr}(X) = \alpha$$ The following variables will also be useful $$B = I+X\Sigma,\quad W^T=\Sigma B^{-1},\quad \tau={\rm Tr}(Y) = I:Y$$ Find the gradient of the function wrt $$Y$$ \eqalign{ \phi &= \log\det(B) \\ d\phi &= B^{-T}:dB \\ &= B^{-T}:dX\,\Sigma \\ &= W:dX \\ &= W:\Big({\alpha\tau^{-1}\,dY-\alpha\tau^{-2}Y(I:dY)}\Big) \\ &= \Big(\alpha\tau^{-1}W-(W:Y)\alpha\tau^{-2}I\Big):dY \\ \frac{\partial\phi}{\partial Y} &= \alpha\tau^{-1}W-(W:Y)\alpha\tau^{-2}I \\ } Set the gradient to zero and solve, per usual for an unconstrained problem. \eqalign{ W &= (W:Y)\tau^{-1}I \;=\; \lambda I \\ \lambda I &= W = W^T = \Sigma B^{-1} = \Sigma(I+X\Sigma)^{-1} \\ \Sigma &= \lambda(I+X\Sigma) \\ X &= (\Sigma - \lambda I)(\lambda\Sigma)^{+} \;=\; \lambda^{-1}\Sigma\Sigma^{+}-\Sigma^{+} \\ } where $$\Sigma^+$$ is the pseudoinverse of $$\Sigma$$.

All that remains is to find the value of $$\lambda$$, which can be calculated by enforcing the original trace constraint. \eqalign{ \alpha &= {\rm Tr}(X) \\ &= \lambda^{-1}{\rm Tr}(\Sigma\Sigma^{+}) - {\rm Tr}(\Sigma^{+}) \\ &= \lambda^{-1}{\rm rank}(\Sigma) - {\rm Tr}(\Sigma^{+}) \\ \lambda &= \frac{{\rm rank}(\Sigma)}{\alpha+{\rm Tr}(\Sigma^{+})} } In the above derivation, the symmetry of $$\Sigma$$ was utilized, but the fact that it is diagonal was not needed. However, since $$(\Sigma,\Sigma^+)$$ are diagonal, $$X$$ is as well.

Finally, enforce non-negativity by taking $$X = (\lambda\Sigma)^{+}\max(0, \,\Sigma - \lambda I)$$

NB: In several steps, a colon is used to denote the trace/Frobenius product, i.e. $$A:B = {\rm Tr}(A^TB)$$