Opening Convex Optimization II: Localization and Cutting-Plane Methods
Convex Optimization II: Localization and Cutting-Plane Methods
- Length
- 1 h 12 min
- Level
- Graduate
- Recorded
- Stanford University2008
Chapter 1 of 10: Before the lecture
Builds the analytic center cutting-plane method, from Newton centering to Hessian-based constraint pruning.
Localization methods generalize bisection to , querying a cutting-plane oracle to shrink a polyhedron known to contain the solution. Boyd, teaching Convex Optimization II at Stanford, starts with the center of gravity, which guarantees a 37 percent volume reduction but is intractable in high dimensions. Hit-and-run sampling, maximum volume ellipsoid and Chebyshev centers follow, along with multiple cuts, nonlinear cuts and Kelly's epigraph cutting-plane method. The analytic center cutting-plane method fills the second half, with centering by an infeasible start Newton method and residual norm backtracking. Hessian-based ellipsoids justify dropping redundant constraints, and the iterations yield dual feasible lower bounds with linear convergence, contrasted against subgradient methods.
Localization methods generalize bisection to , querying a cutting-plane oracle to shrink a polyhedron known to contain the solution. Boyd, teaching Convex Optimization II at Stanford, starts with the center of gravity, which guarantees a 37 percent volume reduction but is intractable in high dimensions. Hit-and-run sampling, maximum volume ellipsoid and Chebyshev centers follow, along with multiple cuts, nonlinear cuts and Kelly's epigraph cutting-plane method. The analytic center cutting-plane method fills the second half, with centering by an infeasible start Newton method and residual norm backtracking. Hessian-based ellipsoids justify dropping redundant constraints, and the iterations yield dual feasible lower bounds with linear convergence, contrasted against subgradient methods.

This lecture
Lecture 25 of 37 of Convex Optimization I.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in