local vs global optimum

Imagine hiking in fog and trying to reach the highest point by always stepping uphill. You may end up on a small hill, unable to go higher with any single step, while a far taller mountain sits across an unseen valley. The little hill is a local optimum — best among its immediate neighbours. The tall mountain is the global optimum — best everywhere. They are not always the same place.

A global optimum is the genuinely best solution over the whole search space — the lowest cost, the most jobs, the highest value, whatever the objective is. A local optimum is a solution that cannot be improved by small, local moves, even if a wholly different solution is better. Greedy algorithms make a sequence of locally best choices, so by construction they are chasing local optimality. The central theme of this whole field is exactly when local optimality forces global optimality: that happens precisely when the problem has the greedy-choice property and optimal substructure (or, more abstractly, a matroid). When it does, the local-best path provably reaches the global best; when it does not, greedy can strand you on a hill.

This distinction also explains why local-search and hill-climbing heuristics for hard problems give no optimality guarantee — they can halt at a local optimum far from the global one, which is why techniques like random restarts or simulated annealing exist to escape such traps. The honest takeaway: 'I cannot improve this with a small change' is a statement about local optimality only. Concluding it is globally optimal requires a real proof, not the comfort of being stuck.