Cutting-Plane Methods
Cutting-plane methods build an outer polyhedral approximation of a convex problem, adding one linear inequality at a time to trim the search region.
Outer approximation
A convex feasible region or objective can be represented as the intersection of infinitely many half-spaces. Cutting-plane methods work with only a finite subset at a time. They solve a relaxed problem over the current outer approximation, then use the solution to generate a new linear inequality (a cut) that removes the current point without removing any true optimum, and add it.
The separation oracle
The engine is a separation oracle: given a candidate point, it either certifies feasibility or returns a violated linear inequality separating the point from the feasible set. For a convex constraint g(x) <= 0, a supporting hyperplane at the candidate built from g and its subgradient is a valid cut. Each cut is a subgradient inequality, so cutting-plane methods and subgradient methods are two views of the same information.
The loop
The generic loop is: solve the current relaxation to get x_k; call the oracle; if x_k is feasible and optimal, stop; otherwise add the returned cut and repeat. Because each cut is linear, the relaxation stays a linear or quadratic program that standard solvers handle. The set of cuts monotonically tightens the approximation.
- Solve the relaxation over accumulated cuts
- Query the separation oracle at the solution
- Add the most violated cut and re-solve
- Terminate when no cut is violated within tolerance
Uses and pitfalls
Cutting-plane methods underlie structured-prediction training, stochastic-program decomposition (Benders), and mixed-integer solvers (Gomory and other cuts). Their strength is decomposing an enormous or implicitly defined problem into a growing sequence of tractable ones. The classic weakness is instability: pure cutting-plane iterates can jump wildly, so bundle methods add a proximal stabilizing term that keeps iterates near a trusted center, and are preferred for reliable convergence.