Let $A$ be a given symmetric positive definite $N\times N$ matrix. I need to find a symmetric positive semi-definite matrix $S$ which is the solution to the following optimization problem
\begin{align}
\max_{S}~&\det(A+S) \\s.t.~&\sum_{i}^{N}\sigma_i(S)\,=\,c \\&S\geq0
\end{align}where $\sigma_i(S)$ are the singular values of $S$ and $c$ is a given positive constant.
Note that I already know that this can be converted into a standard convex problem by replacing the constraint on sum of singular values by trace and also considering log-determinant. However, I am interested in a different approach.
My hunch is that following is the solution.
Let $A=U_a\Sigma_aU_a^H$ be its Eigen-decomposition (EVD). Since both $A$ and $S$ are symmetric positive semi-definite, their EVD and SVD are same. Let $S= U_s\Sigma_sU_s^H$ be its EVD which we are seeking. Then first part of the solution is $$U_s = U_a$$ It only remains find $\Sigma_s$ which contains the singular values of $S$. Substituting this in the original optimization problem, it breaks down into the simple form of finding the variables $\sigma_i(S)$ from the optimization problem
\begin{align}
\max_{\sigma_1(S),\dots,\sigma_N(S)}~&\prod_{i=1}^{N}(\sigma_i(A)+\sigma_i(S)) \\s.t.&\sum_{i=1}^N\sigma_i(S)=c
\end{align}
This is also equivalent to maximizing the $\log$ of the objective since the objective is a increasing function of each variable. Let us substitute $$x_i=\frac{\sigma_i(S)}{\sigma_i(A)}$$ Also, we can use the fact that determinant is the product of singular values for a symmetric positive definite matrix. Combining all this, we have the optimization problem
\begin{align}\max_{x_i}\sum_{i=1}^{N}~&\log(1+x_i)+\log\det(A)\\s.t.~&\sum_{i=1}^{N}\sigma_i(A)x_i\,=\,c\end{align}
The constant term in the objective can be neglected. This is an instance of a very famous problem in wireless communications where one tries to maximize the capacity of set of $N$ wireless channels subject to power constraints in each. Its solution is very well known and is typically referred to as the water filling solution. So I know the process after reaching this point. Note that all this was facilitated by the assumption that $U_s = U_a$. Is that true? How do I prove this?. If not, what are other approaches I can try?
Best Answer
One can verify that $U_{A}=U_{S}$ as follows. Note that $$\det(U_{A}\Sigma_{A}V_{A}^{T}+U_{S}\Sigma_{S}V_{S}^{T})=\det(\Sigma_{A}+U_{A}^{-1}U_{S}\Sigma_{S}V_{S}^{T}V_{A}^{-T})$$ Let $Y=U_{A}^{-1}U_{S}\Sigma_{S}V_{S}^{T}V_{A}^{-T}$ so that the problem can be rephrased as:
$$\max\limits_{Y} \det(\Sigma_{A}+Y) \text{ subject to } Tr(Y)=c,\ Y\succ 0$$
Now, let $Z=\Sigma_{A}+Y$ so that the problem is reformulated:
$$\max\limits_{Z} \det(Z) \text{ subject to } Tr(Z)=c+\sum\limits_{i=1}^{n} \sigma_{A}(i),\ Z\succ 0,\ Z_{i,i}\geq \sigma_{A}(i)$$
Since $Z$ can be written $Z=UT$ where $U$ is orthogonal and $T$ upper triangular, $\det(Z)=\det(T)$ and the off-diagonal terms of $T$ do not contribute so that $T$ may be assumed diagonal. Thus, finally one arrives at:
$$\max\limits_{T} \det(T) \text{ subject to } Tr(T)=c+\sum\limits_{i=1}^{n} \sigma_{A}(i),\ T\succ 0,\ T_{i,i}\geq \sigma_{A}(i),\ \text{T is diagonal}$$
This problem's solution follows from solving the water filling problem above where $t_{k}=T_{k,k}$:
$$\max\limits_{t_{k}} \sum\limits_{k=1}^{n} \log(t_{k}+\sigma_{k}) \text{ subject to } t_{k}\geq 0 \text{ and }\sum\limits_{k=1}^{n} t_{k}=c$$