无约束非线性优化算法
无约束优化问题是优化一类重要的研究分支。本节开始我们将主要讲述求解无约束问题的几类经典算法。 本节知识点有最速下降法和牛顿法的算法构造及收敛性结果。 重点为最速下降法和牛顿法的方向向量的定义及牛顿法的步长恒为1.
由于迭代点远离最优解或海塞阵不正定时，牛顿法可能失效，因而需要改进方法或寻找其他新方法来解决无约束优化问题。本节将讲述阻尼牛顿法和共轭梯度法。 本节知识点有阻尼牛顿法的基本思想和算法构造、共轭梯度法的基本思想和实现。重点为共轭梯度法的方向构造及参数的计算。
迭代结构和线性搜索
一个非线性规划问题
\[\begin{aligned} \min \quad & f(\boldsymbol{x}) \\ \text{s.t.} \quad & \boldsymbol{x} \in F \end{aligned}\]其中 \(F \sube \mathbb{R}^n\)，无约束或约束问题。
用迭代算法，则
\[\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} + \alpha_k \boldsymbol{d}^{(k)}\]目标函数值要越来越小才行，即要保证 \(f(\boldsymbol{x}^{(k+1)}) \le f(\boldsymbol{x}^{(k)})\)。其中 \(\boldsymbol{d}^{(k)}\) 为搜索方向，这个方向函数要能变小。\(\alpha_k \in \mathbb{R}\) 作为步长。
迭代的关键就是方向和距离，即往哪里走的问题。
选 \(\alpha\) 的问题就是线性搜索问题，要求在于确定 \(\alpha_k\) 使得函数值变小。
精确线搜索，精确步长因子，黄金分割法、斐波那契法、割线法等。
不精确线搜索，只要使得每迭代一步都有充分下降。
最速下降法
设目标函数 \(f(\boldsymbol{x})\) 在 \(\boldsymbol{x}^{(k)}\) 附近连续可微
| 算法 | 最速下降 |
|---|---|
| 步骤1 | 给定初始点 \(\boldsymbol{x}^{(1)} \in \mathbb{R}^{n}\)，允许误差 \(\varepsilon > 0\) |
| 步骤2 | 计算搜索方向 \(\boldsymbol{d}^{(k)} = - \nabla f (\boldsymbol{x}^{(k)})\)，如果 \(\Vert \nabla f (\boldsymbol{x}^{(k)}) \Vert \le \varepsilon\) 则停止计算 |
| 步骤3 | 计算精确搜索步长 \(\alpha_k\) 使得 \(f(\boldsymbol{x}^{(k)} + \alpha_k \boldsymbol{d}^{(k)}) = \min_{\alpha \ge 0} f\boldsymbol{x}^{(k)} + \alpha \boldsymbol{d}^{(k)})\) |
| 步骤4 | 令 \(\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} + \alpha_k \boldsymbol{d}^{(k)}\) |
第三步里，论文中更常见的表达式
\[\alpha_k = \arg \min_{\alpha \ge 0} f(\boldsymbol{x}^{(k)} + \alpha \boldsymbol{d}^{(k)})\]精确线性搜索使得 \(\nabla f(\boldsymbol{x}^{(k+1)})^T \boldsymbol{d}^{(k)} = 0\) ，也就是说最速下降法前后两次迭代的搜索方向是正交的。所以在靠近极小点附近路径为锯齿形。
最速下降法的思路：沿着负梯度方向(步骤2)，走到下降最多的点(步骤3)，直到满足精度。
步骤3用到了实际上是个一元函数求极值问题，还是比较容易求解的。
牛顿法
基本思想是用目标函数 \(f(\boldsymbol{x})\) 在迭代点 \(\boldsymbol{x}^{(k)}\) 处的二阶泰勒展开作为逼近函数，用这个函数的极小点来逼近目标函数的极小点。
阻尼牛顿法
共轭梯度法
一般函数情况下的 Fletcher-Reeves 公式：
\[\beta = \frac{ \Vert \nabla f(\boldsymbol{x}^{(k+1)}) \Vert ^2 }{ \Vert \nabla f(\boldsymbol{x}^{(k)}) \Vert ^2 }\]FR 共轭梯度法
- 1.给定初始点 \(\boldsymbol{x}^{(1)} \in \mathbb{R}^{n}\)；允许误差 \(\varepsilon > 0\)；初始搜索方向 \(\boldsymbol{d}^{(1)} = -\nabla f (\boldsymbol{x}^{(1)})\)；停止条件 \(\Vert \nabla f (\boldsymbol{x}^{(k)}) \Vert \le \varepsilon\)
- 2.计算精确搜索步长 \(\alpha_k\) 使得 \(f(\boldsymbol{x}^{(k)} + \alpha_k \boldsymbol{d}^{(k)}) = \min_{\alpha \ge 0} f(\boldsymbol{x}^{(k)} + \alpha \boldsymbol{d}^{(k)})\)， \(\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} + \alpha_k \boldsymbol{d}^{(k)}\)
- 3.由 FR 公式算 \(\beta_k\)，新的搜索方向 \(\boldsymbol{d}^{(k+1)} = - \nabla f (\boldsymbol{x^{(k+1)}}) + \beta_k \boldsymbol{d}^{(k)}\)，2循环直到满足退出条件
与最速下降法相比，在找新的下降方向时，加了一项。
