Opening Convex Optimization II: Analytic Center Cutting-Plane and Ellipsoid Methods
Convex Optimization II: Analytic Center Cutting-Plane and Ellipsoid Methods
- Length
- 1 h 14 min
- Level
- Graduate
- Recorded
- Stanford University2008
Chapter 1 of 10: Before the lecture
Derives the ellipsoid update formula to minimize localization volume and traces its variable metric subgradient steps.
The ellipsoid method provides a polynomial-time algorithm for convex optimization. It localizes the optimal point within an ellipsoid and iteratively refines it using subgradients. The text derives the method's update formula for the minimum volume ellipsoid covering a half ellipsoid. It interprets the process as a variable metric subgradient method with space dilation. The basic ellipsoid algorithm is tested on a piecewise linear minimization problem, comparing its convergence behavior and complexity against the analytic center cutting-plane method. Finally, the limitations of practical stopping criteria versus theoretical convergence guarantees are discussed.
The ellipsoid method provides a polynomial-time algorithm for convex optimization. It localizes the optimal point within an ellipsoid and iteratively refines it using subgradients. The text derives the method's update formula for the minimum volume ellipsoid covering a half ellipsoid. It interprets the process as a variable metric subgradient method with space dilation. The basic ellipsoid algorithm is tested on a piecewise linear minimization problem, comparing its convergence behavior and complexity against the analytic center cutting-plane method. Finally, the limitations of practical stopping criteria versus theoretical convergence guarantees are discussed.
New York Times

This lecture
Lecture 26 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