Opening Convex Optimization II: Stochastic Programming and Cutting-Plane Methods
Convex Optimization II: Stochastic Programming and Cutting-Plane Methods
- Length
- 1 h 16 min
- Level
- Graduate
- Recorded
- Stanford University2008
Chapter 1 of 10: Before the lecture
Builds stochastic subgradients from Monte Carlo samples, then bounds center of gravity cuts at .
Stochastic programming and localization methods extend optimization to problems with unknown parameters and form the basis of advanced cutting-plane algorithms. The lecture details how expectation objectives preserve convexity and introduces certainty-equivalent approximations alongside chance constraints. Stochastic subgradients provide noisy unbiased estimates from Monte Carlo samples, leading directly to adaptive methods like the sign algorithm. Localization methods generalize bisection to higher dimensions by maintaining a polyhedron of uncertainty and reducing it with cutting planes. The center of gravity algorithm guarantees a volume reduction of at most at each step, yielding a convergence bound proportional to the dimension.
Stochastic programming and localization methods extend optimization to problems with unknown parameters and form the basis of advanced cutting-plane algorithms. The lecture details how expectation objectives preserve convexity and introduces certainty-equivalent approximations alongside chance constraints. Stochastic subgradients provide noisy unbiased estimates from Monte Carlo samples, leading directly to adaptive methods like the sign algorithm. Localization methods generalize bisection to higher dimensions by maintaining a polyhedron of uncertainty and reducing it with cutting planes. The center of gravity algorithm guarantees a volume reduction of at most at each step, yielding a convergence bound proportional to the dimension.

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