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.



optimization over positive semidefinite matrices
$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.


