|
|
终于来到最后一部分了，这一章节重点介绍求解之前我们建立的优化问题的相关算法。感觉凌青老师对这一部分的介绍比较快，而且不是特别系统。所以我参考了陈宝林老师的《最优化理论与算法》。
无约束优化算法
1. 一维搜索算法 （线搜索）
实际上在计算机程序当中求解（数值分析）时，我们都是采用迭代的形式进行。所以在这里，我们主要关心两个点：1）迭代的方向；2）迭代的步长。迭代式可以用下式表达:
x^{k+1}=x^{k}+\alpha^{k} d^k,
其中\alpha^{k}代表步长，是一个标量；d^{k}代表方向，维度与x^{k}一致。在迭代的时候，方向一般是比较好确定的（负梯度方向）。因为假如说这是一个凸问题，那么只要找到一个梯度下降的方向就可以了。而步长的确定，为了保证我能够收敛到最优解附近，那么我的步长应该尽可能小一些:
\alpha^{k} = \mathop{argmin}\limits_{\alpha \geq 0} f_0(x^{k}+\alpha^{k}d^k)
1.1 黄金分割法
无约束问题，适用于单峰函数。基本想法是这样的：通过取试探点计算使包含极小点的区间不断缩小，当区间缩小到一定程度的时候，区间上各点的值都接近极小值。因此区间内任一点都可以用来当作极小值的近似。具体推导参看《最优化理论与算法》P257。
计算步骤如下：
- 假定原来的区间范围为[a_1,b_1]，则试探点\mu_1=a_1+0.382(b_1-a_1), \lambda_1=a_1+0.618(b_1-a_1)。
- 比较两个试探点值f(\mu_1)和f(\lambda_1)
- 如果f(\mu_1)大，则更新区间范围为[a_2,b_2] = [\mu_1,b_1]
- 反之，则新的区间为[a_2,b_2] = [a_1,\lambda_1]
- 直到区间长度达到精度要求
实际问题中，目标函数在定义域内不一定是单峰的，所以首先要确定单峰区间。然后再利用该公式计算。
1.2 Fibonacci方法
该方法与黄金分割法类似，只不过区间长度缩短比率不再是常数，而是Fibonacci数列。
Fibonacci数列的定义：
- F_0=F_1=1
- F_{k+1}=F_{k} + F_{k-1}(k=1,2,3,...)
则计算试探点的公式为：
- \mu_1 = a_k + \frac{F_{n-k-1}}{F_{n-k+1}}(b_k-a_k)
- \lambda_1 = a_k + \frac{F_{n-k}}{F_{n-k+1}}(b_k-a_k), k=1,2,3,...,n-1
其中，n是计算次数，需要提前确定。
但是， 在实际计算中，黄金分割法不用提前设定计算次数，应用更广。
1.3 进退法
上面的方法都需要一个包含极小点的区间，在不满足这个要求时，可以使用进退法。思想为：从一点出发，按照一定步长计算，试图找到函数值呈现“高-低-高”的三点，如果这个方向不成功，就换一个方向。确定了高低高的区间后，即可确定包含极小点的区间。
实际应用时，注意选择步长h_0。太短，则收敛慢，太长可能错过了单峰区间。
1.4 函数逼近法
利用另一个函数\phi(x)在极小值点附近逼近目标函数f(x)，这样就可以用函数\phi(x)的极小值逼近目标函数极小值。可以利用二阶泰勒展开式、二次三项式（抛物线）、三次插值函数、连分式函数等进行逼近。
2. 利用导数的最优化方法（无约束优化）
无约束优化问题的求解可以分为两类，一类是利用目标函数导数的方法，另一类是不必计算导数的直接方法。一般来说，无约束问题的求解通过一系列一维搜索来实现，因此如何选择搜索方向是这类问题的核心，也衍生出不同的方法。
2.1 最速下降法 （一阶方法）
负梯度方向为最速下降的方向\bold{d}= - \frac{\nabla f(x)}{\|\nabla f(x)\|}。步长\lambda可通过一维搜索方法进行确定。算法步骤如下
- 给定初始点x^{0}和误差\epsilon。令k=1
- 计算搜索方向\bold{d}^{k} = -\nabla f(x^{k})
- 若\| \bold{d}^{k} \| \leq \epsilon,停止计算，反之利用下式求\lambda^{k}：
f(x^{k}+\lambda_{k}\bold{d}^{k}) = \mathop{\min}\limits_{\lambda \geq 0}f(x^{k} + \lambda \bold{d}^{k})
- 更新x^{k+1} = x^{k} + \lambda_{k}\bold{d}^{k}, k+=1
收敛速度：线性收敛。线性收敛比跟目标函数海森阵的特征值有关。
存在的问题：锯齿现象（因为相邻两个搜索方向是正交的），从全局看最速下降法并不是收敛最快的，适合在前期跌点或者间插步骤。
2.2 牛顿法 （二阶方法）
将目标函数f(x)进行泰勒展开，并取二阶近似，得到函数\phi(x)=f(x^{k})+\nabla f(x^{k})^{\mathrm{T}} + \frac{1}{2}(x-x^{k})^{\mathrm{T}}\nabla^2f(x^{k})(x-x^{k})。对近似函数求极值点，即\nabla \phi(x)=0。得到迭代式：
x^{k+1}=x^{k}-\nabla^{2}f(x^{k})^{-1}\nabla f(x^{k})
通过目标函数的梯度和海森阵的逆进行迭代求解。对于二次函数，牛顿法收敛速度快。但是，当初始点远离极小点时，可能不收敛，原因是牛顿方向\bold{d}=-\nabla^{2}f(x^{k})^{-1}\nabla f(x^{k})不一定是下降方向，函数值可能上升（因为前面没有步长，结果就是可能步子迈大了）。
一些牛顿法的改进方向：
- 可以对牛顿法进行改进，在牛顿方向前乘上步长（一维搜索得到）。每次搜索的时候，都是去求一个最小值对应的\lambda，因此可以函数值不会上升。收敛性得到了改进。【阻尼牛顿法】
- 当海森阵是非正定时，阻尼牛顿法可能不会产生新的点（即步长是0）。解决方法是构造一个新的矩阵G_{k}代替原来的海森阵。具体构造方式为海森阵加上\epsilon_{k}\bold{I}，\bold{I}是单位阵。为什么会想到如此的方法？因为很明显，按照这样的定义方法，新矩阵G_{k}的特征值是原来海森阵的特征值加上\epsilon_{k}，只要这个\epsilon_{k}取得足够大，就一定可以保证新矩阵是正定的，就避免了以前出现的问题。
2.3 共轭梯度法
共轭梯度法基本思想是将共轭性与最速下降法进行结合，利用已知点的梯度构造一组共轭方向，并沿这个方向进行搜索，找到目标函数极小点。
共轭方向给定如下定义：A是n \times m的对称正定矩阵，若\mathcal{R}^{n}中的两个方向d^{(1)}和d^{(2)}，满足下式：
d^{(1)T}Ad^{(2)} = 0
则称这两个方向关于矩阵A共轭。
算法步骤
- 给定一个初始解x_1，计算出目标函数f(x)在该点的梯度g_1，若\| g_1 \| = 0，则停止计算；反之，令d_1=-g_1=-\nabla f(x_1)。这里的d_1代表搜索方向。
- 然后计算迭代步长\lambda_1，满足\min f(x_1+\lambda d_1)。实际上就是找函数\phi(\lambda)=f(x_1+\lambda d_1)的极小点。即：\nabla f(x_1+\lambda d_1)^{T}d_1=0。
- 找到\lambda_1之后，计算得到第二个点x_2。
- 现在需要构造第二个搜索方向d_2，计算公式为：是利用如下公式：d_2=-g_2+\beta_1d_1。其中，\beta_1=\frac{d_1^TAg_2}{d_1^TAd_1}。A是目标函数的海森阵。
- 计算步长\lambda_2，求得第三个点x_3。
- 依次类推迭代计算，直到算出的某个点的梯度=0。
迭代式如下：\lambda_k=-\frac{g_k^Td_k}{d_k^TAd_k}（目标函数为二次），如果为一般的目标函数，则需要利用一维搜索的方法确定。d_{k+1}=-g_{k+1}+\beta_kd_k，\beta_k=\frac{d_k^TAg_{k+1}}{d_k^TAd_k}。
为什么想到要如此构造呢？因为有一个重要的推论：g_{k+1}^{T}d_j=0, \forall j\leq k
这个推论是在证明共轭梯度法为什么能够找到最优解的过程中得到的。这个推论点明了搜索方向和梯度的关系，然后利用施密特正交化公式，去构造的迭代式。
共轭梯度法适合大规模求解问题。
2.4 拟牛顿法
解决海森矩阵难以计算或求逆困难的问题。在牛顿法中，迭代式为：x^{k+1}=x^{k}-\nabla^{2}f(x^{k})^{-1}\nabla f(x^{k})。人们想到采用另一个矩阵来近似这个海森矩阵的逆。根据近似方法的不同，又有如下的方法：
- 秩1校正
- DFP算法（在秩1矫正法基础上，修改了\Delta H的计算方法）
- BFGS方法
拟牛顿法具有超线性收敛，计算速度快，缺点是不适于存储量较大的计算（大型问题）。
本文使用 Zhihu On VSCode 创作并发布
|
|
窥视卡
雷达卡
发表于 2023-1-12 14:58
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡