5,321
edits
Numerical Optimization: Difference between revisions
→Conjugate Gradient Methods
| Line 50: | Line 50: | ||
==Conjugate Gradient Methods== | ==Conjugate Gradient Methods== | ||
[https://www.cs.cmu.edu/~15859n/RelatedWork/painless-conjugate-gradient.pdf Painless Conjugate Gradient]<br> | [https://www.cs.cmu.edu/~15859n/RelatedWork/painless-conjugate-gradient.pdf Painless Conjugate Gradient]<br> | ||
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><br> | 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>.<br> | ||
The practical CG algorithm will converge in at most <math>n</math> steps. | The practical CG algorithm will converge in at most <math>n</math> steps. | ||
===Definitions=== | ===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> | 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 | ;Notes | ||
* <math>\{p_i\}</math> are linearly independent | * <math>\{p_i\}</math> are linearly independent | ||
| Line 63: | Line 62: | ||
* Take the step size <math>\alpha_k</math> which minimizes along <math>\phi(x)</math> | * Take the step size <math>\alpha_k</math> which minimizes along <math>\phi(x)</math> | ||
Practical CG method:<br> | Practical CG method:<br> | ||
{{ hidden | Code | | |||
Below is code for the practical CG method.<br> | |||
<pre> | <pre> | ||
x = x0; | |||
r = A*x - b; | |||
p = -r; | |||
k = 1; | |||
while(norm(r) > tole && k < size(x,2)) | |||
Ap = A*p; | |||
alpha = (r'*r)/(p'*Ap); | |||
x = x + alpha * p; | |||
rn = r + alpha * Ap; | |||
beta = (rn'*rn)/(r'*r); | |||
p = -rn + beta * p; | |||
r = rn; | |||
k = k+1; | |||
end | |||
</pre> | </pre> | ||
}} | |||
===Theorems=== | ===Theorems=== | ||