The BFGS update satisfies the secant condition

ProofAdvanced⏱ 30 minAdvanced Optimizationbfgssecantquasi-newtonpositive definiteness

Problem

Let $s = x_{t+1}-x_t$ , $g = \nabla f(x_{t+1})-\nabla f(x_t)$ , and

B^+ = \Big(I-\frac{sg^\top}{g^\top s}\Big)B\Big(I-\frac{gs^\top}{g^\top s}\Big) + \frac{ss^\top}{g^\top s}.

Verify that $B^+g = s$ , and show that $B\succ0$ and $g^\top s>0$ imply $B^+\succ0$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Newton's method is affine invariant	Advanced Optimization	Proof	Intermediate	30 min
Conjugate gradient and Krylov optimality	Advanced Optimization	Proof	Advanced	1 hour
Local quadratic convergence of Newton's method	Advanced Optimization	Proof	Advanced	1 hour