Suppose a graph drawing has too many edge crossings. Moving vertices at random might improve it, but there are many possible positions to try. Gradient descent offers a directed search: represent a candidate solution by numerical coordinates, define a cost function for its quality, and repeatedly change the coordinates in a direction that lowers the cost. The choice of cost function is crucial; gradient descent is only the optimizer, not a complete solution to the drawing problem. section 16.0 section 16.4
At the current point, the gradient is a vector of partial derivatives—one for each coordinate—and points toward fastest local increase. A descent step moves against that vector: for each coordinate i, set new[i] = current[i] − α × derivative(cost, current, i). The learning rate α controls the step size. Each update uses the slope at the current point; it does not require a view of the entire cost surface. section 16.3.1 section 16.3.2
Listing 16.4 Method gradientDescent
function gradientDescent(f, P0, alpha, maxSteps) #1
for _ in {1..maxSteps} do #2
for i in {1.. |P0|} do #3
P[i] ← P0[i] – alpha * derivative(f, P0, i) #4
if P == P0 then #5
break
P0 ← P #6
return P0
The language-neutral pseudocode shows the coordinate updates, learning rate, iteration limit, and stopping check in one loop. section 16.3.2
Start from a candidate point, update every coordinate, and repeat until the point no longer changes at the chosen precision or a maximum number of steps is reached. A known differentiable formula lets you calculate derivatives directly; otherwise, nearby cost evaluations can approximate them numerically. A differentiable cost is needed near the points where gradients are computed. The method seeks a low-cost point, not necessarily the global minimum. section 16.3.2 section 16.3.3 section 16.6
Before running it, check the shape of the cost and the size of the steps:
- A large learning rate can skip a minimum, oscillate, or diverge; a small one may take too long. Decreasing the rate over time allows broader early moves and finer later ones. section 16.3.4
- Local minima can trap a run. Try different starting positions and compare their final costs when one run is not enough. section 16.5.2
- A step-shaped cost with broad flat regions gives little useful gradient information. For a discrete or nondifferentiable problem, consider simulated annealing instead. section 16.5 section 17.1.6
Fit a line to data
For linear regression, choose a line with parameters m and b. Define its loss from the squared differences between predicted and observed values, then take partial derivatives with respect to m and b—not the dataset points. Updating those two parameters reduces a bowl-shaped loss with a global minimum. section 16.4.1
Draw a graph
Minimizing the number of crossings directly is a poor fit because that cost is step-shaped. Instead, optimize a smoother cost for an aesthetically pleasing, force-directed drawing. Give each vertex random coordinates, repeatedly update its x and y coordinates from their partial derivatives, and optionally restart to retain the lowest-cost result. section 16.5 section 16.5.2
With d coordinates and at most T steps, the generic loop performs up to T × d derivative calculations and keeps coordinate vectors of size d; the work of each derivative depends on the cost function. Gradient descent is most attractive when that cost is differentiable and its shape makes a good minimum reachable. Otherwise, fast local progress may still end at a poor solution. section 16.3.2 section 16.3.3 section 17.1.6
