# optimization over positive semidefinite matrices

I wonder what is the most explicit characterization that can be given for the solution to the ($N$-dimensional) problem of maximizing the criterion

$$-\textrm{trace}[AS^{-1}] - b^\top Sb$$

over positive semidefinite (symmetric) $S$ is, where $A$ is also positive semidefinite, and nonzero $b \in [0,\infty)^N$.

This arises in a model of choosing to sample some signal with precision $S$ and cost parameterized by $b$. Of course, the solution should nest the scalar solution of $S = \sqrt{A}/b$. Many thanks.

-

$S$ must be positive-definite, not just positive-semidefinite, else $AS^{-1}$ does not exist. Suppose $A$ is positive-definite, and let $A^{1/2}$ be its positive-definite square root. Then the supremum over positive-definite $S$ of $-{\rm tr}(AS^{-1}) - b^\top S b$ is $-2 |A^{1/2}b|$, as in the scalar case. But once $N>1$ the supremum is not attained by any finite $S$.
We have $${\rm tr}(AS^{-1}) = {\rm tr}(A^{1/2} A^{1/2} S^{-1}) = {\rm tr}(A^{1/2} S^{-1} A^{1/2}) = {\rm tr}(M^{-1}),$$ where $M$ is the positive-definite matrix $A^{-1/2} S A^{-1/2}$. Then $S = A^{1/2} M A^{1/2}$, so $$b^\top S b = (A^{1/2} b)^\top M (A^{1/2} b) = v^\top S v$$ where $v = A^{1/2} b$. It will be convenient to choose coordinates so that $v$ is a multiple of the first unit vector. Then $$-{\rm tr}(AS^{-1}) - b^\top S b = -{\rm tr}(M^{-1}) - \left|v\right|^2 M_{11}$$ (as usual $M_{11}$ is the first diagonal entry of $M$). But for positive-definite $M$ we have $(M^{-1})_{11} \geq M_{11}^{-1}$, with equality iff $M_{1j}=0$ for all $j \neq 1$. Therefore $$-{\rm tr}(M^{-1}) - \left|v\right|^2 M_{11} < -(M_{11})^{-1} - \left|v\right|^2 M_{11} \leq -2 \left|v\right|.$$ In the last step equality holds iff $M_{11} = \left| v \right|^{-1}$. But $-$ unless $N=1$ $-$ there cannot be equality in the first step, because the diagonal entries $(M^{-1})_{jj}$ for $j \geq 2$ must be positive, though they can be arbitrarily small. We can get within $(N-1)\epsilon$ by making $M^{-1}$ the diagonal matrix ${\rm diag}(\left| v \right|^{-1},\epsilon,\epsilon,\ldots,\epsilon)$ and then recovering $S = A^{1/2} (M^{-1})^{-1} A^{1/2}$ which will be large in all directions except the one measured by ${\rm tr}(AS^{-1})$. If $v=0$ then we can get within $N \epsilon$ of zero by making $(M^{-1})_{11} = \epsilon$, so the formula $-2\left|v\right|$ for the supremum holds in this case too.