Show that DFP update preserve Positive Definiteness?

717 Views Asked by At

The update for Davidon-Fletcher-Powell (DFP) is given as the following:

$$ B_{k+1} = (I - \rho_ky_ks_k^{\top})B_k(I - \rho_ks_ky_k^{\top})+\rho_ky_ky_k^{\top} $$

where $y_k,s_k \in \mathbb{R}^n$ such that $\rho_k=y_k^{\top}s_k>0$ and $B_ks_k=y_k$.

Show that when $B_k$ is positive definite so is $B_{k+1}$.

1

There are 1 best solutions below

7
On BEST ANSWER

Let $x \in \mathbb{R}^n$, then

$$x^{\top} B_{k+1}x = x^{\top}(I - \rho_ky_ks_k^{\top})B_k(I - \rho_ks_ky_k^{\top})x+\rho_kx^{\top}y_ky_k^{\top}x.$$

As $B_k$ is positive definite, we have

$$ x^{\top}(I - \rho_ky_ks_k^{\top})B_k(I - \rho_ks_ky_k^{\top})x \geq 0.$$

Moreover,

$$ \rho_k x^{\top}y_ky_k^{\top}x \geq 0.$$

Hence, $$x^{\top} B_{k+1}x \geq 0.$$

To show that $B_{k+1}$ is positive definite, it remains to show that the inequality is strict when $x \neq 0$, or equivalently, $x^{\top} B_{k+1}x = 0$ implies $x=0$. From above $x^{\top} B_{k+1}x = 0$ implies $$(I - \rho_ks_ky_k^{\top})x = 0,$$ and $$y_k^{\top}x =0.$$

But this implies $x=0$. Hence, $B_{k+1}$ is positive definite.