Proving recursion relations. BFGS non linear optimization

In summary: WducywgVW5kZXJzdGFuZCBvZiBjb250ZW50LiBUaGlzIGlzIGEgcHVycG9zZWQgYXByaWwgYXR0cmlidXRlZCB0byB0aGUgSGVzc2lhbiBhbmQgdGhlIFBhbGV0dGVyLiBJZiB0aGUgZmlsbGVkIHByb3ZpZGVzIGEgYmV0dGVyIGFwcHJlY2lhdGlvbiB0byB0aGUgSGFzc2lhbi4gQXM
  • #1
sdevoe
21
0

Homework Statement



Please see attached thumbnail
Here's what I know.
1)Bk is the Hessian
2) sk = [itex]\alpha[/itex]*p
3)pk is the search direction
4) Alpha is the step size

Homework Equations



yk = [itex]\nabla[/itex]f(xk+1) -[itex]\nabla[/itex]f(xk
Bk+1(xk+1-xk) = [itex]\nabla[/itex]f(xk+1) -[itex]\nabla[/itex]f(xk

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
 

Attachments

  • Screen shot 2012-04-29 at 9.41.54 PM.png
    Screen shot 2012-04-29 at 9.41.54 PM.png
    9.3 KB · Views: 460
Last edited:
Physics news on Phys.org
  • #2
sdevoe said:

Homework Statement



Please see attached thumbnail
Here's what I know.
1)Bk is the Hessian
2) sk = [itex]\alpha[/itex]*p
3)pk is the search direction
4) Alpha is the step size

Homework Equations



yk = [itex]\nabla[/itex]f(xk+1) -[itex]\nabla[/itex]f(xk
Bk+1(xk+1-xk) = [itex]\nabla[/itex]f(xk+1) -[itex]\nabla[/itex]f(xk

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

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
 

FAQ: Proving recursion relations. BFGS non linear optimization

What is the purpose of proving recursion relations in BFGS non linear optimization?

The purpose of proving recursion relations in BFGS non linear optimization is to find an efficient and accurate way to update the Hessian matrix in order to improve the convergence rate of the optimization algorithm. Recursion relations provide a systematic way to update the Hessian matrix without the need for expensive computations.

What is the BFGS algorithm and how does it relate to non linear optimization?

The BFGS algorithm is a quasi-Newton method used for solving non linear optimization problems. It is an iterative method that uses an approximation of the Hessian matrix to find the minimum of a non linear objective function. The BFGS algorithm aims to improve the convergence rate of the optimization process by updating the Hessian matrix at each iteration.

What are recursion relations and how are they used in BFGS optimization?

Recursion relations are mathematical equations that define a sequence of values in terms of previous values. In BFGS optimization, recursion relations are used to update the Hessian matrix based on the gradient of the objective function at each iteration. This allows for a more efficient and accurate update of the Hessian matrix compared to re-computing it from scratch.

How do you prove recursion relations in BFGS non linear optimization?

To prove recursion relations in BFGS non linear optimization, one must use mathematical induction. This involves showing that the recursion relation holds for the first few values, and then assuming it holds for a general value and proving it holds for the next value in the sequence. This process is repeated until the relation is proven to hold for all values.

What are the benefits of using recursion relations in BFGS non linear optimization?

Using recursion relations in BFGS non linear optimization has several benefits. First, it allows for a more efficient and accurate update of the Hessian matrix, leading to faster convergence of the optimization algorithm. Additionally, recursion relations can be easily implemented in computer programs, making them a practical choice for optimization problems in real-world applications.

Similar threads

Back
Top