1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Paata Ivanishvili Mar 27 at 18:38
  • $\begingroup$ Thanks! Where can I find a proof for this inequality? $\endgroup$ – Apprentice Mar 27 at 18:52
  • 1
    $\begingroup$ See, for example, here math.stackexchange.com/questions/454699/… $\endgroup$ – Paata Ivanishvili Mar 27 at 19:33
  • $\begingroup$ 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? $\endgroup$ – Apprentice Mar 28 at 14:53
2
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ Very interesting answer, thanks a lot! $\endgroup$ – Apprentice Mar 28 at 17:47
1
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.