共轭梯度法
最快下降法和牛顿法都有自己的局限性。本文介绍的共轭梯度法是介于最快下降法和牛顿法之间的无约束优化算法，具有超线性收敛速度，结构简单，编程方便。此外，最快的下降方法相似。共轭梯度法只使用目标函数及其梯度值，避免了二级导数的计算，从而减少了计算量和存储量。因此，它是一种更有效的算法来解决无约束优化的问题。
一、共轭方向发 共轭方向法的基本思想是求解 n n n当维正定二次目标函数非常小时，产生一组共轭方向作为搜索方向，在线搜索条件下算法的迭代 n n n步即能求得极小点。京故宫适当修正后共轭方向法可以推广到求解一般非二次目标函数情形。下面先介绍共轭方向的概念。 定义1：设 G G G是 n n n若阶对称正定矩阵 n n n维向量组 d 1 , d 2 , ? ? , d m ( m ≤ n ) 满 足 d_1,d_2,\cdots,d_m(m\le n)满足 d1,d2,?,dm(m≤n)满足
算法1：共轭方向法 0. 给定迭代精度 0 ≤ ϵ ≤ 1 0\le\epsilon\le 1 0≤ϵ≤1和初始点 x 0 x_0 x0。计算 g 0 = ∇ f ( x 0 ) g_0=\nabla f(x_0) g0=∇f(x0)。选取初始方向 d 0 d_0 d0使得 d 0 T g 0 < 0 d_0^Tg_0\lt 0 d0Tg0<0。令 k = 0 k=0 k=0.
- 若 ∣ ∣ g k ∣ ∣ ≤ ϵ ||g_k||\le\epsilon ∣∣gk∣∣≤ϵ，停算，输出 x ∗ ≈ x k x^*\approx x_k x∗≈xk.
- 利用线搜索方法确定步长 α k \alpha_k αk
- 令 x k + 1 = x k + α k d k x_{k+1}=x_k+\alpha_kd_k xk+1=xk+αkdk，并计算 g k + 1 = ∇ f ( x k + 1 ) g_{k+1}=\nabla f(x_{k+1}) gk+1=∇f(xk+1).
- 选取 d k + 1 d_{k+1} dk+1满足下降性和共轭性条件： d k + 1 T g k + 1 < 0 , d k + 1 T G d i = 0 , , i = 0 , 1 , ⋯ , k d_{k+1}^Tg_{k+1}\lt 0,d_{k+1}^TGd_i=0,\quad,i=0,1,\cdots,k dk+1Tgk+1<0,dk+1TGdi=0,,i=0,1,⋯,k.
- 令 k = k + 1 k=k+1 k=k+1，转步1
该算法的收敛性证明略过，如果感兴趣，可以去查找相应的数值优化专著。这里直接给出结论，在精确线搜索下，算法1求解正定二次目标函数极小化问题，之多在 n n n步内即可求得其唯一极小点。这种能在有限步内求得二次函数极小点的性质通常称为二次终止性。
二、共轭梯度法 共轭梯度法是在每一步迭代利用当前点处的最速下降方向来生成关于凸二次函数 f f f的海塞阵 G G G的共轭方向，并建立求 f f f在 R n \mathbb{R^n} Rn上的极小点的方法。这一方法最早是由Hesteness和Stiefel于1952年为求解正定线性方程组而提出来的，后经Fletcher等人研究并应用于无约束优化问题取得了丰富的成果，共轭梯度法也因此成为当前求解无约束优化问题的重要算法类。 设函数如（1）式所定义，则 f f f的梯度和海塞矩阵为 g ( x ) = ∇ f ( x ) = G x + b , G ( x ) = ∇ 2 f ( x ) = G (2) g(x)=\nabla f(x)=Gx+b,\quad G(x)=\nabla^2 f(x)=G\tag{2} g(x)=∇f(x)=Gx+b,G(x)=∇2f(x)=G(2) 下面我们讨论算法（1）中共轭方向的构造。我们取初始方向 d 0 d_0 d0为初始点 x 0 x_0 x0处的负梯度方向，即 d 0 = − ∇ f ( x 0 ) = − g 0 (3) d_0=-\nabla f(x_0)=-g_0 \tag{3} d0=−∇f(x0)=−g0(3) 从 x 0 x_0 x0出发沿 d 0 d_0 d0方向进行线搜索得到步长 α 0 \alpha_0 α0，令 x 1 = x 0 + α 0 d 0 x_1=x_0+\alpha_0d_0 x1=x0+α0d0 其中 α 0 \alpha_0 α0满足条件 ∇ f ( x 1 ) T d 0 = g 1 T d 0 (4) \nabla f(x_1)^Td_0=g_1^Td_0 \tag{4} ∇f(x1)Td0=g1Td0(4) 在 x 1 x_1 x1处，用 f f f在 x 1 x_1 x1的负梯度方向