Optimization Techniques

Amrita Vishwa Vidyapeetham

October 12, 2020

Outline

Multivariable Optimization
Gradient Based Methods
Outline

Multivariable Optimization
Gradient Based Methods
Gradient Based Methods

I Gradient-based methods discussed in this section exploit the derivative

information of the function and are usually faster search methods.
Gradient Based Methods

I Gradient-based methods discussed in this section exploit the derivative

information of the function and are usually faster search methods.
I Since these methods use gradient information and since the objective
functions in many engineering optimization problems are not
differentiable, they cannot be applied directly to many engineering
design problems.
Gradient Based Methods

I Gradient-based methods discussed in this section exploit the derivative

information of the function and are usually faster search methods.
I Since these methods use gradient information and since the objective
functions in many engineering optimization problems are not
differentiable, they cannot be applied directly to many engineering
design problems.
I For the same reason, the gradient-based methods cannot be applied to
problems where the objective function is discrete or discontinuous or
the variables are discrete.
Gradient Based Methods

I Gradient-based methods discussed in this section exploit the derivative

information of the function and are usually faster search methods.
I Since these methods use gradient information and since the objective
functions in many engineering optimization problems are not
differentiable, they cannot be applied directly to many engineering
design problems.
I For the same reason, the gradient-based methods cannot be applied to
problems where the objective function is discrete or discontinuous or
the variables are discrete.
I On the contrary, in problems where the derivative information is easily
available, gradient-based methods are very efficient.
Gradient Based Methods

I Gradient-based methods discussed in this section exploit the derivative

information of the function and are usually faster search methods.
I Since these methods use gradient information and since the objective
functions in many engineering optimization problems are not
differentiable, they cannot be applied directly to many engineering
design problems.
I For the same reason, the gradient-based methods cannot be applied to
problems where the objective function is discrete or discontinuous or
the variables are discrete.
I On the contrary, in problems where the derivative information is easily
available, gradient-based methods are very efficient.
I However, the concept of gradients in understanding the working
principle of the optimization algorithms is so intricate that
gradient-based methods are mostly used in engineering design
problems by calculating the derivatives numerically.
Gradient of the function
B The gradient of a function f (X), X ∈ Rn is an n-component vector
given by
∂f
 
 ∂x1 
 ∂f 
 
∂x2  .
 
∇fn×1 =   .  (1)
 .. 
 
 ∂f 
∂xn
B The gradient has a very important property. If we move along the
gradient direction from any point in n-dimensional space, the function
value increases at the fastest rate.
Gradient of the function
B The gradient of a function f (X), X ∈ Rn is an n-component vector
given by
∂f
 
 ∂x1 
 ∂f 
 
∂x2  .
 
∇fn×1 =   .  (1)
 .. 
 
 ∂f 
∂xn
B The gradient has a very important property. If we move along the
gradient direction from any point in n-dimensional space, the function
value increases at the fastest [Link] the gradient direction is called
the direction of steepest ascent.
Gradient of the function
B The gradient of a function f (X), X ∈ Rn is an n-component vector
given by
∂f
 
 ∂x1 
 ∂f 
 
∂x2  .
 
∇fn×1 =   .  (1)
 .. 
 
 ∂f 
∂xn
B The gradient has a very important property. If we move along the
gradient direction from any point in n-dimensional space, the function
value increases at the fastest [Link] the gradient direction is called
the direction of steepest [Link], the direction of steepest
ascent is a local property and not a global one. This is illustrated in Fig.
6.14, where the gradient vectors f evaluated at points 1, 2, 3, and 4 lie
along the directions 11’, 22’, 33’, and 44’, respectively. Thus the
function value increases at the fastest rate in the direction 11 at point 1,
but not at point 2. Similarly, the function value increases at the fastest
rate in direction 22’(33’) at point 2 (3), but not at point 3 (4).
Gradient Based Method
B In other words, the direction of steepest ascent generally varies from
point to point, and if we make infinitely small moves along the
direction of steepest ascent, the path will be a curved line like the curve
1-2-3-4 in Fig. 6.14.
Gradient Based Method

D Since the gradient vector represents the direction of steepest ascent, the
negative of the gradient vector denotes the direction of steepest descent.
Gradient Based Method

D Since the gradient vector represents the direction of steepest ascent, the
negative of the gradient vector denotes the direction of steepest descent.
D Thus any method that makes use of the gradient vector can be expected
to give the minimum point faster than one that does not make use of the
gradient vector.
Gradient Based Method

D Since the gradient vector represents the direction of steepest ascent, the
negative of the gradient vector denotes the direction of steepest descent.
D Thus any method that makes use of the gradient vector can be expected
to give the minimum point faster than one that does not make use of the
gradient vector.
D All the descent methods make use of the gradient vector, either directly
or indirectly, in finding the search directions.
Gradient Based Method

D Since the gradient vector represents the direction of steepest ascent, the
negative of the gradient vector denotes the direction of steepest descent.
D Thus any method that makes use of the gradient vector can be expected
to give the minimum point faster than one that does not make use of the
gradient vector.
D All the descent methods make use of the gradient vector, either directly
or indirectly, in finding the search directions.
D Hence, we would like to point out that the gradient vector represents the
direction of steepest ascent.
Graphical Representation
The first derivative ∇f (x(t) ) at any point x(t) represents the direction of the
maximum increase of the function value. Thus, if we are interested in
finding a point with the minimum function value, ideally we should be
searching along the opposite to the first derivative direction, that is, we
should search along −∇f (x(t) ) direction (see Figure 3.10).
Graphical Representation
The first derivative ∇f (x(t) ) at any point x(t) represents the direction of the
maximum increase of the function value. Thus, if we are interested in
finding a point with the minimum function value, ideally we should be
searching along the opposite to the first derivative direction, that is, we
should search along −∇f (x(t) ) direction (see Figure 3.10).
Descent Direction

A search direction, d(t) , is a descent direction at point x(t) if the condition

∇f (x(t) ).d(t) ≤ 0 is satisfied in the vicinity of the point x(t) .
Descent Direction

A search direction, d(t) , is a descent direction at point x(t) if the condition

∇f (x(t) ).d(t) ≤ 0 is satisfied in the vicinity of the point x(t) .

Example
Let us consider Himmelblau’s function: Minimize
f (x1 , x2 ) = (x12 + x2 − 11)2 + (x1 + x22 − 7)2 . We would like to determine
whether the direction d(t) = (1, 0)T at the point x(t) = (1, 1)T is a descent
direction or not.
The point and the direction are shown on a contour plot in Figure 3.11. It is
clear from the figure that moving locally along d(t) from the point x(t) will
reduce the function value. We investigate this aspect by calculating the
derivative ∇f (x(t) ) at the point. The derivative, as calculated numerically, is
∇f (x(t)) = (−46, −38)T .
Descent Direction
Taking the dot product between ∇f (x(t) ) and d(t) , we obtain
 
(t) T 1
∇f (x ) .d(t) = (−46, −38) = −46,
0

which is a negative quantity. Thus, the search direction d(t) = (1, 0)T is a
descent direction. The amount of nonnegativity suggests the extent of
descent in the direction. If the search direction d(t) = −∇f (x(t) ) = (46, 38)T
is used, the magnitude of the above dot product becomes
 
T 46
(−46, −38) = −3560.
38

Thus, the direction (46, 38)T or (0.771, 0.637)T is more descent than d(t) . In
fact, it can be proved that the above direction (0.771, 0.637)T is the steepest
descent direction at the point x(t) , as shown in Figure 3.11. It is noteworthy
that for any nonlinear function, the steepest descent direction at any point
may not exactly pass through the true minimum point. The steepest descent
direction is a direction which is a local best direction. It is not guaranteed
that moving along the steepest descent direction will always take the search
closer to the true minimum point.
Graphical Representation
Important Results

Theorem
The gradient vector represents the direction of steepest ascent.

Theorem
The maximum rate of change of f at any point X is equal to the magnitude of
the gradient vector at the same point.