L6 - Nelder Mead Downhill Simplex Flashcards
What does the Downhill Simplex Algorithm do?
Finds the maximum or minimum of a scalar valued objective function in a multi-variate space.
Define a Scalar Valued Objective function
A function that maps vector to scalar. I.e Takes in multiple input values and outputs a single (scalar) value.
What is multivariate space?
Multidimensional space. In this case, we are referring to a space containing multiple varaibles.
What 3 constructs does the Nelder Mead downhill simplex algorithm consist of? Define each…
Simplex - A geometric figure in the Dth dimension with D+1 vertices.
Labelled Coordinates - Ranking the D+1 vertices based on their function value with best, good, worst.
Centroid - The centre point between the best and good vertices.
What is the formula to find the centroid?
C = 1/D( B + G )
How does the Nelder Mead find the min scalar value?
Iteratively replaces the worst vertex with a better one. Repeats until the vertices of the simplex are sufficiently close (usually determined by some threshold set).
What are the 4 operations performed on the worst vertex of the simplex in order to replace it with a more optimal point?
- Reflection - Reflect the worst vertex about the centroid to create R.
The run the function on R. Accept R if it’s less than the good vertex G, otherwise perform Expansion. - Expansions - if f(R) > f(G), expand R to create expanded point E. If f(E) < f(R), replace W with E. This means we are moving towards the functions minimum. Otherwise, perform contraction.
- Contraction - if expansion didn’t work, we focus on R again. If f(R) > f(G) we perform contraction.
We find M1, M2. M1 is mid-point between W and C, M2 is mid-point between R and C.
Accept M1 if f(M1) < f(W) and f(M1) < f(M2)
Accept M2 if f(M2) < f(W) and f(M2) < f(M1) - Shrink - If none of the above worked. Move all vertices closer to the best vertex, shrinking the simplex.
What are the 3 convergence criteria’s often used?
Domain convergence - All simplex vertices are sufficiently close.
Function convergence - All function values are sufficiently close.
Timeout - Max. number of iterations has occured.
What algorithm is used to test the performance of the Nelder Mead algorithm? When does it stop?
Rosenbrock Test Function is used to test performance of optimisation algorithms.
It stops when it returns xi = 1.
What 2 behaviours of the algorithm guarantee conversion?
- Vertices are decreasing on each iteration.
- Simplex angles are uniformly bound between 0 - 90 degrees.
Which parts of the algorithm are the most computationally expensive?
- Sorting vertices
- Function evaluation - Very high!
- Centroid Calculation
Why is the Shrink stage rarely used?
High computational cost.
Explain the Reflection step… What is the intuition behind this step…
Intuition - Moving from W to B or G leads W to a more optimal value. Thus, reflecting W about C should create a more optimal point R such that f(R) < f(W).
Reflect W about C to create R. If f(R) < f(W) we know we are moving in the right direction. Thus, we perform expansion to establish an even more optimal point E. If f(R) >= f(W) we perform contraction.
Explain the Expansion step… What is the intuition behind this step…
Intuition - After reflection, if we know f(R) < f(W), we know that if we expand we will find a more optimal point E.
We expand such that E = 2R - M
Explain the contraction step…
If after reflection f(R) > f(W), we perform contraction.
We find M1 and M2 in the middle of W → C and C → R.
We assign M with the lowest out of M1 and M2 to create a new simplex → BGM
However, if f(M) >= f(W), we perform shrinkage.E
