文章目录

• • • 最速下降法
    • Newton法
    • 共轭梯度法

无约束最优化问题
minf(x)f:Rn−>R(1)求解(1)，就是找到Rn中的一点x∗，使得∀x∈Rn，均有f(x∗)≤f(x)，称x∗为(1)的全局极小点。minf(x) \qquad f:R^n->R \qquad (1) \\ \ \\求解(1)，就是找到R^n中的一点x^*，使得∀x∈R^n，\\ 均有f(x^*)≤f(x)，称x^*为(1)的全局极小点。 minf(x)f:Rn−>R(1) 求解(1)，就是找到Rn中的一点x∗，使得∀x∈Rn，均有f(x∗)≤f(x)，称x∗为(1)的全局极小点。

最速下降法

• 收敛性定理：设f连续可微，水平集L={x | f(x) ≤ f(x^ 1)}，则最速下降法或者在有限步迭代后终止，或者得到点列{x^k}，其任何聚点都是f的驻点。
• 在收敛定理的假设下，若f 为凸函数，则最速下降法或在
  有限迭代步后达到极小点，或得到点列 其任何聚点都是
  f 的极小点

最速下降法的两个特征

1. 相邻两次迭代的搜索方向互相正交 （锯齿现象）
2. 对二元正定二次函数，用最速下降法产生的点列：偶数点列均在一条直线上，奇数点列也均在一条直线上，且都过最优点

最速下降法的改进：

1. 选择不同初始点
2. 采用不精确的一维搜索：采用非精确一维搜索求步长,
   可使相邻两个迭代点处的梯度不正交，从而改变收敛性
3. 采用加速梯度法：由于最速下降法在极小值点附近成锯齿状，因此下降过程中搜索方向可取
   dk=xk−xk−2d^k = x^k-x^{k-2} dk=xk−xk−2
   下两步继续用最速下降法，即负梯度方向

Newton法

步骤3中的搜房方向，可通过求解下列方程组得到
▽2f(xk)dk+▽f(xk)=0▽^2f(x^k)d^k+▽f(x^k)=0 ▽2f(xk)dk+▽f(xk)=0

• 当 f 为正定二次函数时，用Newton法从任意初始点可一步
  迭代达到极小点。
• 二次收敛性：从任意初始点出发，经有限次迭代总可以达到正定二次函
  数的极小点，称这样的算法具有二次收敛性

Newton法的优点

1. 当初始点离极小点很近时，算法收敛速度快
2. 算法简单，不需要进行一维搜索
3. 对正定二次函数，迭代一次就可得到极小点

Newton法的缺点

1. 对多数问题算法不具有全局收敛性
2. 每次迭代都要计算Hesse矩阵，计算量大
3. 每次迭代都要计算(▽2f(xk))−1或求解方程组▽2f(xk)d+▽f(xk)=0每次迭代都要计算(▽^2f(x^k))^{-1} \\ 或求解方程组▽^2f(x^k)d+▽f(x^k)=0每次迭代都要计算(▽2f(xk))−1或求解方程组▽2f(xk)d+▽f(xk)=0

(▽2f(xk))−1可能不存在方程组是奇异的，病态的▽2f(xk)非正定，dk可能不是下降方向(▽^2f(x^k))^{-1}可能不存在 \\ 方程组是奇异的，病态的 \\ ▽^2f(x^k)非正定，d^k可能不是下降方向 (▽2f(xk))−1可能不存在方程组是奇异的，病态的▽2f(xk)非正定，dk可能不是下降方向

4. 收敛于鞍点或极大点的可能性并不小

Newton法的改进

针对缺点(1) 对多数算法不具有全局收敛性，和 (4) 收敛于鞍点或极大点的可能性并不小，步长不取固定值1，而是采用精确一维搜索找最佳步长λk,这就是阻尼牛顿法
minf(xk+λdk)minf(x^k+λd^k) minf(xk+λdk)

Newton法的近一步改进
针对缺点(2)每次计算Hesse矩阵

共轭梯度法

共轭方向的性质

共轭方向法步骤

FR共轭梯度法
ak=∣∣gk+1∣∣2∣∣gk∣∣2a_k=\frac{||g_{k+1}||^2}{||g_k||^2} ak​=∣∣gk​∣∣2∣∣gk+1​∣∣2​

FR共轭梯度法的计算步骤