5
$\begingroup$

I am wondering if $f(\mathbf{x})$ is convex on the input of a vector of $n$ positive reals $\mathbf{x}$:

$f(\mathbf{x})=\operatorname{Tr}[(\mathbf{A}+\operatorname{diag}(\mathbf{x}))^{-1}]$

where $\mathbf{A}$ is a positive-definite $n\times n$ matrix of reals, $\operatorname{diag}(\mathbf{x})$ returns a diagonal matrix with values from $\mathbf{x}$ placed on the diagonal, and $\operatorname{Tr}[\mathbf{M}]$ is the trace of matrix $\mathbf{M}$.

I understand that I can prove convexity via taking the second derivative, but I am not sure how to it in the matrix case. I also know that for positive-definite $\mathbf{A}$, $g(\mathbf{y})=\frac{1}{2}\mathbf{y}^T\mathbf{A}\mathbf{y}+\mathbf{y}^T\mathbf{b}$ is strictly convex, but I am not sure how that applies here (if it applies at all).

1 Answers 1

3

Consider $g(t) = {\bf u}^T (C + tB)^{-1} \bf u$ for any real vector $\bf u$, where $C$ and $B$ are real symmetric matrices and $C+tB$ is positive definite. Note that the first derivative of $(C + tB)^{-1}$ with respect to $t$ is $- (C + tB)^{-1} B (C + tB)^{-1}$, and the second derivative is $2 (C+tB)^{-1} B (C+tB)^{-1} B (C+tB)^{-1}$. So $g''(t) = 2 {\bf u}^T (C+tB)^{-1} B (C+tB)^{-1} B (C+tB)^{-1} {\bf u} = 2 {\bf v}^T (C+tB)^{-1} \bf v$ where ${\bf v} = B (C+tB)^{-1} \bf u$. Since $(C+tB)^{-1}$ is positive definite when $C+tB$ is positive definite, $g''(t) \ge 0$, i.e. $g$ is convex as long as $C+tB$ is positive definite. Now $Tr (C+tB)^{-1} = \sum_j {\bf u}_j^T (C+tB)^{-1} {\bf u}_j$ for an orthonormal basis ${\bf u}_j$, so this is also convex. And $f(t {\bf x} + (1-t) {\bf y})$ is of this form, with $C = A + \text{diag}({\bf y})$ and $B = \text{diag}({\bf x} - {\bf y})$, when $0 \le t \le 1$ (note that for $0 \le t \le 1$, $t {\bf x} + (1-t) {\bf y}$ has nonnegative entries, and the sum of a positive definite matrix and a nonnegative diagonal matrix is positive definite). That says $f$ is convex.

  • 0
    Thank you, I get it now. And yes, one can't get away without checking the derivative, so my "proof" doesn't work. I really appreciate you taking the time to respond to my queries and pointing out a way to prove convexity that I didn't know before. Again, thank you!2012-06-03