Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My class has recently learnt the BFGS method for unconstrained optimisation. In this procedure, we have a rank-1 update to a positive definite matrix at each step.

This is specified as:

$H_{k+1} = H_k + \frac{\eta\eta^T}{\delta^T\eta}-\frac{H_k\delta\delta^TH_k^T}{\delta^TH_k\delta}$

$\forall \eta, \delta \in \mathbb{R}^n$.

Show that for any symmetric positive definite matrix $H_k,$ we have that $H_{k+1}$ is positive definite so long as $\delta^T\eta > 0$. Don't assume anything about $H_k$ other than the fact that it is symmetric p.d.

share|improve this question
add comment

2 Answers

$\def\skp#1{\left<#1\right>}$As $H_k$ is spd, the form $(x,y) \mapsto \skp{x,y}_k := x^tH_ky$ defines a scalar product. By Cauchy-Schwarz we have \[ \skp{x,y}_k^2 \le \skp{x,x}_k\skp{y,y}_k \] for any $x,y \in \mathbb R^n$ and with strict inequality if $x$ and $y$ aren't linear dependent. Now let $x \in \mathbb R^n\setminus \{0\}$, then \begin{align*} \skp{x,x}_{k+1} &= x^tH_{k+1}x\\ &= x^tH_k x + x^t\frac{\eta\eta^t}{\delta^t\eta}x - x^t\frac{H_k\delta\delta^tH_k^t}{\delta^tH_k\delta}x\\ &= \skp{x,x}_k + \frac 1{\delta^t\eta}x^t\eta\eta^tx - \frac 1{\skp{\delta, \delta}_k}\skp{x,\delta}_k\skp{\delta, x}_k\\ &= \skp{x,x}_k + \frac 1{\delta^t\eta}(x^t\eta)^2 - \frac 1{\skp{\delta, \delta}_k}\skp{x,\delta}_k^2\\ \end{align*} If now $x$ and $\delta$ aren't linear dependent, then we can estimate further using Cauchy-Schwarz: \begin{align*} \skp{x,x}_{k+1} &> \skp{x,x}_k + 0 - \frac 1{\skp{\delta,\delta}_k}\skp{x,x}_k\skp{\delta,\delta}_k\\ &= 0. \end{align*} Otherwise, if, say $x = \lambda\delta$, then $x^t\eta = \lambda \delta^t\eta \ne 0$, and, hence \begin{align*} \skp{x,x}_{k+1} &= \skp{x,x}_k + \frac 1{\delta^t\eta}(x^t\eta)^2 - \frac 1{\skp{\delta,\delta}_k}\skp{x,x}_k\skp{\delta,\delta}_k\\ &= \frac 1{\delta^t\eta}(x^t\eta)^2\\ &> 0. \end{align*} So $\skp{x,x}_{k+1} > 0$ for $x \ne 0$, and $H_{k+1}$ is positive definite.

share|improve this answer
add comment

We know that $H_k$ is symmetric positive definite (SPD).

For any vector $v$, it is easy to show that $vv^T$ is symmetric positive semidefinite (SPSD).

Thus $\eta\eta^T$ is SPSD. It is given that $\delta^T\eta$ is positive, so $(\eta\eta^T)/(\delta^T\eta)$ is SPSD.

$H_k\delta\delta^TH_k^T = (H_k\delta)(H_k\delta)^T$ is of the form $vv^T$, so it is also SPSD. Because $H_k$ is SPD, $\delta^TH_k\delta$ is positive. Thus $(H_k\delta\delta^TH_k^T)/(\delta^TH_k\delta)$ is SPSD.

Now $H_{k+1}$ is the sum of an SPD matrix and two SPSD matrices, so it is also SPD.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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