02/05/2025
Direct Search Methods
Direct Search Methods
• Direct search methods in optimization are derivative-free
techniques
• No gradient or Hessian information is required
• Use objective function values to search global optimum
• Used when:
• The function is non-differentiable, discontinuous, or expensive to
evaluate.
• The function is a black-box, such as simulation-based or experimental.
1
02/05/2025
Random Jumping Method
• Generate sets of n random numbers, (𝑟! , 𝑟" , . . . , 𝑟# ), that are uniformly distributed
between 0 and 1.
• Bounds 𝑙$ and 𝑢$ for each design variable 𝑥$ , i = 1, 2, . . . , n, are established for
generating the random values of 𝑥$ :
𝑙$ ≤ xi ≤ 𝑢$ , i = 1, 2, . . . , n
• By generating a large number of random points X and evaluating the value of the
objective function at each of these points, we can take the smallest value of f (X) as the
desired minimum point.
2
02/05/2025
Random Walk Method
• The random walk method is based on generating a sequence of improved
approximations to the minimum, each derived from the preceding
approximation.
𝑋!"# = 𝑋! + 𝜆𝑢!
Where 𝑋! is a point in the 𝑖th stage , 𝜆 is a prescribed scalar step and 𝑢! is the
unit vector obtained in the 𝑖th stage
3
02/05/2025
Nelder-Mead (Simplex) Method
• Uses a geometric simplex (a polytope of n+1 vertices in n-
dimensions) to explore the space.
• Common in unconstrained optimization.
• The geometric figure formed by a set of n + 1 points in an n-
dimensional space is called a simplex.
• Two steps:
• Compares the values of the objective function at the n + 1 vertices of a general
simplex
• Moves the simplex gradually toward the optimum point during the iterative
process.
Nelder-Mead (Simplex) Method
• Three main steps of Simplex method are:
• Reflection
• Expansion
• Contraction
• 𝑿𝒉 : Solution/point that returns worst objective function value
• 𝑿𝒍 : Solution/point that returns best objective function value
• 𝑿𝒈 : Solution/point that returns average objective function value
4
02/05/2025
Nelder-Mead (Simplex) Method
• Three main steps of Simplex method are:
• Reflection
• 𝑿𝒓: Reflection point obtained by directing the search in the opposite face of the
worst solution 𝑿𝒉
𝑿𝒓 = 𝟏 + 𝜶 𝑿𝟎 − 𝜶𝒉𝒉
'!()*+,- /-)0--+ 1 *+' 1
where the reflection coefficient 𝜶 = '!()*+,- /-)0--+ 1! *+' 1# > 0
$ #
𝟏
and the centroid 𝑿𝟎 = ∑𝒏𝒊5𝟏 𝑿𝒊
𝒏
𝒊6𝒉
𝒉𝒉 = 𝒎𝒂𝒙 𝒇(𝑿𝒊 )
Replace 𝑿𝒉 by 𝑿𝒓 if 𝒇(𝑿𝒍 ) < 𝒇 𝑿𝒓 < 𝒇(𝑿𝒉 )
10
5
02/05/2025
11
12
6
02/05/2025
Nelder-Mead (Simplex) Method
• Three main steps of Simplex method are:
• Expansion
• If reflection has created a new best solution i.e., 𝑓(𝑋8 ) < 𝑓 𝑋9
• Expand or move along the direction of 𝑿𝒓 to further reduce the objective
function value
• Expansion then expands 𝑋8 to 𝑋-
• 𝑿𝒆 : Expansion point obtained
𝑿𝒆 = 𝜸𝑿𝒆 + 𝟏 − 𝜸 𝑿𝟎
'!()*+,- /-)0--+ 1 *+' 1
where the expansion coefficient 𝜸 = '!()*+,- /-)0--+ 1% *+' 1#
! #
Replace 𝑿𝒉 by 𝑿𝒆 if 𝒇(𝑿𝒍 ) < 𝒇 𝑿𝒆 < 𝒇(𝑿𝒍 ) and restart the reflection process
or
Replace 𝑿𝒉 by 𝑿𝒓 if 𝒇(𝑿𝒆 ) > 𝒇 𝑿𝒍 go to reflection process again
13
Nelder-Mead (Simplex) Method
• Three main steps of Simplex method are:
• Contraction
• If reflection has created a very poor solution i.e., 𝑓(𝑋% ) > 𝑓 𝑋$ for all 𝑖 except 𝑖 = ℎ
and𝑓(𝑋% ) < 𝑓 𝑋&
• Contraction contracts 𝑋& to 𝑋'
• 𝑿𝒆 : Expansion point obtained
𝑿𝒄 = 𝜷𝑿𝒉 + 𝟏 − 𝜷 𝑿𝟎
,$-./#'0 20.300# 4% /#, 4#
where the expansion coefficient 𝜷 = and
,$-./#'0 20.300# 4$ /#, 4#
0≤𝜷≤𝟏
Replace 𝑿𝒉 by 𝑿𝒄 if 𝒇(𝑿𝒄 ) < 𝒎𝒊𝒏[𝒇 𝑿𝒉 , 𝒇 𝑿𝒓 ] and proceed with the reflection process
or
(4&84')
Replace all 𝑿𝒊 by if 𝒇(𝑿𝒄 ) ≥ 𝒎𝒊𝒏[𝒇 𝑿𝒉 , 𝒇 𝑿𝒓 ] and restart the reflection process
"
14
7
02/05/2025
15
16
8
02/05/2025
17
18
9
02/05/2025
19
10