数值优化之无约束优化

数值优化之无约束优化

注：之前开组会的时候制作的，分享一手

1.无约束最优化方法的基本结构

- 问题描述

- 符号说明

- 最优性条件

• 一阶必要条件：
  

• 二阶必要条件：

• 二阶充分条件:

• 关于二阶充分条件的例子：

- 图形、等高线

所谓的等高线，就是函数在其上恒取常数值的曲线，即$f(x)=c$。$c$取不同的值，在$O{x}_1{x}_2$平面上可以得到一族曲线。

- 方法的基本结构

总结：基本要素主要有两个：其一是下降的方向；其二就是步长（各种算法的区别主要在于这两个基本要素的不同）

- 终止准则

- 收敛性与收敛速度

收敛速度图示

一般认为介于二次和线性收敛之间就可以接受

- 搜索步长

所谓的精确线搜索，指在迭代点$x_k$,当迭代方向$d_k$已知时，使$f(x)$沿$d_k$关于步长$\alpha$取极小值，即

非精确线搜索：

• Armijo准则：
  

求解过程如下：给一初值$\alpha$,一直二分直到满足Armijo准则

while f(x_k+alpha*d_k)>f(x_k)+rou*g_k'*d_k*akpha
    alpha = alpha/2

• Wolfe准则
  
  

• 强Wolfe准则
  

2.无约束优化方法

2.1 最速下降法

根据$f(x_k+\alpha d)$在$x_k$点的$Taylor$展式

最速下降法的算法步骤: 下降方向为负梯度方向，搜索方法为精确线搜索

2.2 基本Newton方法

2.2.1 Newton方程

牛顿方程图示：

2.2.2 基本Newton方法迭代步骤

下降方向为$d_k=-G_k^{-1}{g}_k$ ,步长为$1$

2.2.3 基本Newton方法优缺点

优点：

• 方法以二阶收敛速度收敛

缺点：

• $G_k$会出现不正定或奇异的情形，当$G_k$为负定时，满足牛顿方程的$d_k$实际上是上升方向，并非是下降方向
• 每一步迭代都需要计算$Hesse$矩阵，即计算$n(n+1)/2$个二阶偏导数
• 每步迭代需要求解一个线性方程组，计算量为$O(n^3)$

2.3 混合方法

• $G_k$奇异，下降方向使用负梯度方向$-g_k$替代（步3）
• $g_k$与$d_k$几乎正交时，下降方向使用负梯度方向$-g_k$替代（步5）
• 在$G_k$ 负定，但$G_k^{-1}$存在时，取$d_k=G_k^{-1}{g}_k$(步4)

2.4 拟牛顿方法

2.4.1 拟牛顿条件

假定当前迭代点是$x_{k+1}$,若我们用已经得到的$x_k,x_{k+1}$及其一阶导数信息$g_k$和$g_{k+1}$,构造一个正定矩阵$B_{k+1}$作为hesse矩阵$G_{k+1}$的近似，使其满足牛顿方程。
$$B_{k+1}d=-g_{k+1}$$
然而这样做依旧需要求一个线性方程组，进一步的改进为用相同的信息构造一个$H_k$作为$G_{k+1}^{-1}$的近似，这样的下降方向即为:
$$d_k=-H_{k+1}{g}_{k+1}$$
在$x_{k+1}$处做泰勒展开：

2.4.2 拟牛顿方法迭代步骤

2.4.3 常见的拟牛顿方法

• DFP

• BFGS

• Broyden族公式

• BFGS方法和DFP方法的性质

  • 定理3.9 ：设$H_k$对称正定，且$s_k^T{y}_k>0$，则由DFP方法或者BFGS方法构造出$H_{k+1}$,且$H_{k+1}$对称正定

  • 定理3.10： 对于使用精确线搜索或者非精确线搜索（强Wolfe/Wolfe准则）的DFP方法或者BFGS方法，有
    $$s_k^T{y}_k>0$$

  • 总结 ：强Wolfe—>Wolfe准则—>$s_k^T{y}_k>0$—>$H_{k+1}$正定—>搜索方向是下降方向

2.4.4 拟牛顿方法的优点

• 只需要$f(x)$的一阶信息
• 方法具有较快的收敛速度

2.5 共轭梯度法

共轭梯度法是一种迭代算法，不需要存储完整的 Hessian 矩阵，特别适用于处理大型线性方程组和二次型优化问题。

共轭梯度方法的迭代方向为：
$$d_k=-g_k+{\beta }_{k-1}{d}_{k-1}$$
其中${\beta }_{k-1}$有多种构造方法，例如共轭下降（Conjugate Descent,CD）公式
$${\beta }_{k-1}=\frac{g_k^T{g}_k}{d_{k-1}^T{g}_{k-1}}$$
注：当使用强Wolfe线搜索准则并且$\rho <1$时，共轭梯度下降方法得到的方向为下降方向