Numerical Optimization共轭梯度法

$n个p_i$n个pi​线性无关且共轭，表示为x的基

这样极小化括号的数，转化为n个一维的优化问题

共轭法

搜索步长$\alpha_k$αk​是通过极小化$\Phi(x_k+\alpha p_k)$Φ(xk​+αpk​)得到的

即对于凸的二次函数，共轭算法的步长是可能精确计算得到的

证明

举例

二维的问题，$\phi(x)$ϕ(x)的等高线是椭圆，由于A是对角阵，所以对称轴于行于坐标轴，且e1与e2对于A是共轭
；
当A，不再是对角矩阵时，e1与e2 不再是A的共轭方向
2步之内无法找到问题的解

因此，坐标方向法：当原始问题对应的矩阵A非对角时，我们可以对原问题作线性变化，使得新的newA 是对角的，然后可以使用共轭方向法在n 部内求得最优点。

一般性


第k步生成的残差rk和前面的搜索方向正交
如何生成共轭搜索方向，两种方法：特征向量，和Gram -Schmidt 正交化。对于第一种有对于实对称矩阵属于不同特征值的特征向量相互正交，因此可以推出来这些特征向量对于A 是共轭的

共轭梯度法

具体流程


对于$r_n$rn​和$r_0\dots r_{n-1}$r0​…rn−1​正交，则可以推出来n维空间中和n个线性无关向量都正交的话，这个向量一定是n向量，即$A_{x_n}=b$Axn​​=b是所求的解。
这些结论是依赖于初始点的选择的，即是在（p0=-ro）