A plateau is a region of a cost function where the value stays constant or changes too little for nearby moves to produce a useful improvement. Optimization algorithms can become stuck there because moving the current solution does not reveal a better position. section 16.2.2 section 16.2.3
Plateaus affect optimization in several practical ways:
- Make hill descent ineffective when nearby candidate solutions have the same cost. section 16.2.3
- Appear naturally in step functions, whose values change abruptly and remain flat between changes. section 16.2.3 section 17.1
- Complicate random optimization alongside local minima, often requiring more exploration or repeated runs. section 17.1
Graph embedding
When optimizing a graph drawing by minimizing edge intersections, moving a vertex may leave the intersection count unchanged. The resulting flat region is a plateau: probing nearby positions may produce no improvement, especially as the number of tunable parameters grows. section 16.2.3
Figure 16.12 How a generic randomized heuristic with local optimization works, explained using the marble analogy. Notice that we need to try to update x in both directions and check if we get an improvement.
Visualizes local optimization probing both directions around a solution, including cases where a step-shaped cost function leaves the search on a plateau. section 16.2.3
