Opening Subgradient Methods for Constrained Problems
Subgradient Methods for Constrained Problems
- Length
- 1 h 19 min
- Level
- Graduate
- Recorded
- Stanford University2008
Chapter 1 of 11: Before the lecture
Boyd reads dual subgradient updates as price adjustments, then proves convergence under noisy subgradients.
Subgradient methods for constrained convex problems start from the projected subgradient method, which takes a subgradient step and projects back onto the feasible set. Boyd applies it to the dual, maximizing over nonnegative Lagrange multipliers, and interprets the update as prices adjusting to resource constraints. A quadratic minimized over the unit box works the dual method through, and alternating objective and feasibility steps handle general convex inequalities. For noisy unbiased subgradients, a proof with conditional expectations shows convergence under square-summable but not summable step sizes. A noisy piecewise-linear example and a discussion of posterior analysis close the session; duality, subgradient calculus and basic probability are assumed.
Subgradient methods for constrained convex problems start from the projected subgradient method, which takes a subgradient step and projects back onto the feasible set. Boyd applies it to the dual, maximizing over nonnegative Lagrange multipliers, and interprets the update as prices adjusting to resource constraints. A quadratic minimized over the unit box works the dual method through, and alternating objective and feasibility steps handle general convex inequalities. For noisy unbiased subgradients, a proof with conditional expectations shows convergence under square-summable but not summable step sizes. A noisy piecewise-linear example and a discussion of posterior analysis close the session; duality, subgradient calculus and basic probability are assumed.

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