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-8).
- 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 9).
- Why the number of variables sinks methods that sample blindly: the curse of dimensionality and its practical consequences, grid search included (rooms 10-11).
- Local search, its local optima, and the only two escapes: restarts (rooms 12-15) and accepting a move for the worse, which leads to simulated annealing with its Metropolis criterion and cooling schedule (rooms 16-19).
- Population methods: particle swarm with its cognitive and social pulls and its inertia (rooms 20-23), and the genetic algorithm with selection, crossover, mutation and elitism (rooms 24-26).
- The two deterministic methods: the Nelder-Mead simplex and gradient descent, and the four concrete ways in which the gradient crashes (rooms 27-29).
- 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 30-35).
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 mountain range
A tribe is looking for the lowest valley of a mountain range permanently covered in fog and can only send 7 expeditions: each click on the map clears the fog around a point and brings back its altitude. At the end the whole map is revealed: there were two valleys, and from the bottom of one the other cannot be seen. 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. The spoiler defines local minimum and global minimum.
Student tasks
- Look for the lowest valley with 7 expeditions, reading the altitudes and deciding where to go next.
- Recognize what information an optimization method actually has.
- Decide what can be concluded when, from the bottom of a valley, everything around goes up.
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 the spoiler explains that the error falls like N^(−2/d): doubling the darts halves the error in dimension 2.
Student tasks
- Throw with few and with many darts and describe how the error changes.
- With 200 darts, rank four terrains by the error they leave.
- Identify the virtue only this method has: it cannot get trapped in a local minimum.
Room 3 · The catalogue of terrains
The eight functions for the rest of the lab (the mountain range, the bowl, the curved valley, the egg box, the plateau, the staircase, the needles and the needle in the haystack), each with its textbook name (sphere, Rosenbrock, Rastrigin, Ackley, Schwefel…), its formula and the method it is designed to break. The map is drawn in dimension 2, but all of them are defined for any number of variables. A warning closes the room: in real problems f has no formula, and the needle in the haystack is there as a reminder.
Student tasks
- Identify the terrain whose minimum is a whole region rather than a point.
- Mark the terrains with many local minima.
- Recognize the terrain where there is no clue at all to follow.
Room 4 · 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, which reappears later in the lab.
Student tasks
- Judge a report that gives the error of a single run.
- Say what happens to the median error as the number of darts grows.
- Compute how many independent runs are needed for a given reliability.
Room 5 · 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.
- Decide what takes most of the time in a real problem whose function is not analytic.
Room 6 · 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 7 · 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. In the curved valley and in the bowl you can be far from the optimum with an almost perfect value, and on the staircase the minimum is not a point but a whole region.
Student tasks
- Decide which error matters in a concrete application.
- Find, by clicking on the map, in which functions a small error in value can go with a large error in position.
Room 8 · 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
- Mark which of the four curves really reach the minimum.
- Interpret a straight line on a logarithmic scale and a curve that stays flat for 500 evaluations.
- Compute how many evaluations a linearly convergent method needs for a given precision.
Room 9 · Explore or exploit
The hinge room of the lab. A single dial — the jump size σ — with both failures visible on the egg box: with a small σ the method never leaves the pit it fell into, and with a large one it never finishes refining. The typical error over 21 runs shows that neither extreme wins, and it is announced that every method to come is a different way of turning this same dial: temperature, inertia, selection pressure.
Student tasks
- Diagnose, from a flat curve, which way the dial must be turned.
- Sweep the slider and locate the σ with the lowest typical error on the egg box.
- Decide how exploring and exploiting should be shared out over a single run.
Room 10 · 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: N(d) = 10^d. The table reaches 10^10 in dimension 10, and a live experiment on the bowl (median of 11 runs) shows that random search goes from 25 evaluations in dimension 2 to about 825 in dimension 5 to get below an error of 0.05.
Student tasks
- Compute the expected darts needed to hit in dimension 6.
- Check in the experiment the order of magnitude of the evaluations in dimension 5.
Room 11 · Random or grid?
Grid search: k values per variable cost k^d evaluations, and a half-finished grid is of no use. Two drawings of 25 points compare it with random sampling: the 5 × 5 grid tries only 5 distinct values of each variable, while the 25 random points try 25. Moreover, random sampling can be stopped halfway and what has been done is still a sample of the whole terrain.
Student tasks
- Compute the cost of a full grid with 5 variables and 4 values each.
- Count how many distinct values of x₁ a 7 × 7 grid tries.
- Explain why random sampling is usually preferable to a grid with the same number of points.
Room 12 · 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, σ, and a budget challenge asks students to choose it so that the search gets below an error of 0.00002 on the bowl with only 200 evaluations, checked over 21 seeds so that a lucky hit does not count.
Student tasks
- Move σ and watch the trail of the search on the map.
- Beat the budget challenge by choosing a σ that works on at least half of the seeds.
- Explain why it is not good that, with a very small σ, almost every proposal improves.
Room 13 · The trap
The same method on the egg box, where only 1% of starts reach the global minimum. The map is coloured by basins of attraction, and the student clicks anywhere 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 see how many reach the global minimum.
- Say what has been proved when the search has gone 300 evaluations without improving.
- Compute how many starts are needed for a given success probability.
Room 14 · Starting over
The first escape: split the budget among several restarts. Sweeping the number of restarts (from 1 to 500), the typical error is bad at both ends, because every extra restart shortens all the others. The room 4 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 15 · The step that learns
Rechenberg’s one-fifth rule makes σ tune itself according to the acceptance rate. A graph shows σ 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 σ close in on itself.
Student tasks
- Give the target acceptance rate of the one-fifth rule.
- Compare fixed and adaptive σ on both landscapes.
- Diagnose why the mechanism fails precisely when it works well.
Room 16 · 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 17 · 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.
- Say what the formula does with a proposal that improves.
Room 18 · Cooling down
Before the formulas, annealing is watched moving: each step of the path is coloured by whether it moved somewhere better, accepted somewhere worse or rejected the proposal, with three bars for the budget spent, the probability of accepting a worse move and the worse moves accepted so far. Then T₀ and the cooling factor α appear, with the temperature over time above the convergence curve it produces, and three schedules to see what each one dies of: instant freeze, always hot and cold start. A budget challenge asks for a pair (T₀, α) that solves the needles on at least 4 of 5 seeds with 3000 evaluations.
Student tasks
- Count how many worse moves the “always hot” schedule accepts in a full run.
- Work out what is left of the initial temperature with α = 0.99 after 2000 steps.
- Beat the challenge by finding a pair (T₀, α) that works on most seeds.
Room 19 · Duel: annealing against local search
First the live duel: both methods start from the same point, with the same budget and the same jump, on each of the five landscapes. Then the table: 1500 evaluations, σ = 0.02 and 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
- Watch the five duels and mark the terrains where annealing wins.
- Explain why the more sophisticated method loses on the bowl.
- Decide what is most reasonable when facing a new problem about which nothing is known.
Room 20 · 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 with which the median of 21 runs gets below an error of 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.
- Explain what is wrong with a swarm of 100 particles that, with 1000 evaluations, only takes 9 steps.
Room 21 · What the group knows
Communication is switched on: each particle is attracted both to its own best position (the cognitive pull, c₁) and to the best of the whole swarm (the social pull, c₂). With 1500 evaluations, every change of a control launches a new search, and the scoreboard gives how many of 21 runs reach the global minimum as well as the median error, because on the needles the result is all or nothing. 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 c₁ = 0 on the needles and describe what happens to the swarm.
- Decide whether c₂ = 0 fails for the same reason as c₁ = 0.
- Find the ratio c₁/c₂ with which the swarm reaches the global minimum most often on the needles.
- Compare the bowl and the needles while raising the particles from 3 to 20.
Room 22 · 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
- Find the largest value of w with which the particles of the bowl all end at a single point.
- Deduce from the stability condition beyond which value the particles stop settling.
- Explain what it says about choosing parameters that w = 0 is the best option on the bowl.
Room 23 · The swarm in many dimensions
The horizontal axis stops being time and becomes the dimension. With the same budget of 3000 evaluations, three methods are compared on the egg box 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, with the swarm projected onto x₁ and x₂ and its convergence curve, also reveals that using too many particles is as bad as using too few.
Student tasks
- Read the graph looking at the slope: what happens to the darts from d = 2 to d = 10.
- Find the number of particles with which the median of 21 runs gets below 0.07 in dimension 10.
- Explain why 300 particles give a much worse result than 20 with 3000 evaluations.
Room 24 · Choosing the best
The genetic block starts without crossover, isolating selection: children are mutated copies of a parent chosen by a tournament of k, the selection pressure. There are two controls, the tournament and the population size, and two terrains; the budget of 1500 evaluations does not change, so a population twice as large lives half as many generations. On the needles, where the global structure deceives, the result is sharp: the control that gets the method out of the 0.14 error is the population, not the pressure, because selection cannot choose what no initial individual has brought (the room 4 formula).
Student tasks
- Sweep both controls on the needles and decide which one gets the method out of 0.14.
- Find a pair (k, population) whose median over 41 runs gets below 0.01 on the needles.
- Explain what the method becomes when there is no selection at all.
Room 25 · Mixing two solutions
Uniform crossover and the building block hypothesis, with its limit measured. With two controls, the crossover probability p and the pressure k, the same experiment on two landscapes: on the egg box, which is separable, crossover multiplies performance by almost three; in the curved valley, where the variables are coupled, it contributes nothing. The word epistasis is introduced and it is explained why the historical promise of crossover was not kept. A final note presents BLX-0.5 crossover, the most common one with continuous variables.
Student tasks
- With p = 1, sweep the pressure and see what the gain from crossover depends on.
- Recognize, given a formula, whether crossover will help or not.
- Count how many distinct children uniform crossover of two parents can produce in dimension 2.
Room 26 · Mutating without losing the best
The two pieces that keep the genetic algorithm 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 the number of elites (0 to 4) until the median over 21 runs gets below 10^(−6) on the needles with 2000 evaluations.
- Say what happens to the method if every coordinate of every child always mutates.
Room 27 · 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 computes the reflected point by hand. Four terrains show how far it gets: on the bowl it succeeds 21 times out of 21, in the curved valley 20 out of 21, on the egg box 5 out of 21 and on the needles never. 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 on the four terrains and recognize each move.
- Explain why reflection always replaces the worst vertex.
- Say what the method does when the reflected point is better than all three vertices.
- Identify the situation in which this method does worse than the others.
Room 28 · Using the slope
The obvious question — why not use the derivative? — with its honest answer: the gradient estimated by differences costs d+1 evaluations per step, and even paying that price it needs 16 evaluations to get below an error of 10^(−6) on the bowl, where the swarm needs 586 and random search does not manage it even with 20,000. A slider for the rate η on three terrains shows divergence at high rates on the bowl, the zigzag of the curved valley and, on the egg box, a flawless descent into the first pit.
Student tasks
- Read the table of evaluations needed per method.
- Deduce from the formula beyond which learning rate the method stops converging.
- Decide whether 16 against 586 means the swarm is a bad method.
- Explain why on the egg box the gradient settles at a high, stable error.
Room 29 · 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.
- Tell the test where the landscape, not the gradient, is to blame.
- Explain why fog affects the gradient far more than local search.
Room 30 · Every method, together
A review before the competition: the cards of the seven methods (name, parameters and pseudocode) and a test bench where terrain, method, dimension (2, 3, 5 or 10) and budget are chosen, the parameters are adjusted and one run or thirty are launched, with their median, best and worst result.
Student tasks
- Run the same method once and thirty times and say what the thirty add.
- Try the seven methods on the bowl, the plateau and the needles, and say which one stands out on each terrain.
Room 31 · The tournament
Seven methods, five landscapes, the same budget of 2000 evaluations 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. A note explains why annealing wins no column: its home is combinatorial problems, not these continuous landscapes.
Student tasks
- Predict which method wins on the needles before running the tournament.
- Read the table and identify who comes last on the bowl.
Room 32 · When you cannot trust what you measure
Measurement noise: every evaluation returns the value with an error inside, like a simulation with random seeds or a physical measurement. A landscape (five) and a dimension (2 or 10) are chosen, and a graph gives the error of the seven methods as the noise rises from 0% to 20%. On the bowl, Nelder-Mead goes from 4.6·10^(−87) without noise to 1.9·10^(−3) with 1%; with that 1% all methods fall into the same band, and from 5% upwards population methods pull ahead and win.
Student tasks
- Explain why a little noise sinks Nelder-Mead by so many orders of magnitude.
- Explain why a population copes with noise better than a single point.
- Point out what is missing from the reasoning of someone who picks a method for a new problem because of how it did on another.
Room 33 · 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.
- Identify the flaw the sophisticated methods share here.
- Tell the correct statement of the theorem from its exaggerated readings.
Room 34 · The mission
A practical exam before the final room: a function that is none of the catalogue and is not seen until the end, and 120 measurements spent in four rounds of 30. Before each round, method and parameters are chosen, and the best point found carries over to the next round. At the end the terrain is revealed (six irregular pits, a large one acting as a decoy), the result is compared with the median of 120 random darts, and the last configuration is rerun 21 times to separate judgement from luck.
Student tasks
- Spend the 120 measurements choosing method and parameters in each round.
- Explain why annealing with very short jumps and a high temperature is the worst possible configuration.
- Draw an honest conclusion from the histogram of one’s own configuration rerun 21 times.
Room 35 · 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.