Kelley's Cutting-Plane Algorithm

Kelley's method minimizes a convex function by building a lower model from its supporting linear pieces and minimizing that model each round.

A piecewise-linear lower model

Kelley's algorithm, from 1960, is the archetypal cutting-plane method for minimizing a convex function f over a compact convex set. Because f is convex, its first-order (tangent) approximation at any point lies below the true function everywhere. Collect several such tangents and their pointwise maximum is a piecewise-linear function that underestimates f.

The iteration

At iteration k the model is m_k(x) = max over stored points i of ( f(x_i) + g_i^T (x - x_i) ), where g_i is a subgradient at x_i. Minimize this model over the feasible set (a linear program) to get x_{k+1}. Evaluate f and a subgradient there, add the new tangent to the model, and repeat. The model value gives a lower bound and f(x_{k+1}) gives an upper bound, so the gap between them certifies progress.

import numpy as np
from scipy.optimize import linprog

def kelley(f, grad, lb, ub, x0, iters=50):
    xs=[x0]; gs=[grad(x0)]; fs=[f(x0)]
    n=len(x0); x=x0
    for _ in range(iters):
        # minimize t s.t. t >= f_i + g_i^T (x - x_i) for all cuts
        A=[]; b=[]
        for xi,gi,fi in zip(xs,gs,fs):
            A.append(np.append(gi,-1)); b.append(gi@xi - fi)
        res=linprog(c=np.append(np.zeros(n),1), A_ub=np.array(A),
                    b_ub=np.array(b), bounds=[(lb,ub)]*n+[(None,None)])
        x=res.x[:n]; xs.append(x); gs.append(grad(x)); fs.append(f(x))
    return x

Behavior

Kelley's method converges for convex problems, and its lower model becomes exact in the limit. It reuses all past information, which can make it more sample-efficient than a subgradient method that forgets everything but the current point. Its notorious drawback is instability: early on the model is a poor approximation, so minimizers can swing to far corners of the feasible set, wasting evaluations.

The bundle fix

Bundle methods cure the instability by adding a proximal term (mu/2)||x - center||^2 to the model minimization, penalizing large jumps from a trusted center point that is advanced only when a real decrease is confirmed. This keeps the reliability of the cut model while damping its wild early behavior, and is the practical descendant of Kelley's original idea.