The Steepest Descent Algorithm for Unconstrained ...

The Steepest Descent Algorithm for Unconstrained Optimization and a Bisection Line-search Method Robert M. Freund February, 2004 1 2004 Massachusetts Institute of Technology. 1 The Algorithm The problem we are interested in solving is: P : minimize f(x) x n , where f(x) is differentiable. If x= xis a given point, f(x) can be approxi-mated by its linear expansion f( x)+ f( x+ d) f( x)T d if d small , , if d is small. Now notice that if the approximation in the above expression is good, then we want to choose d so that the inner product f( x)T dis as small as possible. Let us normalize dso that d =1. Then among all directions dwith norm d = 1, the direction d = f( x) f( x) makes the smallest inner product with the gradient f( x). This fact follows from the following inequalities: f( x) d = f( )T f( = f( )T x)T d f( x f( x) xd.)

If x =¯x is a given point, f(x) can be approxi-mated by its linear expansion f(¯x+ d) ≈ f(¯x)+∇f(¯x)T d if d “small”, i.e., if d is small. Now notice that if the approximation in the above expression is good, then we want to choose d so that the inner product ∇f(¯x)T d is as small as possible. Let us normalize d so that d =1.

Loading..

Tags:

  Points, Descent, Steepest descent, Steepest

Information

Related search queries