Opening Convex Optimization II: Branch-and-Bound Methods
Convex Optimization II: Branch-and-Bound Methods
- Length
- 1 h 19 min
- Level
- Graduate
- Recorded
- Stanford University2008
Chapter 1 of 11: Before the lecture
Splits rectangles on a binary tree, prunes them by bounds, then attacks a fifty-variable cardinality problem.
Branch-and-bound methods solve non-convex global optimization problems by partitioning the feasible set and computing exact lower and upper bounds. The lecture details the algorithm using unconstrained minimization over rectangles, tracking bounds on a binary tree and pruning subregions when bounds exceed known global limits. It then extends the framework to mixed Boolean-convex problems and cardinality minimization heuristics. Examples demonstrate the method on small and large random problems, comparing iteration counts against brute-force enumeration.
Branch-and-bound methods solve non-convex global optimization problems by partitioning the feasible set and computing exact lower and upper bounds. The lecture details the algorithm using unconstrained minimization over rectangles, tracking bounds on a binary tree and pruning subregions when bounds exceed known global limits. It then extends the framework to mixed Boolean-convex problems and cardinality minimization heuristics. Examples demonstrate the method on small and large random problems, comparing iteration counts against brute-force enumeration.
This lecture
Lecture 37 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. 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