Opening Convex Optimization II: Conjugate Gradient and Truncated Newton Methods
Convex Optimization II: Conjugate Gradient and Truncated Newton Methods
- Length
- 1 h 15 min
- Level
- Undergraduate
- Recorded
- Stanford University2008
Chapter 1 of 11: Before the lecture
Boyd runs conjugate gradient on a 100,000-node resistor network, then truncates it to approximate Newton steps.
The conjugate gradient method solves symmetric positive definite linear systems with only matrix-vector products, never forming or storing the matrix. Boyd continues the topic in Stanford's Convex Optimization II, diagonalizing the system to show how the eigenvalue spectrum governs convergence. A seven-dimensional example plots the polynomial built at each iteration, and a resistor network with one hundred thousand nodes tests sparse performance. Matrix-free multiplies, warm starts, and diagonal or approximate Cholesky preconditioners follow, with round-off setting limits on the theory. Truncated Newton methods then compute inexact Newton steps this way, and regularized logistic regression shows the speed gained by capping inner iterations.
The conjugate gradient method solves symmetric positive definite linear systems with only matrix-vector products, never forming or storing the matrix. Boyd continues the topic in Stanford's Convex Optimization II, diagonalizing the system to show how the eigenvalue spectrum governs convergence. A seven-dimensional example plots the polynomial built at each iteration, and a resistor network with one hundred thousand nodes tests sparse performance. Matrix-free multiplies, warm starts, and diagonal or approximate Cholesky preconditioners follow, with round-off setting limits on the theory. Truncated Newton methods then compute inexact Newton steps this way, and regularized logistic regression shows the speed gained by capping inner iterations.
Iterative Methods for Linear and Nonlinear Equations

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