Introduction

Most optimization algorithms assume the function being minimized has a smooth gradient everywhere. But many functions that arise in practice — the ℓ1\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.

Try It

The demo below minimizes f(x)=∣x−1∣+0.5 ∣x+1∣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 ff at the current candidate, computes a subgradient, and adds a new supporting hyperplane (a cut) to the model.

<!-- Bundle methods demo: true function (blue), cutting-plane model (orange), proximal term (purple dashed) -->
<div class="info-bar">
  <span>Function: <b>f(x) = |x&minus;1| + 0.5|x+1|</b></span>
  <span>True minimum: x* = 1, f(x*) = 1</span>
</div>
<canvas id="canvas" width="480" height="260"></canvas>
<div class="status" id="status">Click ’Add cut’ to start the bundle algorithm.</div>
<div class="btns">
  <button id="btn-cut" type="button">Add cut</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="legend">
  <span class="leg-item"><span class="leg-swatch" style="background:#3b82f6"></span>True f(x)</span>
  <span class="leg-item"><span class="leg-swatch" style="background:#f97316"></span>Bundle model</span>
  <span class="leg-item"><span class="leg-swatch" style="background:#a855f7;opacity:0.6"></span>Proximal objective</span>
  <span class="leg-item"><span class="leg-swatch" style="background:#22c55e"></span>Next candidate</span>
</div>

/* Styles for the bundle methods demo */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Bundle method demo for f(x) = |x-1| + 0.5|x+1|
// True minimum: x* = 1, f(x*) = 1

// The nonsmooth convex objective with two kinks (at x=1 and x=-1)
function f(x) { return Math.abs(x - 1) + 0.5 * Math.abs(x + 1); }

// Return any subgradient of f at x (subdifferential is a set at the kink points)
function subgradient(x) {
  // At a kink we pick any value in the subdifferential; here the right-derivative convention
  const s1 = x >= 1 ? 1 : -1;
  const s2 = x >= -1 ? 0.5 : -0.5;
  return s1 + s2;
}

// Algorithm state
const PROX_WEIGHT = 0.5; // proximal weight (controls how far candidate steps from center)
const EPSILON = 0.05;    // convergence tolerance on the cutting-plane gap
let cuts = [];           // accumulated cuts: each is { y, fval, g }
let center = -2.5;       // current stability center — start well away from the optimum
let converged = false;

// Canvas coordinate helpers
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const X_MIN = -4, X_MAX = 3.5;
const Y_MIN = -0.5, Y_MAX = 6.5;

function toCanvasX(x) { return (x - X_MIN) / (X_MAX - X_MIN) * canvas.width; }
function toCanvasY(y) { return canvas.height - (y - Y_MIN) / (Y_MAX - Y_MIN) * canvas.height; }

// Cutting-plane model = max of all supporting hyperplanes (always a lower bound on f)
function modelAt(x) {
  if (cuts.length === 0) return -Infinity;
  return Math.max(...cuts.map(c => c.fval + c.g * (x - c.y)));
}

// Solve the proximal bundle subproblem by grid search (exact in 1-D)
function solveProxQP() {
  // minimize model(x) + (PROX/2)*(x-center)^2 over a fine grid
  const N = 1000;
  let best = center, bestVal = Infinity;
  for (let i = 0; i <= N; i++) {
    const x = X_MIN + (X_MAX - X_MIN) * i / N;
    const v = modelAt(x) + 0.5 * PROX_WEIGHT * (x - center) * (x - center);
    if (v < bestVal) { bestVal = v; best = x; }
  }
  return best;
}

function drawScene(candidate) {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Light grid lines for readability
  ctx.strokeStyle = '#e5e7eb'; ctx.lineWidth = 1;
  for (let gx = Math.ceil(X_MIN); gx <= X_MAX; gx++) {
    ctx.beginPath(); ctx.moveTo(toCanvasX(gx), 0); ctx.lineTo(toCanvasX(gx), canvas.height); ctx.stroke();
  }
  for (let gy = 0; gy <= Math.floor(Y_MAX); gy++) {
    ctx.beginPath(); ctx.moveTo(0, toCanvasY(gy)); ctx.lineTo(canvas.width, toCanvasY(gy)); ctx.stroke();
  }
  // Coordinate axes
  ctx.strokeStyle = '#9ca3af'; ctx.lineWidth = 1.5;
  ctx.beginPath(); ctx.moveTo(0, toCanvasY(0)); ctx.lineTo(canvas.width, toCanvasY(0)); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(toCanvasX(0), 0); ctx.lineTo(toCanvasX(0), canvas.height); ctx.stroke();

  // Purple dashed: proximal objective = model + proximity penalty centered at current center
  if (cuts.length > 0) {
    ctx.strokeStyle = 'rgba(168,85,247,0.5)'; ctx.lineWidth = 1.5;
    ctx.setLineDash([5, 4]);
    ctx.beginPath();
    let pStarted = false;
    for (let i = 0; i <= 400; i++) {
      const x = X_MIN + (X_MAX - X_MIN) * i / 400;
      const y = modelAt(x) + 0.5 * PROX_WEIGHT * (x - center) * (x - center);
      if (y > Y_MAX + 1) { pStarted = false; continue; }
      if (!pStarted) { ctx.moveTo(toCanvasX(x), toCanvasY(y)); pStarted = true; }
      else ctx.lineTo(toCanvasX(x), toCanvasY(y));
    }
    ctx.stroke(); ctx.setLineDash([]);
  }

  // Orange: cutting-plane model — piecewise-linear lower bound, rises toward f as cuts accumulate
  if (cuts.length > 0) {
    ctx.strokeStyle = '#f97316'; ctx.lineWidth = 2.2;
    ctx.beginPath();
    let mStarted = false;
    for (let i = 0; i <= 400; i++) {
      const x = X_MIN + (X_MAX - X_MIN) * i / 400;
      const y = modelAt(x);
      if (y > Y_MAX + 1 || y < Y_MIN - 1) { mStarted = false; continue; }
      if (!mStarted) { ctx.moveTo(toCanvasX(x), toCanvasY(y)); mStarted = true; }
      else ctx.lineTo(toCanvasX(x), toCanvasY(y));
    }
    ctx.stroke();
  }

  // Blue: true function f(x)
  ctx.strokeStyle = '#3b82f6'; ctx.lineWidth = 2.5;
  ctx.beginPath();
  for (let i = 0; i <= 400; i++) {
    const x = X_MIN + (X_MAX - X_MIN) * i / 400;
    const y = f(x);
    i === 0 ? ctx.moveTo(toCanvasX(x), toCanvasY(y)) : ctx.lineTo(toCanvasX(x), toCanvasY(y));
  }
  ctx.stroke();

  // Individual cut lines (faint orange) — each is a supporting hyperplane
  cuts.forEach(c => {
    ctx.strokeStyle = 'rgba(249,115,22,0.3)'; ctx.lineWidth = 1;
    ctx.beginPath();
    ctx.moveTo(toCanvasX(X_MIN), toCanvasY(c.fval + c.g * (X_MIN - c.y)));
    ctx.lineTo(toCanvasX(X_MAX), toCanvasY(c.fval + c.g * (X_MAX - c.y)));
    ctx.stroke();
  });

  // Dark blue dot: current stability center
  ctx.fillStyle = '#1d3557';
  ctx.beginPath(); ctx.arc(toCanvasX(center), toCanvasY(f(center)), 5, 0, 2 * Math.PI); ctx.fill();

  // Green dot: next candidate (argmin of proximal objective)
  if (candidate !== null) {
    ctx.fillStyle = '#22c55e';
    ctx.beginPath(); ctx.arc(toCanvasX(candidate), toCanvasY(f(candidate)), 5, 0, 2 * Math.PI); ctx.fill();
  }
}

function updateStatus(text, cls) {
  const el = document.getElementById('status');
  el.textContent = text; el.className = 'status ' + cls;
}

function addCut() {
  if (converged) return;

  // Determine next evaluation point, compute f and subgradient, add cut
  const y = cuts.length === 0 ? center : solveProxQP();
  const fval = f(y);
  const g = subgradient(y);

  // Cutting-plane gap at y, measured before adding the new cut
  // gap = f(y) - modelAt(y) computed BEFORE adding this cut
  // (model(y) including this cut would trivially equal f(y))
  const gapAtY = cuts.length > 0 ? fval - modelAt(y) : Infinity;

  cuts.push({ y, fval, g });

  // Serious step: advance center if the new point reduces f
  if (fval < f(center)) center = y;

  // Compute next candidate for display, then check convergence
  const nextCandidate = converged ? null : solveProxQP();
  drawScene(nextCandidate);

  if (cuts.length > 1 && gapAtY < EPSILON) {
    converged = true;
    document.getElementById('btn-cut').disabled = true;
    updateStatus(fmt('Converged in %length% cuts — gap < 0.05. Model has tightened around the minimum.', { length: cuts.length }), 'done');
  } else {
    const dispGap = gapAtY === Infinity ? '—' : gapAtY.toFixed(3);
    updateStatus(fmt('Cut %length% added. Gap = %dispGap%. Keep adding cuts.', { length: cuts.length, dispGap: dispGap }), 'running');
  }
}

function reset() {
  cuts = []; center = -2.5; converged = false;
  document.getElementById('btn-cut').disabled = false;
  drawScene(null);
  updateStatus('Click ’Add cut’ to start the bundle algorithm.', '');
}

document.getElementById('btn-cut').addEventListener('click', addCut);
document.getElementById('btn-reset').addEventListener('click', reset);
drawScene(null);
Result
Console

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.

The Real Complexity

Bundle methods have a crisp theoretical story:

  • The model. After collecting subgradients g1,…,gkg_1, \dots, g_k evaluated at points y1,…,yky_1, \dots, y_k, the cutting-plane model is f^(x)=max⁡i{f(yi)+gi⊤(x−yi)}\hat{f}(x) = \max_{i} \{ f(y_i) + g_i^\top (x - y_i) \}. It is always a valid lower bound: f^(x)≤f(x)\hat{f}(x) \le f(x) for all xx.

  • Stabilization. Adding a proximal term gives the bundle subproblem: minimize f^(x)+12t∥x−xˉ∥2\hat{f}(x) + \tfrac{1}{2t}\|x - \bar{x}\|^2 over xx, where xˉ\bar{x} is the current stability center and t>0t > 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 xk+1x_{k+1} achieves sufficient decrease in ff, 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/ε2)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 xk+1=xk−αkgkx_{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.

Where It Matters

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⊤x)\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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bundle-methods/Content licensed under CC BY-NC 4.0.