Opening Convex Optimization II: Truncated Newton Method and L1-Norm Methods
Convex Optimization II: Truncated Newton Method and L1-Norm Methods
- Length
- 1 h 13 min
- Level
- Undergraduate
- Recorded
- Stanford University2008
Chapter 1 of 10: Before the lecture
Runs truncated Newton on million-variable rate control, then replaces cardinality with the norm.
Truncated Newton methods solve very large convex problems by computing search directions with preconditioned conjugate gradient rather than direct factorization. Boyd, teaching Stanford's Convex Optimization II, compares their run times with direct methods and shows how diagonal preconditioning and warm starts overcome jamming. A network rate control problem with millions of variables serves as the test case for large primal-dual interior-point systems. The second half turns to cardinality problems, which are generally NP-hard, and replaces cardinality with the norm as a convex heuristic. Examples include sparse design, regressor selection, signal reconstruction, outlier estimation, linear classifiers, portfolios, piecewise fitting, and polishing the resulting sparsity pattern.
Truncated Newton methods solve very large convex problems by computing search directions with preconditioned conjugate gradient rather than direct factorization. Boyd, teaching Stanford's Convex Optimization II, compares their run times with direct methods and shows how diagonal preconditioning and warm starts overcome jamming. A network rate control problem with millions of variables serves as the test case for large primal-dual interior-point systems. The second half turns to cardinality problems, which are generally NP-hard, and replaces cardinality with the norm as a convex heuristic. Examples include sparse design, regressor selection, signal reconstruction, outlier estimation, linear classifiers, portfolios, piecewise fitting, and polishing the resulting sparsity pattern.
BV book

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