0
$\begingroup$

I'm trying to prove the convexity of a function from its Hessian matrix.

He = $\begin{bmatrix} \frac{1}{x_1} - \frac{1}{\sum_{i=1}^n x_i} & & \frac{-1}{\sum_{i=1}^n x_i} & \cdots & \frac{-1}{\sum_{i=1}^n x_i}\\ \frac{-1}{\sum_{i=1}^n x_i} & & \frac{1}{x_2} - \frac{1}{\sum_{i=1}^n x_i} & \cdots & \frac{-1}{\sum_{i=1}^n x_i}\\ \vdots & & \ddots & & \vdots \\ \frac{-1}{\sum_{i=1}^n x_i} & & \cdots & & \frac{1}{x_n} - \frac{1}{\sum_{i=1}^n x_i}\\ \end{bmatrix}$

My idea was to separate this into two matrices and see if we could get something out of that:

He = $\begin{bmatrix} \frac{1}{x_1} & 0 & 0 & \cdots & 0\\ 0 & \frac{1}{x_2} & 0 & \cdots & 0\\ \vdots & \ddots & \ddots & \ddots & 0\\ 0 & 0 & \cdots & 0 & \frac{1}{x_n}\\ \end{bmatrix}$ + $\begin{bmatrix} \frac{-1}{\sum_{i=1}^n x_i} & \frac{-1}{\sum_{i=1}^n x_i} & \cdots & \frac{-1}{\sum_{i=1}^n x_i}\\ \frac{-1}{\sum_{i=1}^n x_i} & \ddots & \ddots & \frac{-1}{\sum_{i=1}^n x_i}\\ \vdots & \ddots & \ddots & \vdots\\ \frac{-1}{\sum_{i=1}^n x_i} & \frac{-1}{\sum_{i=1}^n x_i} & \cdots & \frac{-1}{\sum_{i=1}^n x_i}\\ \end{bmatrix}$

Knowing that: $x \in \mathbb{R}_{++}^n$

we can see that the first matrix is positive definite and the second matrix consists of the same value in each position, and this value must be negative.

Also, since $\dfrac{1}{x_i} > \dfrac{1}{\sum_{i=1}^n x_i}$ for all $i$, the entries on the diagonal of the original Hessian must all be positive.

However, I don't know what else I can do with this.

$\endgroup$

1 Answer 1

1
$\begingroup$

$D:= \text{diag}\big(x_1,x_2,...,x_n\big)$
$\alpha := \frac{1}{\sum_{k=1}^n x_k}$
$H :=D^{-1} -\alpha\mathbf 1\mathbf 1^T$

1.) argument via congruence
$\mathbf v:= D^\frac{1}{2}\mathbf 1$
$B:=D^\frac{1}{2}HD^\frac{1}{2} = I -\alpha \mathbf v \mathbf v^T= I +\big(-\alpha \mathbf v \mathbf v^T\big)$
note that $\text{trace}\Big(-\alpha \mathbf v \mathbf v^T\Big) = -\alpha\cdot\text{trace}\Big( \mathbf v \mathbf v^T\Big)= -\alpha\cdot \mathbf v^T\mathbf v = -\alpha \cdot \alpha^{-1}=-1$
so
$-\alpha \mathbf v \mathbf v^T = Q\Lambda Q^T$
where $Q^{-1}=Q^T$ and $\Lambda$ is diagonal with a $-1$ in bottom right corner and everything else is zero. Then
$B = I + -\alpha \mathbf v \mathbf v^T = QIQ^T + Q\Lambda Q^T = Q\big(I+\Lambda\big) Q^T$

so $H$ is congruent to $B$ which is congruent to $\big(I+\Lambda\big)$
thus they all have signature of $\big(n-1,0\big)$

2.) argument over paths
Using topological continuity of eigenvalues you can verify this as follows. For $\tau \in [0,1]$
$H(\tau) :=D^{-1} + \tau\cdot \big(-\alpha\mathbf 1\big)\mathbf 1^T$

where $H(\tau)$ is real symmetric for all $\tau \in[0,1]$ and clearly $H(0)\succ \mathbf 0$ and $H(1) = H$.
now for $\tau \in [0,1]$, by matrix determinant lemma
$\det\Big(H(\tau)\Big) $
$= \det\Big(D^{-1} + \tau\cdot \big(-\alpha\mathbf 1\big)\mathbf 1^T\Big)$
$= \det\Big(D^{-1}\Big)\cdot \Big(1+ \tau\cdot \mathbf 1^T D\big(-\alpha\mathbf 1\big)\Big)$
$= \det\Big(D\Big)^{-1}\cdot \Big(1+ \tau\cdot \alpha^{-1} \cdot(-\alpha)\big)\Big)$
$= \det\Big(D\Big)^{-1}\cdot \Big(1- \tau\Big)$
$\geq 0$
and the inequality is strict for $\tau \in [0,1)$

This means $H(1)=H\succeq \mathbf 0$. I.e. If $H$ was indefinite, then where must be some $\tau^* \in [0,1)$ where $\det\big(H(\tau^*)\big) =0$ via eigenvalue continuity, but there isn't so $H$'s signature is $\big(?,0\big)$. We can actually determine that $?=n-1$ by observing

$\text{rank}\Big(H\Big) = \text{rank}\Big(D^{-1} - \big(\alpha\mathbf 1\big)\mathbf 1^T\Big)\geq \text{rank}\Big(D^{-1}\Big) - \text{rank}\Big(\alpha\mathbf 1\mathbf 1^T\Big) =n-1$, which must be met with equality because $\det\big(H\big) =0$. Thus $H$ has signature $\big(n-1,0\big)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .