# Homework Help: Proving recursion relations. BFGS non linear optimization

1. Apr 29, 2012

### sdevoe

1. The problem statement, all variables and given/known data

Here's what I know.
1)Bk is the Hessian
2) sk = $\alpha$*p
3)pk is the search direction
4) Alpha is the step size

2. Relevant equations

yk = $\nabla$f(xk+1) -$\nabla$f(xk
Bk+1(xk+1-xk) = $\nabla$f(xk+1) -$\nabla$f(xk
3. The attempt at a solution
Bk+1(xk+1-xk) = yk

and then somehow from there I have to use the above to prove the Hk+1 equation

#### Attached Files:

• ###### Screen shot 2012-04-29 at 9.41.54 PM.png
File size:
10.3 KB
Views:
110
Last edited: Apr 29, 2012
2. Apr 29, 2012

### Ray Vickson

You don't know that B_k is the Hessian; you only know that it is a current approximation to the Hessian. In a purely quadratic model with exact line searches, each line search produces a better approximation to the Hessian, so starting from B_0 = Identity matrix (for example), you will have B_k = exact Hessian for some k <= n; that is, in at most n line searches you will get the Hessian---all of this without ever computing a second derivative! Going from B_k to B_{k+1} is a rank-1 update. There are formulas for how to change the inverse after a rank-1 update. I don't remember them, but they are widely available in the linear algebra/nonlinear optimization literature.

RGV