Teaching objectives
How do you look for the lowest point of a landscape you cannot see? The optimizer does not have the formula: it can only point at a spot and ask how much the function is worth there, and each question costs — in a real problem it can be an eight-hour simulation. This lab goes through seven ways of spending those questions, from throwing random darts to swarms and evolving populations, and makes them compete on the same budget over very different terrains. Second of the Optimization trilogy, after Linear optimization. Aimed at university level.
What is learned
- Measuring a search: the function evaluation as the unit of cost, the convergence curve on a logarithmic scale, and the difference between the error in value and the error in position (rooms 1-7).
- The trade-off between exploring and exploiting, which reappears in every method under a different name — step, temperature, inertia, selection pressure — and which always offers two ways of getting it wrong (room 8).
- Why the number of variables sinks methods that sample blindly: the curse of dimensionality and its practical consequences (room 9).
- Local search, its local optima, and the only two escapes: restarts (rooms 10-13) and accepting a move for the worse, which leads to simulated annealing with its Metropolis criterion and cooling schedule (rooms 14-17).
- Population methods: particle swarm with its cognitive and social pulls and its inertia (rooms 18-21), and the genetic algorithm with selection, crossover, mutation, elitism and diversity (rooms 22-25).
- The two deterministic methods: the Nelder-Mead simplex and gradient descent, and the four concrete ways in which the gradient crashes (rooms 26-28).
- Comparing rigorously: same budget, several seeds, and winners that change when noise or dimensions are added. The no free lunch theorem and what it says exactly (rooms 29-32).
Key mathematical ideas
- Comparing two methods requires giving them the same thing, and the only thing that can be counted identically for all of them is the number of objective function evaluations. Not seconds, which measure the computer, nor iterations, which do not mean the same in a swarm as in a local search. In that currency, a gradient approximated by finite differences is not free: it costs d+1 evaluations per step.
- Since all these methods use randomness, one run is not a result. The honest thing is to give the median of several and say how many there were. The probability that at least one of N attempts succeeds is P = 1 − (1 − p)^N, a formula that reappears in restarts and in swarm size — with the twist that, on a fixed budget, the p of each attempt depends on how many attempts you make.
- Random search improves like N^(−2/d): on a log-log scale it is a straight line of slope −2/d. Gaining one digit of precision costs multiplying the evaluations by 10^(d/2).
- A method that only accepts improvements cannot leave a local minimum, by definition. Its success probability is the area of the basin of attraction of the global optimum divided by the total area.
- The Metropolis criterion, P = e^(−Δf/T), translates physical annealing into optimization: the temperature is measured in the units of the function, and the logarithmic cooling that guarantees the global optimum takes longer than the age of the universe.
- On a logarithmic scale, a descending straight line is linear convergence (the error is multiplied by a fixed factor) and a flattening curve is sublinear: the usual price of not using derivatives.
- The crossover of a genetic algorithm is a bet on the structure of the problem: it multiplies performance on separable functions and contributes nothing when the variables are coupled (epistasis).
- The Wolpert and Macready theorem says that, averaged over all possible objective functions, all methods perform the same. It does not say it makes no difference which you choose: it says a method's advantage always comes from assuming something about the problem, and that almost no imaginable function satisfies those assumptions. Methods work because the world has structure.
Room-by-room contents
Room 1 · The invisible landscape
The map starts covered in fog: only the colour of the points the student has evaluated is visible, together with its numeric value. In twelve clicks the error must be brought below 0.05 in a bowl whose minimum is at the centre. The room establishes the idea holding up the whole lab: the optimizer does not see the terrain, it can only ask for the value of the function at specific points, and each question costs.
Student tasks
- Find the minimum by hand, reading the uncovered values and deciding where to go next.
- Recognize what information an optimization method actually has.
Room 2 · Throwing darts
Pure random search: N uniform points, keep the best. A slider controls N and a picker changes landscape. The room establishes the normalized error (0 at the optimum, about 1 at a random point) that makes landscapes of very different magnitudes comparable, and it turns out that doubling the darts halves the error in dimension 2.
Student tasks
- Throw darts with different values of N and on different landscapes.
- Work out experimentally how the error divides when the number of darts is doubled.
Room 3 · One run is not a result
The same configuration is run fifty times and the histogram of errors is drawn with its median and percentiles. This is the room that teaches how to report a stochastic method honestly, and out of it comes the formula P = 1 − (1 − p)^N that will reappear three more times through the lab.
Student tasks
- Compare how wide the cloud of results is on different landscapes and budgets.
- Compute how many independent runs are needed for a given reliability.
Room 4 · The currency of this lab
The unit of measurement for the whole lab is fixed: the evaluation of the objective function. Not seconds (they measure the computer) nor iterations (they do not mean the same in different methods). A table shows four configurations that look very different and cost exactly the same.
Student tasks
- Count the evaluations a given swarm configuration spends.
- Reason about what happens to a method with a large population and a small budget.
Room 5 · The convergence curve
The representation by which every method will be judged is introduced: the best value found so far against the evaluations spent, with the vertical axis on a logarithmic scale. Three curves of the same method in dimensions 2, 3 and 5 show that what changes with dimension is not the shape but the slope.
Student tasks
- Read from the curve how many evaluations are needed to reach a given precision.
- Interpret what it means (and what it does not mean) for a curve to go flat.
Room 6 · Error in what?
The error in value is distinguished from the error in position by clicking anywhere on the map and reading both at once. Three landscapes make it evident: on the plateau and in the valley you can be very far away with an almost perfect cost, and on the staircase the minimum is not a point but a whole region.
Student tasks
- Explore points on the plateau, the staircase and the valley comparing the two errors.
- Decide which error matters in a concrete application.
Room 7 · What converging means
Four real curves from the lab with four different endings: converging to the global, converging to a local, stalling and not converging. Students learn that on a logarithmic scale a straight line means linear convergence (the error is multiplied by a fixed factor) while a flattening curve means sublinear convergence.
Student tasks
- Classify the four curves by their ending.
- Compute how many evaluations a linearly convergent method needs for a given precision.
Room 8 · Explore or exploit
The hinge room of the lab. A single dial — the jump size sigma — with both failures visible: with a small sigma the method never leaves the pit it fell into, and with a large one it never finishes refining. Performance against sigma draws a very clear U, and it is announced that every method to come is a different way of turning this same dial.
Student tasks
- Sweep the slider and locate the sigma of optimal performance on the egg box.
- Diagnose, from a flat curve, which way the dial must be turned.
Room 9 · The curse of dimensionality
With a box of side 10 and a good zone of side 1, every dimension added multiplies the darts needed by ten. The table reaches 10^10 in dimension 10, and a live experiment confirms that random search goes from 36 evaluations in dimension 2 to more than two thousand in dimension 5 for the same precision.
Student tasks
- Compute the expected darts needed to hit in dimension 6.
- Check in the experiment how random search scales with dimension.
Room 10 · Looking around
The first method that uses what it has seen: stay where things go well and propose a nearby point. The first real parameter appears, sigma, and a budget challenge asks students to choose it so as to get below a given error with only 200 evaluations, checked over 21 seeds so that a lucky hit does not count.
Student tasks
- Move sigma and watch the trail of the search on the map.
- Beat the budget challenge by choosing a sigma that works on most seeds.
Room 11 · The trap
The same method on the egg box, where only 1% of starts reach the global minimum. The student clicks anywhere on the map to release a search from there and see where it ends. Local minimum and basin of attraction are defined, and it becomes clear that a method accepting only improvements can never leave a local minimum.
Student tasks
- Release searches from different points and note how many reach the global minimum.
- Compute how many starts are needed for a given success probability.
Room 12 · Starting over
The first escape: split the budget among several restarts. The performance curve against the number of restarts is a U again, because every extra restart shortens all the others. The room 3 formula is generalized to the case where the success probability depends on the number of attempts itself.
Student tasks
- Use the slider to find the number of restarts that minimizes the typical error.
- Explain why a very high number of restarts turns the method into random search.
Room 13 · The step that learns
Rechenberg's one-fifth rule makes sigma tune itself according to the acceptance rate. A graph shows sigma decreasing on its own through the run. And the room ends with the uncomfortable result: on the bowl the adaptive step improves things by six orders of magnitude, and on the egg box it makes them ten times worse, because inside a false pit the high acceptance rate makes sigma close in on itself.
Student tasks
- Compare fixed and adaptive sigma on both landscapes.
- Diagnose why the mechanism fails precisely when it works well.
Room 14 · One step back
The second escape from local optima: accepting a worsening with a fixed probability p. The two extremes are already familiar methods (p = 0 is local search, p = 1 is a random walk) and the optimum is around 0.2, seven times better than never accepting. The room closes by pointing out the flaw of a fixed p: it treats a tiny stumble and a disaster alike.
Student tasks
- Find the probability minimizing the typical error on the egg box.
- Explain why accepting everything is also bad.
Room 15 · Temperature
The Metropolis criterion: P = e^(−Δf/T). An interactive graph shows the acceptance probability against how much a proposal worsens, for different temperatures. Emphasis is placed on a detail almost never explained and causing much grief: T is measured in the units of f, so a lukewarm temperature on one landscape is frozen solid on another.
Student tasks
- Compute concrete acceptance probabilities with the formula.
- Solve for the temperature that accepts a given worsening half the time.
Room 16 · Cooling down
T0 and the cooling factor alpha appear, with the temperature-over-time graph above the convergence curve it produces. The two failures are cooling too fast (the rest of the budget is trapped local search) and not cooling (the method ends up wandering). A budget challenge asks for a pair (T0, alpha) that solves the needles on at least 4 of 5 seeds.
Student tasks
- Try the three cooling schedules and see the shape of each curve.
- Beat the challenge by finding a pair (T0, alpha) that works on most seeds.
Room 17 · Duel: annealing against local search
Same budget, same step, five landscapes, forty-one seeds. The result is deliberately uncomfortable: annealing wins where there are traps (the egg box, the needles) and clearly loses where there are none (the bowl, the valley), because every accepted worsening is an evaluation spent going backwards. It is the first explicit appearance of the thesis of the lab.
Student tasks
- Run the duel and read the table landscape by landscape.
- Explain why the more sophisticated method loses on the easiest terrain.
Room 18 · A swarm
Several searchers at once, with the budget shared among them. For now without communication, to isolate the effect of number alone. The budget challenge of this room is the most striking of the lab: with exactly ten steps, students must find the minimum number of particles that brings the error below 0.1 on the needles, and the jump turns out to be very abrupt.
Student tasks
- Compare few particles with many steps against many particles with few steps.
- Find the minimum number of particles that beats the threshold in ten steps.
Room 19 · What the group knows
Communication is switched on: each particle is attracted both to its own best position and to the best of the whole swarm. Both extremes fail for opposite reasons and with the same final number, which forces students to look at the swarm and not just the error: with the social pull at zero these are independent searches, and with the cognitive pull at zero the swarm collapses prematurely.
Student tasks
- Set both extremes and observe the shape of the swarm in each case.
- Tell premature convergence from excess exploration by what is on screen.
Room 20 · Inertia
The third swarm coefficient, with a quirk that makes it didactically valuable: which way it should be turned depends on the landscape. Two maps side by side with the same value show that in the bowl the less inertia the better, while on the needles there is a clear optimum, with both failures visible: a swarm stuck below it and a swarm bouncing off the walls above it.
Student tasks
- Sweep the inertia while watching both landscapes at once.
- Deduce from the stability condition beyond which value the particles stop settling.
Room 21 · The swarm in many dimensions
The horizontal axis stops being time and becomes the dimension. With the same budget, three methods are compared in dimensions 2, 3, 5, 10 and 20: what matters is not who wins a column but the slope of each curve. A budget challenge in dimension 10 also reveals that using too many particles is as bad as using too few.
Student tasks
- Read the graph looking at the slope rather than at the winner of each column.
- Find the number of particles that solves the problem in dimension 10.
Room 22 · Choosing the best
The genetic block starts without crossover, isolating selection. The tournament of k introduces selection pressure, and the needles — where the global structure deceives — make the result very sharp: the minimum pressure that does anything is the best, because anything above it steers the population into the wrong hemisphere.
Student tasks
- Sweep the selection pressure and locate the optimal value.
- Explain what the method becomes when there is no selection at all.
Room 23 · Mixing two solutions
Uniform crossover and the building block hypothesis, with its limit measured. The same experiment on two landscapes: on the egg box, which is separable, crossover multiplies performance by three; in the curved valley, where the variables are coupled, it contributes absolutely nothing. The word epistasis is introduced and it is explained why the historical promise of crossover was not kept.
Student tasks
- Read the comparative table with and without crossover on both landscapes.
- Recognize, given a formula, whether crossover will help or not.
Room 24 · Mutating without losing the best
The two pieces that keep the genetic from breaking. Mutation is the only source of new material: without it the method only recombines what was already in the initial population. Elitism is shown graphically: without it, the curve of the best of the population stops being monotone and jumps upwards every time the leader is lost.
Student tasks
- Compare the curves of the best of the population with and without elitism.
- Tune mutation and elitism until the budget challenge on the needles is beaten.
Room 25 · Diversity
The standard deviation of the population, measured alongside the error. The lesson is in the order: diversity collapses first and the error curve flattens afterwards, never the other way round, and that lag turns diversity into a leading indicator useful for diagnosis without knowing where the optimum is.
Student tasks
- Watch both curves together on several landscapes and note which falls first.
- Diagnose which parameter to change from the diversity graph.
Room 26 · The rolling triangle
The Nelder-Mead simplex, deterministic and derivative-free, with its four moves animated step by step on the map. A worked example with whole numbers lets students compute the reflected point by hand. The spoiler tells that it is the most used derivative-free optimizer in the world and that it nevertheless has no convergence theorem in dimension greater than one.
Student tasks
- Watch the triangle roll step by step and recognize each of the four moves.
- Compute by hand the coordinates of a reflected point.
Room 27 · Using the slope
The question students have wanted to ask for twenty-six rooms, with its honest answer: the gradient estimated by differences costs d+1 evaluations per step, and even paying that price it needs 16 evaluations for a precision that costs the swarm 586 and that random search never reaches. A comparative table puts it in writing, and a slider shows both divergence at high rates and the zigzag of the valley.
Student tasks
- Read the table of evaluations needed per method.
- Deduce from the formula beyond which learning rate the method stops converging.
Room 28 · Where the exact methods crash
Four tests and four different causes: zero derivative on the staircase, derivative of pure noise in fog, local minima on the egg box and bad geometry in the valley. Local search stands beside it as a control. Here the existence of everything before is justified: heuristics do not exist because nobody knows how to differentiate, but because there are many problems where the derivative does not exist, cannot be estimated or leads nowhere.
Student tasks
- Run the four tests and compare the gradient with local search on each.
- Match each failure with its cause and tell a failure of the method from a failure of the landscape.
Room 29 · The tournament
Seven methods, five landscapes, the same budget and twenty-one seeds per cell. The bet comes before seeing the table, so that it is a real prediction. The result, honest and slightly uncomfortable, is that there is no fully green row and that the oldest deterministic method wins three of the five columns on the friendliest possible terrain.
Student tasks
- Predict the winner of a column before running the tournament.
- Read the table and identify who comes last on the easiest landscape.
Room 30 · Changing the playing field
The same tournament with two changes, one at a time: first with noise in the evaluations and then in dimension ten. The ranking flips in both cases, and with the three panels together five of the seven methods turn out to win some column somewhere. There is no winner: there is a map of the conditions under which each one wins.
Student tasks
- Run both tournaments and compare the three panels.
- Explain why population methods cope better with noise.
Room 31 · No free lunch
The landscape where there is nothing to learn: flat everywhere except in one hidden little box. The table is not a tie but something better: pure randomness finds it 98% of the time and the gradient never, because every sophisticated method shares the flaw of stopping looking broadly as soon as it thinks it has found something. From there the Wolpert and Macready theorem is stated, insisting on what it does NOT say.
Student tasks
- Run the search and compare the location rates of the seven methods.
- Tell the correct statement of the theorem from its exaggerated readings.
Room 32 · Choose the method
Final diagnostic room. Six real situations — a very expensive evaluation, a noisy function, two hundred variables, a convex function with no derivative, a combinatorial problem and a global minimum hidden far away — and in each one students must choose the method they would start with. Nothing new is learned: everything before is used. It closes with the complete toolbox and the bridge to the bio-inspired optimization lab.
Student tasks
- Choose the right method in each of the six situations.
- Justify the choices with what was seen in the previous blocks.
Rooms to project
The most striking ones to show and discuss in class.