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. x) For this reason the un-normalized direction: d = f( x) is called the direction of Steepest Descent at the point x.

Using the steepest descent algorithm to minimize f (x) starting from x1 =(x1 1 1,x2)=(0, 10), and using a tolerance of =10−6, we compute the iterates shown in Table 2 and in Figure 2: For a convex quadratic function f (x)= 1xT Qx−cT x, the contours of the 2 function values will be shaped like ellipsoids, and the gradient vector ∇f (x)

Loading..

Tags:

  Descent, Steepest descent, Steepest

Information

Related search queries