# Convexity of inverse quadratic form

Let $$\alpha_i\in[0,1]^k$$, $$x_i\in\mathbb{R}^d$$ for all $$i\in[k]$$, with $$k \geq d$$. Define $$X: \operatorname{col}(X) = \{x_i\}_{i\in[k]}$$, $$\Lambda(\alpha) = \operatorname{diag}(\alpha)$$, $$y\in\mathbb{R}^d$$. Is the following expression convex?

$$f(\alpha) = y^\top\left(\sum_{i=1}^k \alpha_i x_ix_i^\top\right)^{-1}y.$$

Note that the above expression can be expressed equivalently in matrix form as

$$f(\alpha) =y^T(X\Lambda(\alpha) X^\top)^{-1}y$$

• If $A, B$ are positive definite matrices then $\frac{1}{2} (A^{-1}+B^{-1}) \geq (\frac{A+B}{2})^{-1}$, where $U\geq V$ means $U-V$ is positive semidefinite. Now apply this inequality to $A = \sum \alpha_{i} x_{i}x_{i}^{T}$ and $B = \sum \beta_{i} x_{i}x_{i}^{T}$. – Paata Ivanishvili Mar 27 at 18:38
• Thanks! Where can I find a proof for this inequality? – Apprentice Mar 27 at 18:52
• See, for example, here math.stackexchange.com/questions/454699/… – Paata Ivanishvili Mar 27 at 19:33
• A book would have been a better source I think, and the answer in the question you posted are mostly wrong or with many errors. Do you know any book including this proof? – Apprentice Mar 28 at 14:53

## 2 Answers

Claim 1: If $$A$$ is positive semidefinite then $$\langle Ax, x \rangle \langle Ay,y\rangle \geq \langle Ax,y\rangle^{2}$$.

This Cauchy--Schwartz inequality can be proved by considering quadratic function $$\lambda \mapsto \langle x+\lambda y, A(x+\lambda y) \rangle \geq 0$$ and writing down that its discriminant $$D = 4 (\langle x, y\rangle ^{2} - \langle x, Ax\rangle \langle y, Ay\rangle$$) must be non-positive.

Claim 2: if $$A$$ is positive definite then $$\langle A^{-1}c,c \rangle =\max_{x}\left\{ 2\langle x,c \rangle - \langle Ax,x\rangle \right\}$$ for all vectors $$c$$.

Indeed, the direction $$\langle A^{-1}c,c \rangle \geq 2\langle x,c \rangle - \langle Ax,x\rangle$$ can be obtained as follows: $$\langle A^{-1}c,c \rangle +\langle Ax,x\rangle \geq 2 \sqrt{\langle A^{-1}c,c \rangle \langle Ax,x\rangle} \geq 2|\langle x,c \rangle|$$, where the last inequality with $$c=Ay$$ coincides with Claim 1. Since $$A$$ is invertible it covers all c's. On the other hans the choice $$x=A^{-1}c$$ in $$\max_{x}\left\{ 2\langle x,c \rangle - \langle Ax,x\rangle \right\}$$ gives $$\langle A^{-1}c,c \rangle$$.

Claim 3: $$(\frac{A+B}{2})^{-1} \leq \frac{A^{-1}+B^{-1}}{2}$$ holds for all positive definite matrices.

We have $$\langle c, (\frac{A+B}{2})^{-1}c \rangle = \max_{x} \left\{ 2\langle x,c \rangle - \langle (\frac{A+B}{2})x,x\rangle \right\} \leq \frac{\max_{x} \left\{ 2\langle x,c \rangle - \langle (A)x,x\rangle \right\}}{2} +\frac{\max_{x} \left\{ 2\langle x,c \rangle - \langle Bx,x\rangle \right\}}{2} = \frac{\langle A^{-1}c,c\rangle + \langle B^{-1}c,c\rangle}{2}$$ $$\square$$.

• the idea of representing convex function as a sup of linear functions (or sometimes even sup of concave functions with comparable quantity) is a standard technique in stochastic optimal control theory.
• the link that I provided in the comments, I think the second answer using derivatives looks correct to me.
• Very interesting answer, thanks a lot! – Apprentice Mar 28 at 17:47

I have written an answer myself based on the suggestion by @Paata Ivanishvili. It is based on the following inequality: for any two matrices $$\mathbf{X},\mathbf{Y}$$, $$\lambda\in[0,1]$$

$$(1-\lambda)\mathbf{X}^{-1}+\lambda\mathbf{Y}^{-1} \succeq((1-\lambda)\mathbf{X}+\lambda\mathbf{Y})^{-1}.$$

If this relation is true, we have

\begin{align} f(\lambda\alpha +(1-\lambda)\beta) & = y^\top\left(\sum_{i=1}^k (\lambda\alpha_i +(1-\lambda)\beta_i)x_ix_i^\top\right)^{-1}y \\ & \leq \lambda y^\top\left(\sum_{i=1}^k \alpha_i x_ix_i^\top\right)^{-1}y + (1-\lambda) y^\top\left(\sum_{i=1}^k \alpha_i x_ix_i^\top\right)^{-1}y. \end{align}