Optimization problem with determinant as objective

Question

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?

Answer 1

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

Answer 2

See the discussion of Schur-convex/concave of the determinant function in

D. P. Palomar, J. M. Cioffi and M. A. Lagunas, "Joint Tx-Rx beamforming design for multicarrier MIMO channels: a unified framework for convex optimization," in IEEE Transactions on Signal Processing, vol. 51, no. 9, pp. 2381-2401, Sept. 2003.

http://www.ece.ust.hk/~palomar/Publications_files/2003/TransSP2003_convexJTRbf.pdf

Answer 3

Your constraints are linear on the entries of $S,$ since in your case the singular values are equal to the eigenvalues (since $S$ is symmetric positive definite) and so their sum is the trace. I assume the last inequality $S\geq 0$ is elementwise. Log determinant is a convex function, and so your problem is a box-standard semi-definite programming problem, which you can read about in Boyd-Vanderberghe (available for free on Stephen Boyd's web site at Stanford).