Suppose you are moving vertices to draw a graph with fewer crossing edges. Each arrangement has a cost, and a nearby move might improve it. But reaching an arrangement that no nearby move improves does not prove you have found the best drawing overall. section 16.2.1
A locally optimal solution has a cost no greater than sufficiently nearby solutions; a global optimum has the lowest cost across the whole problem space. A local minimum can be a region rather than a single point. What counts as “nearby” depends on the moves allowed by the optimization algorithm. section 16.2.1 section 16.2.3
The one-dimensional cost curve makes the distinction visible: a dip can be lower than its surroundings without being the lowest dip on the curve. section 16.2.1
The shape of the cost function determines how easily a search gets stuck. On a smooth, bowl-shaped surface, downhill movement leads toward one minimum. A step function may instead have flat plateaus and multiple local minima: small moves can show no improvement even when a better solution exists elsewhere. Counting edge crossings creates this kind of difficult cost function for graph drawing. section 16.2.2 section 16.6
When a search stalls, choose a strategy that matches the cost landscape:
- Use local search to test nearby changes and keep an improvement. For a graph drawing, move a vertex in different directions and recount intersections; this cannot by itself escape every local minimum. section 16.2.3
- Restart from different random initial positions, run downhill again, and compare the resulting costs. This is useful when a practical cost function still has several local minima. section 16.5.1
- Allow some long-range transitions in simulated annealing. Restricting every move to the immediate neighborhood can remove its ability to escape local minima; unrestricted random sampling, however, may require many attempts to find a downhill move. section 17.1.4
Initial positions matter in k-means
K-means starts with random centroids, repeatedly assigns points to their closest centroid, and recenters each cluster. A poor initialization can slow convergence or produce a poor result when iterations are capped. Run it several times with different initial centroids, then compare the clusterings rather than trusting one run. section 12.2
Locally optimal is therefore a useful stopping condition, not a guarantee of global quality. The trade-off is search effort: nearby moves concentrate work around the current solution, while restarts or far-reaching moves explore alternatives. This matters especially as graph-drawing search grows to two position parameters per vertex. section 17.1.4 section 16.2.3
