Module 16 · Lesson 16.3
No free lunch, and knowing when to stop
Why there is no best algorithm, and why every stopping criterion is a decision about what you are willing to miss.
Why this matters
Two questions come up at the end of every optimisation exercise, and they have unsatisfying answers that are worth having anyway: which method should I use? and when do I stop?
The first has a theorem attached. The second does not, and is the more consequential in practice.
By the end of this lesson you should be able to
- State the No Free Lunch result and what it does and does not claim
- Read a best-so-far curve and use it to judge a stopping point
- List the common stopping criteria and what each gives up
- Report an optimisation result with the qualifiers it needs
No free lunch
Averaged over all possible objective functions, every search algorithm performs identically. A method that does better than random on one class of problem must do worse than random on another, by exactly as much.
That sounds like a counsel of despair and it is not, because engineering problems are not drawn uniformly from all possible functions. They have structure — smoothness in places, monotonicity in others, physical relationships between variables — and a method matched to that structure genuinely does better.
What the result actually forbids is the claim that some method is best in general. It is a warning against a particular kind of marketing, and a licence to choose a method because it suits your problem rather than because it is fashionable.
The demonstration is in the lab: gradient descent wins outright on the smooth landscape, finding the exact optimum in 79 evaluations where every other method spent 441 and did worse. On the rugged landscape the same method is beaten by four of the five others. Neither result is a fact about the method's quality.
Stopping
Every run stops for one of four reasons, and each gives something up:
A fixed evaluation budget. Simple, predictable, and completely uninformed about whether the search was still improving.
Convergence — the best-so-far has not improved for N evaluations. Sensible, and it can stop a stochastic method during a long plateau that it was about to escape.
A target value. Stop when the objective is good enough. This is often the right criterion in engineering, because 'good enough' is a real concept here in a way it is not in mathematics — a design that satisfies every constraint with a sensible margin does not become better by being 2 % lighter.
Diminishing returns. Stop when the improvement per evaluation falls below what it is worth. The most defensible and the hardest to specify.
Stopping early risks missing a better design. Stopping late spends time for nothing. There is no criterion that avoids both, and the choice should be recorded with the result.
The best-so-far curve
Plot the best value found against the number of evaluations. It only ever falls, and its shape is what tells you whether to continue:
- A steep early fall then a long flat stretch: probably converged, and further evaluations are buying little.
- A staircase — flat, then a sudden drop, then flat again: the method is escaping basins, and stopping during a flat stretch would have missed the drop.
- Still falling steadily at the budget: you stopped too early, and the result should say so.
The staircase is the reason a convergence criterion is dangerous with a stochastic method. A genetic algorithm can sit on a plateau for twenty generations and then find something substantially better.
Reporting
An optimisation result needs five things beside the number:
- 1.The objective, and what it stands for if it is a proxy.
- 2.The constraints, including any that turned out to bind.
- 3.The method, and the starting point or seed.
- 4.The evaluations spent, and why the search stopped.
- 5.Whether the result was reached from more than one start, and whether they agreed.
Without those, 'the optimum is 84 tonnes' is not a reviewable statement.
Worked example
Reading two best-so-far curves
Given
- Two runs on the rugged landscape, both with a budget of 441 evaluations
- Run A: falls quickly to 1.46 by evaluation 60, then flat for the rest
- Run B: sits at 1.60 until evaluation 210, drops to 1.15, then flat
Find
What each curve says about stopping
Check yourself
What does the No Free Lunch result actually forbid?
Practice
A search improves the objective from 240 to 186 in its first 100 evaluations, then to 181 over the next 400. What is the improvement per evaluation over the second stretch, as a percentage of the objective per hundred evaluations?
Practice
On the rugged landscape the global optimum is 1.150 and a gradient run from an unlucky start returns 1.457. By what percentage does that run overstate the objective?
Check yourself
What does 'no free lunch' actually claim?
Check yourself
An optimisation report says 'the optimum design has a mass of 4 260 kg'. What is wrong with that sentence?
Summary
- No Free Lunch forbids the claim of general superiority, not the choice of a method suited to your problem
- Gradient descent won the smooth landscape outright and lost the rugged one to four methods out of five
- A best-so-far curve's shape says whether to continue; a staircase means the method is still escaping basins
- A convergence criterion cannot tell 'converged' from 'on a plateau'
- Report the objective, constraints, method, start, budget, stopping reason and whether several starts agreed
- Running from a second start is the cheapest insurance available
This is educational material. It uses simplified examples to teach principles, and must not be relied on for real design or safety-critical decisions. Module overview and checkpoint