Computational Engineering / Optimisation algorithms
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.
Lesson review: expert verification remains open
This lesson has received a full-context editorial review and a check of its technical explanations. Selected arithmetic has been checked separately. This is not independent engineering sign-off.
Checks needed for project use
- A computational engineering reviewer must check algorithms, convergence claims, statistical assumptions and numerical examples beyond the cases explicitly recorded.
- Reproduce quoted algorithm evaluation counts and reference minima from the actual seeded lab before treating them as verified benchmark results.
These are educational models and exercises. Check their assumptions before using the results. The full technical content and every diagram have not yet been independently verified.
Concrete and steel calculations retain their stated first-generation Eurocode teaching basis. Use the standards and amendments specified for your project; do not mix generations without an appropriate design basis.
Read the lesson register and outstanding review notesWhy 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
Classical No Free Lunch results compare search algorithms averaged uniformly over all functions in specified finite problem spaces, under their sampling assumptions. They do not say that algorithms perform equally on engineering problems or that every continuous optimisation problem falls within the theorem. A method can exploit structure in a relevant problem class.
Stopping
Possible criteria include a fixed budget, a target objective, small improvements, small optimality residuals or a certified bound gap where available. A plateau in the best sampled value is not proof of convergence, for deterministic or stochastic search. Continued improvement at a budget limit should be reported, but does not alone mean the agreed stopping decision was wrong.
Plot best feasible value against evaluation count and record the feasibility tolerance. For minimisation this incumbent curve cannot increase if previously found candidates are retained. Several runs can help assess variability, although they do not prove global optimality.
Report the objective, constraints, method, start or seed, computational cost, stopping criterion, repeated-run evidence and any genuine optimality certificate. These details let a reviewer distinguish a useful candidate from a proved optimum.
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