Optimization

Gradient Descent

The workhorse of continuous optimization: step downhill along the negative gradient to minimize a differentiable objective.

The core idea

Gradient descent minimizes a differentiable function f(x) by repeatedly moving in the direction of steepest descent, which is the negative gradient. The update rule is x_{k+1} = x_k - a * grad f(x_k), where a > 0 is the step size or learning rate. The gradient points toward the direction of fastest increase, so its negation points toward fastest local decrease.

Why the negative gradient

A first-order Taylor expansion gives f(x + d) approx f(x) + grad f(x) dot d. To decrease f the fastest per unit length of d, choose d parallel to -grad f(x). This only guarantees local descent for a small enough step; too large a step can overshoot and increase f.

Convergence behavior

On a convex function with L-Lipschitz gradient, a constant step size a <= 1/L guarantees convergence to the global minimum. For strongly convex functions convergence is linear (geometric), with rate governed by the condition number kappa = L/m, the ratio of largest to smallest curvature. Ill-conditioned problems (large kappa) zig-zag across narrow valleys and converge slowly.

Step size selection

Fixed step: simple but requires knowing curvature to set safely.
Line search: choose a each iteration to sufficiently decrease f (see line search methods).
Diminishing step: a_k -> 0 with sum a_k = infinity, used in stochastic settings.

Limitations

Plain gradient descent uses only first-order information, so it is slow on ill-conditioned or highly curved landscapes and can stall near saddle points. It does not escape local minima on non-convex objectives. These weaknesses motivate momentum, adaptive step sizes, and second-order methods.

python

def gradient_descent(grad, x0, lr=0.1, iters=1000):
    x = x0
    for _ in range(iters):
        x = x - lr * grad(x)
    return x

Gradient descent underlies most of machine learning training and appears in engineering design loops, including the surrogate-model tuning used to explore fusion device parameter spaces.