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.)

However, if A/a is large, then the convergence constant δ will be only slightly smaller than 1. Table 1 shows some sample values. Note that the number of iterations needed to reduce the optimality gap by a factor of 10 grows linearly in the ratio A/a. 4 Examples 4.1 Example 1: Typical Behavior Consider the function f (x1,x2)=5x2 1 + x22 +4x1x2 ...

Loading..

Tags:

  Convergence, Descent, Steepest descent, Steepest

Information

Related search queries