关于Boyd共轭梯度笔记中Krylov序列函数值单调递减性质的疑问

Hey there! Let's break this down step by step to clear up your confusion. First, a critical premise for conjugate gradient methods: we assume matrix $A$ is symmetric positive definite—this is essential for the properties we’ll use here.

First: Fix the Expansion of $f(x_k + \alpha_k p_k)$ #

Your initial expansion has a mistake because $f(x)$ is a quadratic function, not a linear one, so $f(x + y) \neq f(x) + f(y) + 2x^T A y$. Let’s redo the expansion correctly:

Starting with the given definition:
$$f(x) := \tfrac{1}{2} x^T A x + b^T x$$

Expand $f(x_k + \alpha p_k)$ (we’ll drop the subscript on $\alpha$ temporarily for simplicity):
$$
\begin{align*}
f(x_k + \alpha p_k) &= \tfrac{1}{2}(x_k + \alpha p_k)^T A (x_k + \alpha p_k) + b^T(x_k + \alpha p_k) \
&= \tfrac{1}{2}x_k^T A x_k + \tfrac{1}{2}\alpha^2 p_k^T A p_k + \alpha x_k^T A p_k + b^T x_k + \alpha b^T p_k \
&= f(x_k) + \alpha\left(x_k^T A p_k + b^T p_k\right) + \tfrac{1}{2}\alpha^2 p_k^T A p_k
\end{align*}
$$

We can simplify the linear term using the gradient $\nabla f(x_k) = A x_k + b$ (let’s denote this gradient as $g_k$):
$$x_k^T A p_k + b^T p_k = p_k^T(A x_k + b) = p_k^T g_k$$

Now the expression becomes:
$$f(x_k + \alpha p_k) = f(x_k) + \alpha p_k^T g_k + \tfrac{1}{2}\alpha^2 p_k^T A p_k$$

Next: Use the Optimal Step Size $\alpha_k$ #

In conjugate gradient, $\alpha_k$ is the optimal step size—it’s chosen to minimize $f(x_k + \alpha p_k)$. To find this value, take the derivative of the function with respect to $\alpha$ and set it to zero:
$$
\frac{d}{d\alpha}f(x_k + \alpha p_k) = p_k^T g_k + \alpha p_k^T A p_k = 0
$$

Solving for $\alpha_k$ gives:
$$\alpha_k = -\frac{p_k^T g_k}{p_k^T A p_k}$$

Since $A$ is positive definite, $p_k^T A p_k > 0$ (as long as $p_k$ is a valid non-zero search direction, which it always is in conjugate gradient).

Finally: Prove $f(x_{k+1}) \leq f(x_k)$ #

Substitute $\alpha_k$ back into the expression for $f(x_{k+1}) - f(x_k)$:
$$
\begin{align*}
f(x_{k+1}) - f(x_k) &= \alpha_k p_k^T g_k + \tfrac{1}{2}\alpha_k^2 p_k^T A p_k \
&= \left(-\frac{p_k^T g_k}{p_k^T A p_k}\right)p_k^T g_k + \tfrac{1}{2}\left(\frac{(p_k^T g_k)^2}{(p_kT A p_k)^2}\right)p_kT A p_k \
&= -\frac{(p_k^T g_k)^2}{p_kT A p_k} + \frac{1}{2}\frac{(p_k^T g_k)^2}{p_kT A p_k} \
&= -\frac{1}{2}\frac{(p_k^T g_k)^2}{p_kT A p_k}
\end{align*}
$$

Now analyze the result:

• The numerator $(p_k^T g_k)^2$ is a square, so it’s non-negative.
• The denominator $p_k^T A p_k$ is positive (from $A$ being positive definite and $p_k \neq 0$).

This means the entire expression is non-positive:
$$f(x_{k+1}) - f(x_k) \leq 0 \implies f(x_{k+1}) \leq f(x_k)$$

That’s why the inequality holds! The key was fixing the expansion and leveraging the fact that $\alpha_k$ is explicitly chosen to minimize the function value at each step.

内容的提问来源于stack exchange，提问作者jjjjjj