Addendum: Hit-And-Run CG Algorithm

Lecture Description

Addendum: Hit-And-Run CG Algorithm, Maximum Volume Ellipsoid Method, Chebyshev Center Method, Analytic Center Cutting-Plane Method, Extensions (Of Cutting-Plane Methods), Dropping Constraints, Epigraph Cutting-Plane Method, PWL Lower Bound On Convex Function, Lower Bound, Analytic Center Cutting-Plane Method, ACCPM Algorithm, Constructing Cutting-Planes, Computing The Analytic Center, Infeasible Start Newton Method Algorithm, Properties (Of Infeasible Start Newton Method Algorithm), Pruning Constraints, PWL Lower Bound On Convex Function, Lower Bound In ACCPM, Stopping Criterion, Example: Piecewise Linear Minimization

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.

Related Resources

Transcript   |  Analytic Center Cutting-plane Method

Course Index

1. Basic Rules for Subgradient Calculus
2. Recap: Subgradients
3. Convergence Proof, Stopping Criterion
4. Project Subgradient For Dual Problem
5. Stochastic Programming
6. Addendum: Hit-And-Run CG Algorithm
7. Example: Piecewise Linear Minimization
8. Recap: Ellipsoid Method
9. Comments: Latex Typesetting Style
10. Decomposition Applications
11. Sequential Convex Programming
12. Recap: 'Difference Of Convex' Programming
13. Recap: Conjugate Gradient Method
14. Methods (Truncated Newton Method)
15. Recap: Example: Minimum Cardinality Problem
16. Model Predictive Control
17. Stochastic Model Predictive Control
18. Recap: Branch And Bound Methods, Basic Idea, Unconstrained, Nonconvex Minimization