5,321
edits
Numerical Optimization: Difference between revisions
→Conjugate Gradient Methods
No edit summary |
|||
| Line 41: | Line 41: | ||
==Conjugate Gradient Methods== | ==Conjugate Gradient Methods== | ||
The goal is to solve <math>Ax=b</math> or equivalently <math>\min \phi(x)</math> where <math>\phi(x)=(1/2)x^T A x - b^Tx</math> | |||
===Definitions=== | |||
Vectors <math>\{p_i\}</math> are conjugate w.r.t SPD matrix <math>A</math> if <math>p_i^T A p_j = 0</math> for <math>i \neq j</math> | |||
;Notes | |||
* <math>\{p_i\}</math> are linearly independent | |||
===Algorithms=== | |||
Basic idea:<br> | |||
* Find a conjugate direction <math>p_k</math> | |||
* Take the step size <math>\alpha_k</math> which minimizes along <math>\phi(x)<\math> | |||
==Resources== | ==Resources== | ||
* [https://link.springer.com/book/10.1007%2F978-0-387-40065-5 Numerical Optimization by Nocedal and Wright (2006)] | * [https://link.springer.com/book/10.1007%2F978-0-387-40065-5 Numerical Optimization by Nocedal and Wright (2006)] | ||