Optimization Techniques: Convex vs. Non-Convex, Nelder-Mead Simplex Algorithm

Convex vs. Non-Convex Optimization

  • Optimization tasks fall into two main categories:
    • Convex optimization: Objective function is convex.
    • Non-convex optimization: Objective function is non-convex.
  • Importance of identifying convexity:
    • Easier to find the optimal solution.
    • Avoidance of local optima: Convex optimization guarantees that any minimum found is the global minimum.
  • Differentiable functions:
    • If a function y(x)y(x) is differentiable, its derivative (gradient) can be used to find the minimum.
    • Example: If y(x)=x2y(x) = x^2, then dydx=2x\frac{dy}{dx} = 2x. Setting 2x=02x = 0 gives x=0x = 0, which is the global minimum. Substituting x=0x = 0 back into y(x)y(x) gives the global minimum value.
  • Many real-world problems are non-convex.

Bracketing and Complex Functions

  • Bracketing is useful for relatively simple functions.
  • For complex functions, more sophisticated methods are needed.

Nelder-Mead Simplex Algorithm: Finding Water on Mars

  • Scenario: Finding water on Mars using a device to test soil humidity.
  • Initial Steps:
    • Take three random samples: identify the best (b), good (g), and worst (w) points based on humidity levels.
    • Objective: Determine the best direction to move to find more water.
  • Algorithm Steps
    • Reflection: Find the midpoint (centroid) between the best (b) and good (g) points.
    • Calculate the reflective point (r) by "flipping" the worst point (w) across the centroid.
    • Evaluate the reflective point (r).
    • If r is better than g (but not better than b), replace w with r and proceed to the next iteration.
    • Expansion: If r is better than both g and b, consider moving even further in the same direction.
    • Calculate an expansion point (e) by doubling the distance from the centroid to the reflective point.
    • If e is better than r, accept e; otherwise, accept r.
    • Contraction: If r is worse than g, perform a contraction.
      • Calculate two contraction points (m1 and m2) either inside or outside of the current simplex.
      • Accept the better of m1 and m2.
    • Shrink: If both contraction attempts fail, shrink the simplex by halving the distance from the best point to the other two points.
  • Mathematical Representation:
    • Centroid Calculation: The centroid cc between two points bb and gg with coordinates (x<em>1,y</em>1)(x<em>1, y</em>1) and (x<em>2,y</em>2)(x<em>2, y</em>2) is calculated as: c=(x<em>1+x</em>22,y<em>1+y</em>22)c = (\frac{x<em>1 + x</em>2}{2}, \frac{y<em>1 + y</em>2}{2}).
    • Reflection Point Calculation: r=c+α(c−w)r = c + \alpha (c - w), where α\alpha is the reflection coefficient (typically 1).
    • Expansion Point Calculation: e=c+γ(c−w)e = c + \gamma (c - w), where γ\gamma is the expansion coefficient (typically 2).
    • Contraction Point Calculation: m=c−β(c−w)m = c - \beta (c - w), where β\beta is the contraction coefficient.
  • Key Idea: Iteratively improve the simplex (triangle) by moving towards better solutions.
  • Advantage: Computationally cheap and easy to implement.

Simplex in Detail

  • Simplex: A geometric concept.
    • In d dimensions, a simplex consists of d+1 points.
    • 1 dimension: a line connecting two points.
    • 2 dimensions: a triangle (3 points).
    • 3 dimensions: a tetrahedron (4 points).
  • Algorithm Visualization:
    • Imagine a triangle on Mars that changes shape and moves until it reaches the water point.
  • Centroid Calculation (Mathematically):
    • For points b and g with coordinates (x<em>b,y</em>b)(x<em>b, y</em>b) and (x<em>g,y</em>g)(x<em>g, y</em>g), the centroid cc is: c=(x<em>b+x</em>g2,y<em>b+y</em>g2)c = (\frac{x<em>b + x</em>g}{2}, \frac{y<em>b + y</em>g}{2}).
    • Example: If b=(1,2)b = (1, 2) and g=(3,4)g = (3, 4), then c=(1+32,2+42)=(2,3)c = (\frac{1+3}{2}, \frac{2+4}{2}) = (2, 3).
  • Reflecting the Worst Vertex:
    • The reflected point rr is calculated as: r=c+α(c−w)r = c + \alpha (c - w), where α\alpha is typically 1.
  • Expansion:
    • If rr is better than gg, try expanding to point ee using: e=c+γ(c−w)e = c + \gamma (c - w), where γ=2\gamma = 2.
  • Contraction:
    • If rr is worse than gg, contract to a point mm using: m=c−β(c−w)m = c - \beta (c - w), where β\beta is a contraction factor.
    • Choose the better point between contracting inside or outside.

Overall Algorithm Summary

  1. Initialization: Start with an initial simplex.
    • Choosing the initial simplex can impact performance; try multiple initial values.
  2. Iteration: Repeat until convergence.
    • Order points by their values (e.g., from minimal to maximal).
    • Calculate the centroid cc.
    • Attempt to replace the worst point (w) using reflection, expansion, or contraction.
    • If all attempts fail, shrink the simplex.

Convergence Conditions

  • Stopping criteria for the algorithm:
    • Domain Convergence: Points are sufficiently close together.
    • Useful for discontinuous functions.
    • Function Convergence: Function values at the points are nearly the same.
    • Time Convergence: Stop after a maximum number of iterations to prevent infinite loops.

Algorithm Benchmarking

  • Comparison with Other Algorithms:
    • Many nature-inspired algorithms exist (e.g., bee-inspired algorithms).
    • Need benchmarks to compare their performance.
  • Rosenbrock (Banana) Function:
    • A common test function for optimization algorithms.
    • Minimum at the corner (e.g., (1, 1) in 2D).
    • Use to test how quickly an algorithm can reach the minimum.

Implementation Details and Improvements

  • Workshop Exercise: Implement the Nelder-Mead algorithm.
  • Comparison with Powell's Algorithm:
    • Powell's algorithm may be faster in some cases, but Nelder-Mead is more intuitive.
  • Efficiency Tips:
    • Sorting: Insertion sort can be efficient if the list is mostly sorted.
    • Centroid Calculation: Use computational tricks to update the centroid without recalculating it from scratch.
  • Convergence Guarantees:
    • Difficult to prove convergence mathematically, but empirical observations can help.
    • If function values are always decreasing, it indicates convergence.
    • Maintaining a non-degenerate simplex also helps.
  • Existing Implementations:
    • Many programming languages (e.g., Python's SciPy library) have built-in implementations of Nelder-Mead.

Advantages and When to Use

  • Advantages:
    • Uses only function evaluations; no need to calculate gradients.
  • When to Use:
    • For well-behaved functions, try gradient-based methods (e.g., Powell's method).
    • For general, difficult-to-differentiate functions, try the Nelder-Mead simplex algorithm.