Lecture: Recap: Branch And Bound Methods, Basic Idea, Unconstrained, Nonconvex Minimization
Tim Papandreou - Stanford
Description
Lecture Description
Announcements, Recap: Branch And Bound Methods, Basic Idea, Unconstrained, Nonconvex Minimization, Lower And Upper Bound Functions, Branch And Bound Algorithm, Comment: Picture Of Branch And Bound Algorithm In R^2, Comment: Binary Tree, Example, Pruning, Convergence Analysis, Bounding Condition Number, Small Volume Implies Small Size, Mixed Boolean-Convex Problem, Solution Methods, Lower Bound Via Convex Relaxation, Upper Bounds, Branching, New Bounds From Subproblems, Branch And Bound Algorithm (Mixed Boolean-Convex Problem), Minimum Cardinality Example, Bounding X, Relaxation Problem, Algorithm Progress, Global Lower And Upper Bounds, Portion Of Non-Pruned Sparsity Patterns, Number Of Active Leaves In Tree, Global Lower And Upper Bounds,
Course Description
Continuation of Convex Optimization I.
Topics include: Subgradient, cutting-plane, and ellipsoid methods. Decentralized convex optimization via primal and dual decomposition. Alternating projections. Exploiting problem structure in implementation. Convex relaxations of hard problems, and global optimization via branch & bound. Robust optimization. Selected applications in areas such as control, circuit design, signal processing, and communications.
from course: Convex Optimization II
Comments