Home / Courses / Optimization / Derivative-Free

Optimization · Module 9 of 10

Derivative-Free and Global Optimization

Sometimes there is no gradient: the objective is a black-box simulation, or noisy, or riddled with local minima. Derivative-free methods search with function values alone, and global methods try to escape local traps.

01

Readiness check

This module searches without gradients. Tick only what you can do closed-notes.

  • Evaluate a function at several points.
  • Recall a unimodal function has one minimum on an interval.
  • Compare function values to find the smaller.
  • Find the centroid of a set of points.
  • Recall the difference between a local and a global minimum.
0 or 1 weak itemsContinue with this module.
2 weak itemsContrast with gradient methods in Module 3.
3 or more weak itemsConnect to computation in Programming and Computation.
02

The core idea

Derivative-free methods optimise using only function values, by cleverly sampling and comparing. Golden-section search brackets a one-variable minimum; Nelder-Mead crawls a simplex downhill; global methods sample broadly to escape local minima.

golden section: shrink a bracket by 0.618 each stepNelder-Mead: reflect the worst vertexglobal: sample widely to escape local traps

Gradient methods are fast, but they need a gradient, and many engineering objectives do not offer one cleanly: a black-box simulation, a noisy experiment, or a function with kinks. Derivative-free methods work from function values alone. For one variable, golden-section search brackets the minimum of a unimodal function and shrinks the bracket by the golden ratio (about 0.618) each iteration, keeping one interior evaluation for reuse, a guaranteed, steady contraction. For several variables, the Nelder-Mead simplex keeps a set of n + 1 points and repeatedly replaces its worst vertex by reflecting it through the centroid of the rest, expanding or contracting to crawl downhill without any derivative. These methods find a local minimum. When the objective has many local minima, global methods, such as random restarts, simulated annealing, or genetic algorithms, sample the space broadly and accept occasional uphill moves to escape traps, trading guarantees and speed for a better chance at the global optimum.

The skill works when: you sample and compare values systematically, shrinking toward the minimum.
The skill breaks down when: a multimodal objective is treated as unimodal, or a local method is trusted to find a global optimum.
The concept. Derivative-free methods probe the objective with sample points and move toward lower values. A multimodal landscape has several local minima, which global methods sample broadly to escape.
03

The skills, taught in order

Five skills build one-variable search, the Nelder-Mead simplex, and global strategies.

9.1 When derivatives are unavailable

A gradient may be missing because the objective is a simulation, an experiment, or a noisy or non-smooth function. Derivative-free methods need only the ability to evaluate f, at the cost of slower convergence than gradient methods.

9.2 Golden-section search

For a unimodal function on an interval, golden-section search places two interior points and discards the sub-interval that cannot contain the minimum, shrinking the bracket by a factor of about 0.618 each step. Its use of the golden ratio lets one interior point be reused, saving an evaluation.

MethodDimensionIdea
Golden sectionone variableshrink a bracket by 0.618
Nelder-Meadseveral variablesreflect the worst simplex vertex
Pattern searchseveral variablesprobe along coordinate directions
Global (genetic, annealing)many variablessample broadly, accept uphill moves

Derivative-free methods span one-variable brackets to population-based global search, all using values only.

9.3 The Nelder-Mead simplex

Nelder-Mead maintains a simplex of n + 1 points and improves it by geometric moves: reflect the worst vertex through the centroid of the others, then expand if that helped or contract if it did not. The simplex tumbles downhill toward a local minimum without a derivative.

9.4 Pattern and coordinate search

Pattern-search methods probe along a set of fixed directions, accepting any move that lowers the objective and shrinking the step when none does. They are simple, robust to noise, and come with convergence guarantees under mild conditions.

9.5 Global optimization

When many local minima exist, local methods get stuck. Global strategies, random restarts, simulated annealing, and genetic algorithms, sample the space widely and sometimes accept worse points to escape a basin, improving the odds of finding the global optimum at the cost of many more evaluations.

Engineering connection: optimising a shape through a black-box simulation, or tuning many parameters with no gradient, is exactly where these methods earn their keep.

04

Worked example 1: one step of golden-section search

Minimise f(x) = (x − 2)2 on the interval [0, 5] with golden-section search. Place the two interior points, compare, and give the reduced interval.

Figure 1. Two interior points split the interval by the golden ratio. Since the left point has the lower value, the right sub-interval is discarded, shrinking the bracket to [0, 3.09].
  1. ProblemTake one golden-section step for the function in Figure 1.
  2. Given / findf(x) = (x − 2)2, [a, b] = [0, 5]. Find the interior points, compare, and give the new interval.
  3. Assumptionsf is unimodal on [0, 5], so bracketing applies.
  4. ModelWith r = 0.618, x1 = a + (1 − r)(b − a), x2 = a + r(b − a); keep the side with the lower value.
  5. Equationsx1 = 0 + 0.382(5) = 1.91x2 = 0 + 0.618(5) = 3.09
  6. Solvef(x1) = (1.91 − 2)2 = 0.008; f(x2) = (3.09 − 2)2 = 1.19. Since f(x1) < f(x2), discard the right part: new interval [0, 3.09].
  7. CheckThe new interval width is 3.09 = 0.618 × 5, the guaranteed golden-ratio reduction, and it still contains the true minimiser x = 2.
  8. ConclusionOne step shrinks the bracket from [0, 5] to [0, 3.09] while keeping the minimum, using only two function evaluations.
Result. New bracket [0, 3.09], a 0.618 reduction containing the minimum.
05

Worked example 2: a Nelder-Mead reflection

For f(x, y) = x2 + y2, a Nelder-Mead simplex has vertices B = (1, 0) and G = (0, 1) with value 1, and worst vertex W = (1, 1) with value 2. Reflect the worst vertex through the centroid of the others and evaluate the new point.

Figure 2. The worst vertex is reflected through the centroid of the other two. The reflected point lands on the minimum with value zero, so the simplex accepts it and moves downhill.
  1. ProblemPerform one Nelder-Mead reflection for the simplex in Figure 2.
  2. Given / findf = x2 + y2; B = (1, 0), G = (0, 1), worst W = (1, 1). Find the reflected point and its value.
  3. AssumptionsStandard reflection coefficient 1; centroid taken over all vertices except the worst.
  4. ModelCentroid M of {B, G}; reflection R = M + (M − W) = 2M − W.
  5. EquationsM = ((1 + 0)/2, (0 + 1)/2) = (0.5, 0.5)R = 2M − W = (1, 1) − (1, 1) = (0, 0)
  6. SolveR = (0, 0), f(R) = 0 + 0 = 0. Since f(R) = 0 is better than the current best (1), the reflection succeeds and W is replaced by R.
  7. CheckThe reflected point is exactly the true minimum of x2 + y2, so the simplex has moved onto the optimum, using only function evaluations and simple geometry.
  8. ConclusionOne reflection replaces the worst vertex with the minimum (0, 0). Nelder-Mead crawls downhill by such moves with no gradient at all.
Result. Reflected point (0, 0) with f = 0, accepted as the new vertex.
06

Misconceptions and diagnostics

MistakeSymptomDiagnostic questionCorrection
Assuming unimodalityGolden section misses the true min"Is the function unimodal here?"Bracketing needs one minimum in the interval.
Local method for a global goalStuck in a nearby basin"Are there several local minima?"Use restarts or a global method.
Forcing gradients on a black boxNoisy or meaningless derivatives"Can I even compute a gradient?"Use a derivative-free method on black-box objectives.
Too few evaluations for globalGlobal search reports a poor point"Did I sample the space widely?"Global methods need many evaluations to be reliable.
07

Practice ladder

Level 1 · Direct skill

On [0, 10] with the golden ratio 0.618, find the two interior points.

Show answer

x1 = 0.382 × 10 = 3.82, x2 = 0.618 × 10 = 6.18.

Level 2 · Mixed concept

For f(x) = (x − 4)2 on [0, 10], which sub-interval survives the first step?

Show answer

f(3.82) = 0.032 < f(6.18) = 4.75, so keep the left part, [0, 6.18].

Level 3 · Independent problem

A Nelder-Mead simplex for f = x2 + y2 has best (0, 1), good (1, 0), worst (2, 2). Find the reflected point.

Show answer

M = ((0 + 1)/2, (1 + 0)/2) = (0.5, 0.5). R = 2M − W = (1, 1) − (2, 2) = (−1, −1), f = 2, better than the worst's 8, so accept.

Transfer task | Real engineering

You optimise a shape through a CFD simulation with no gradient and suspect several local optima. Describe a sensible strategy.

What good work looks like

Use a derivative-free local method (Nelder-Mead or pattern search) from several random starts, or a global method (genetic algorithm), accepting the extra simulations; compare the best results and refine the winner locally.

08

Working with AI, and proving it yourself

Use AI as an examiner, not a solver

"Check that my golden-section interval shrank by the right factor."
"Give me three simplexes; I will compute the reflection of each."
"Optimise the black box for me." Sampling and comparing is the skill.
"Is this the global minimum?" Reasoning about multimodality is the point.

Portfolio task

Optimise a derivative-free objective with golden section or Nelder-Mead, then test for global optimality with several restarts, and report the best point found.

Must include: the search steps, a convergence check, and a multi-start global test.
09

Retrieval and spaced review

Closed notes. Answer out loud, then reveal.

1. When are derivative-free methods needed?

When the objective is a black box, noisy, or non-smooth, so no gradient is available.

2. How does golden-section search progress?

It shrinks the bracket by about 0.618 each step, reusing one interior point.

3. What is the core Nelder-Mead move?

Reflecting the worst simplex vertex through the centroid of the others.

4. What do global methods do differently?

They sample broadly and accept uphill moves to escape local minima.

5. What is the cost of global methods?

Many more function evaluations, with weaker guarantees.

TodayFinish this quiz and Levels 1 and 2 of the ladder.
+1 dayRe-run the golden-section and reflection steps from a blank page.
+3 daysSearch three new objectives without gradients.
+7 daysBalance competing objectives, Module 10.
+30 daysReuse a derivative-free method on a black-box simulation.
10

Textbook mapping

This module follows Nocedal and Wright, Numerical Optimization, 2nd edition. Use these references to read further.

Topic in this moduleWhere to read more
Derivative-free optimization and Nelder-MeadNocedal & Wright, Chapter 9
Pattern and coordinate searchNocedal & Wright, Chapter 9
Golden-section and global methodsStandard optimization references

Chapter numbers refer to the 2nd edition; one-variable and global heuristics draw on standard optimization references. The methods are standard, so any recent edition will align closely.