I am studying Numerical Optimisation and now it comes to Conjugate Gradient Methods
Intuitively, I can accept
"Solving $Ax=b$ is equivalent to solving $min_x~\phi(x)=\frac{1}{2}x^\top Ax-b^\top x$"
How to formally show that these two are equivalent?
Thank you very much
Presumably, it is assumed in this context that $A$ is symmetric and positive definite.
Let $x_*$ denote a solution to $Ax = b$. Note that $$ \begin{align} x^TAx &= (x - x_* + x_*)^TA(x - x_* + x_*) \\ &= (x-x_*)^TA(x-x_*) + x^TAx_* + x_*^TAx + x_*^TAx_* \\ &= (x-x_*)^TA(x-x_*) + 2x_*^TAx + x_*^TAx_* \\ &= (x-x_*)^TA(x-x_*) + 2(Ax_*)^Tx + x_*Ax_* \\ &= (x-x_*)^TA(x-x_*) + 2b^Tx + x_*Ax_*. \end{align} $$ It follows that $$ \begin{align} \phi(x) &= \frac 12 (x-x_*)^TA(x-x_*) + b^Tx + \frac 12 x_*Ax_* - b^Tx \\ & = \frac 12 (x - x_*)^TA(x - x_*) + \frac 12 x_*Ax_*. \end{align} $$ Note that $x_*Ax_*$ is constant. Because $A$ is positive semidefinite, we can therefore see from the above that $\phi(x)$ is minimized when $(x-x_*)^TA(x - x_*)$ attains its minimal value of $0$, and this minimum occurs when $x = x_*$.
In other words, $x_*$ (the solution to $Ax = b$) is the value at which the minimum is attained.