共轭梯度下降及matlab简单实现

考虑问题：

$$min\ f(x) = \frac{1}{2}x^T A x + b^T x + c$$
具体求解的方法如下：
首先，任意给定一个初始点 $x^{(1)}$，计算出目标函数 $f(x)$在这个点的梯度，若 $||g_1||=0$，则停止计算，否则，令
$$d^{(1)}=-▽ｆ(x^{(1)})=-g_1$$
沿着 $d^{(1)}$的搜索，得到 $x^{(2)}$，计算 $x^{(2)}$处的梯度，若 $||g_2||=0$，则停止计算，否则利用若 $－g_2$和 $d^{(1)}$构造第二个搜索方向 $d^{(2)}$，再沿着 $d^{(2)}$搜索。
一般地，若已知 $x^{(k)}$和 $d^{(k)}$，则从 $x^{(k)}$出发，沿 $d^{(k)}$进行搜索，可得：
$$x^{(k+1)}=x^{(k)}+\lambda_k d^{(k)}$$
令：
$$\phi(\lambda)=f(x^{(k)}+\lambda d^{(k)})$$
求 $\phi(\lambda)$的极小值点：
$$\phi ^ {'}(\lambda) = ▽f(x^{(k+1)})^T d^{(k)}=0$$
带 $▽f(x^{(k+1)}) = Ax^{(k+1)}+b$得
$$(Ax^{(k+1)}+b)^T d^{(k)}=0$$
带 $x^{(k+1)}=x^{(k)}+\lambda_k d^{(k)}$，并展开得：
$$(g_k + \lambda_kAd^{(k)})^Td^{(k)}=0$$
求得：
$$\lambda_k=-\frac{g_k^T d^{(k)}}{d^{(k)T}Ad^{(k)}}$$
如果还没有满足终止条件：
$$d^{(k+1)} = -g_{k+1}+\beta_kd^{(k)}$$
左乘 $d^{(k)T}A$
$$d^{(k)T}Ad^{(k+1)} = -d^{(k)T}Ag_{k+1}+\beta_kd^{(k)T}Ad^{(k)}=0$$
得：
$$\beta_k=\frac{d^{(k)T}Ag_{k+1}}{d^{(k)T}Ad^{(k)}}$$

求 $min \ x_1^2+\frac{1}{2}x_2^2+\frac{1}{2}x_3^2$

A = [2 0 0; 0 1 0; 0 0 1];
x(:,1) = [1;1;1];
g(:,1)=A*x(:,1);
d(:,1) = [-1;-2;0];
n = 1;

lambda = [];
beta = [];

while norm(g(:,n)) > 0.01
    lambda(n) = -(g(:,n)'*d(:,n))/(d(:,n)'*A*d(:,n));
    x(:,n+1) = x(:,n)+lambda(n)*d(:,n);
    g(:,n+1) = A*x(:,n+1);
    beta(n) = (d(:,n)'*A*g(:,n+1))/(d(:,n)'*A*d(:,n));
    d(:,n+1) = -g(:,n+1)+beta(n)*d(:,n);
    n = n+1;
end