Bundle Methods

Most optimization algorithms assume the function being minimized has a smooth gradient everywhere. But many functions that arise in practice — the $\ell_1$ norm, hinge loss in support-vector machines, or dual objectives in Lagrangian relaxation — have kinks: points where the gradient suddenly changes direction or does not even exist.

At a kink, the usual gradient tells you nothing useful about which way to step. A single subgradient points away from the minimum, and small steps in the subgradient direction oscillate without converging.

Bundle methods fix this by accumulating information across many steps. At each iteration the algorithm collects subgradients from past evaluation points into a bundle. It then builds a piecewise-linear (cutting-plane) model — a lower approximation of the function — and adds a proximal (quadratic stabilization) term to keep the next candidate point near a stable center. The result is a method that converges even when the landscape is as rough as a crumpled sheet of paper.

Bundle methods were developed independently by Claude Lemaréchal and Philip Wolfe in the late 1970s, and they remain among the most powerful algorithms for nonsmooth convex optimization.

The demo below minimizes $f(x) = |x - 1| + 0.5\,|x + 1|$ — a nonsmooth convex function with two kinks. The blue curve is the true function. Each time you click Add cut, the algorithm evaluates $f$ at the current candidate, computes a subgradient, and adds a new supporting hyperplane (a cut) to the model.

<!-- {{c_html_intro}} -->
<div class="info-bar">
  <span>{{label_function}}: <b>f(x) = |x&minus;1| + 0.5|x+1|</b></span>
  <span>{{label_min}}: x* = 1, f(x*) = 1</span>
</div>
<canvas id="canvas" width="480" height="260"></canvas>
<div class="status" id="status">{{msg_initial}}</div>
<div class="btns">
  <button id="btn-cut" type="button">{{btn_add_cut}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="legend">
  <span class="leg-item"><span class="leg-swatch" style="background:#3b82f6"></span>{{leg_true}}</span>
  <span class="leg-item"><span class="leg-swatch" style="background:#f97316"></span>{{leg_model}}</span>
  <span class="leg-item"><span class="leg-swatch" style="background:#a855f7;opacity:0.6"></span>{{leg_proximal}}</span>
  <span class="leg-item"><span class="leg-swatch" style="background:#22c55e"></span>{{leg_candidate}}</span>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; padding: 8px; }
.info-bar { font-size: .82rem; color: #555; margin-bottom: 6px; display: flex; gap: 12px; flex-wrap: wrap; }
canvas { display: block; border: 1px solid #dde3ea; border-radius: 8px; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: 8px 0 4px; min-height: 1.3em; }
.status.running { color: #1d4ed8; }
.status.done { color: #15803d; }
.btns { display: flex; gap: 8px; flex-wrap: wrap; margin-bottom: 8px; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.legend { display: flex; gap: 10px; flex-wrap: wrap; font-size: .78rem; color: #444; margin-top: 4px; }
.leg-item { display: flex; align-items: center; gap: 4px; }
.leg-swatch { display: inline-block; width: 14px; height: 4px; border-radius: 2px; }

// Code not found

Watch the orange piecewise-linear model (the maximum of all cuts so far) rise toward the true function from below. The proximal penalty (shown as the dashed parabola) keeps the next candidate near the current center, preventing wild oscillations. When the gap between the model's best value and the true function value is smaller than the tolerance $\varepsilon$, the algorithm declares convergence.

Bundle methods have a crisp theoretical story:

• The model. After collecting subgradients $g_1, \dots, g_k$ evaluated at points $y_1, \dots, y_k$, the cutting-plane model is $\hat{f}(x) = \max_{i} \{ f(y_i) + g_i^\top (x - y_i) \}$. It is always a valid lower bound: $\hat{f}(x) \le f(x)$ for all $x$.

• Stabilization. Adding a proximal term gives the bundle subproblem: minimize $\hat{f}(x) + \tfrac{1}{2t}\|x - \bar{x}\|^2$ over $x$, where $\bar{x}$ is the current stability center and $t > 0$ is the proximity weight. This is a quadratic program (QP) that can be solved exactly and cheaply.

• Serious vs. null steps. If the new candidate $x_{k+1}$ achieves sufficient decrease in $f$, the center moves (serious step). Otherwise only the bundle grows (null step). This ensures progress without demanding descent at every iteration.

• Convergence rate. For a convex Lipschitz function, bundle methods reach an $\varepsilon$-optimal solution in $O(1/\varepsilon^2)$ subgradient evaluations — the same as the subgradient method, but with far better practical behavior because the model aggregates curvature information.

• Comparison with pure subgradient. A raw subgradient step $x_{k+1} = x_k - \alpha_k g_k$ can oscillate violently near a kink. The bundle's proximal QP automatically selects a direction that balances the accumulated evidence from all past cuts against staying close to the best point found so far.

For nonsmooth convex problems, bundle methods are often the algorithm of choice in serious numerical software, such as the PBUNS and ConicBundle packages.

The moment an objective function develops a kink, bundle methods are ready:

• Lagrangian relaxation in combinatorial optimization: dualizing hard constraints turns an integer program into a nonsmooth dual function. Bundle methods maximize it to get strong lower bounds for branch-and-bound.
• Support-vector machines: the SVM hinge loss $\max(0,\, 1 - y\, w^\top x)$ is nonsmooth. Bundle methods handle large-scale SVM training without smoothing the loss.
• Unit commitment in power systems: scheduling generators over a day leads to a mixed-integer program whose Lagrangian dual is nonsmooth. Bundle methods provide tight bounds used by every major grid operator.
• Structural mechanics and topology optimization: compliance functions in finite-element models often involve eigenvalues, which are nonsmooth. Bundle methods find load-bearing designs that classical gradient methods miss.
• Robust optimization: minimax problems — minimize the worst-case loss over a set of scenarios — produce nonsmooth objectives by construction. Bundle methods turn this into a tractable computation.

Wherever a problem has a nonsmooth convex structure, bundle methods connect the power of cutting-plane geometry with the stability of proximal point algorithms — a combination that neither approach achieves alone. See also linear programming for the smooth convex cousin where simplex and interior-point dominate.

Smooth calculus fails at a kink. The subgradient method survives but oscillates. Bundle methods thread the needle: by accumulating all past subgradients into a cutting-plane model and stabilizing the search with a proximal penalty, they converge reliably even when the landscape is piecewise and rough.

The proximal bundle idea — that keeping a memory of past evidence and a tether to a stable center is better than following the local gradient alone — turns out to be a profound design principle. Variants of it underpin modern algorithms for training structured prediction models, solving dual problems in operations research, and managing uncertainty in robust planning.

So the next time a loss function has a sharp corner that defeats gradient descent, remember: the right answer is not to smooth it away, but to bundle the evidence and let the model tighten around the truth.