0
$\begingroup$

\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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Omnomnomnom Sep 19 '19 at 8:07
  • $\begingroup$ 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. $\endgroup$ – Omnomnomnom Sep 19 '19 at 8:11
  • $\begingroup$ @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. $\endgroup$ – Lee Sep 19 '19 at 10:05
  • $\begingroup$ 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/…. $\endgroup$ – Travis C Cuvelier Sep 19 '19 at 17:31
  • $\begingroup$ 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. $\endgroup$ – Travis C Cuvelier Sep 19 '19 at 17:33
2
$\begingroup$

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)$$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.