Optimization Problem 5.9



Derive the precondition conjugate gradient by applying the standard conjugate gradient in the variables $\hat{x}$ and then transforming back to the original


1) let $\Phi (x) = \frac{1}{2}x^TAx - b^T x$

2) We want to apply some $C\hat{x}$ and see if we can transform it back to the original

$$\hat{\Phi} (\hat{x}) = \frac{1}{2}(C\hat{x})^TA(C\hat{x}) - b^T(C\hat{x})$$

$$\hat{\Phi} (\hat{x}) = \frac{1}{2}C\hat{x}^T A C\hat{x} - b^T C^{-1}\hat{x}$$

$$\hat{\Phi} (\hat{x}) = \frac{1}{2}\hat{x}^TC^{-1} A C^{-1}\hat{x} - (C^{-T} b)^T\hat{x}$$

3) subsitution $$\hat{A} = C^{-1} A C^{-1}$$ $$\hat{b} = C^{T} b$$

$$\hat{\Phi} (\hat{x}) = \frac{1}{2}\hat{x}^T\hat{A}\hat{x} - (\hat{b})^T\hat{x}$$

4) We can now show $\hat{\Phi}$ is in the same format as $\Phi$

In [ ]:
Share this Post