GRADIENT METHODS

GRADIENT METHODS

In this chapter we consider a class of search methods for real-valued functions on R^n. These methods use the gradient of the given function.
LEVEL SETS:
The level set of a function f:R^n?R at level c is the set of points S={x:f(x)=c}.
For f:R^2?R, we are usually interested in S when it is a curve. For f:R^3?R, the sets S most often considered are surfaces.
Example : Consider the following real-valued function on R^2:
f(x)=100?(x_2-x_1^2)?^2+?(1-x_1)?^2, x=[x_1,x_2 ]^T
The function above is called Rosenbrock s function. A plot of the function f is shown in the next Figure :

The level sets of f at levels 0.7, 7, 70, 200, and 700 are depicted in the next Figure.

These level sets have a particular shape resembling bananas. For this reason, Rosenbrock s function is also called the banana function.
To say that a point x_0 is on the level set S at level c means that ?f(x?_0)=c.
Recall that a level set of a function f:R^n?R is the set of points x satisfying f(x)=c for some constant c. Thus, a point x_0?R^n is on the level set corresponding to level c if f(x_0 )=c.
In the case of functions of two real variables, f:R^2?R, the notion of the level set is illustrated in the next Figure :

The gradient of f at x_0, denoted ?f(x_0), if it is not a zero vector, is orthogonal to the tangent vector to an arbitrary smooth curve passing through x_0 on the level set f(x)=c. Thus, the direction of maximum rate of increase of a real-valued differentiable function at a point is orthogonal to the level set of the function through that point. In other words, the gradient acts in such a direction that for a given small displacement, the function f increases more in the direction of the gradient than in any other direction. To prove this statement, recall that ??f(x),d?,?d?=1 , is the rate of increase of f in the direction d at the point x. By the Cauchy-Schwarz inequality