|
|
1 零阶信息，一阶信息和高阶信息
我们考虑如下的一个优化问题：
\underset{x\in D}{\min\text{ }}f\left( x \right) \quad (1.1) \\D=\left\{ x\in R|0\le x\le 1 \right\} \quad (1.2) \\
要想优化目标函数 f(x) 就必须从 f(x) 中获得一些信息，我们根据所利用的信息不同将优化算法分为三大类：
- 零阶优化算法：直接用 f(x) 的信息做优化。常见于智能算法，进化算法，比如粒子群算法，遗传算法等。
- 一阶优化算法：用一阶导数的信息 \nabla f\left( x \right) 和 零阶信息 f(x) 的信息一起做优化。例如我们下一节笔记中的最速下降法。
- 高阶优化算法：用零阶信息，一阶信息和高阶导数的信息来做优化。例如我们下下节笔记将会降到的牛顿法。
2 零阶算法求解一维优化问题
我们假设只采用零阶信息来寻找优化问题 (1.1-1.2) 的最优解。实际上零阶算法往往是我们能想到的一种最直接的求解方法。 由于优化问题 (1.1-1.2) 的可行域就是一维的[0,1]闭区间，采用零阶信息来寻找最优解一种最直接的想法就是在区间[0,1]之间直接均匀地选如下 M+1 个点计算出目标函数的值，然后从这 M+1个点中选出目标函数最小的那个作为最优解输出。
我们以f(x) = 6(x-0.3)^2+1 为例子来直观地演示一下上面所描述的过程，如下图所示：
https://www.zhihu.com/video/1542477185704628224
我们将以上流程总结成一个算法，算法名称为均匀网格法，算法具体流程如下所示：
Step 1: 在可行域[0,1]之间均匀选出 M+1个点，如下所示：
X=\left\{ x^{\left( i \right)}=\frac{i}{M},\forall i=0,1,2,...,M \right\} \\
Step 2: 计算出X中相对应的 M+1 个目标函数值：
F= \left\{ f\left( 0 \right) ,f\left( \frac{1}{M} \right) ,f\left( \frac{2}{M} \right) ,...,f\left( 1 \right) \right\} \\
带入到我们这个问题中实际上就是计算出如下 M+1 个目标函数值：
Step 3: 输出 F 集合中目标函数的最小值记作 \hat{x}，并且输出 \hat{x} 作为算法输出的最优值。
均匀网格法的算法流程是一个很自然地寻找最优解的一个想法。我们将真正的最小值记做 x^{*}。到这里我们就会产生一个疑问均匀网格法求得的最优目标函数值 f(\hat{x}) 到底离真正的最优目标函数值 f(x^{*}) 差距有多大呢？接下来我们就围绕这个问题展开论证。
3 均匀网格算法求解一维优化问题的复杂度
在展开论证之前，我们需要对目标函数f(x)的光滑型做一个假设。
我们假设目标函数 f(x) 是 李普希兹连续的。那么对于任取的 x,y\in D，有如下表达式成立：
\left| f\left( x \right) -f\left( y \right) \right|\le L\lVert x-y \rVert \\
其中L被称为李普希兹常数。
我们不难发现，在 X 中必然存在一个元素使得如下表达式成立，不妨记这个元素的索引为j
\left| x^{\left( j \right)}-x^* \right| \le \frac{1}{2M} \\
进一步从李普希兹条件可得：
f\left( x^{\left( j \right)} \right) -f\left( x^* \right) \le L\left| x^{\left( j \right)}-x^* \right|\le \frac{L}{2M} \\
由于 f\left( \hat{x} \right) 是 X 集合里边最小的值，结合上式有：
f\left( \hat{x} \right) -f\left( x^* \right) \le f\left( x^{\left( j \right)} \right) -f\left( x^* \right) \le \frac{L}{2M} \\
观察上式右端项，我们会发现 M 越大的则 通过上述算法得到的最优化 f(\hat{x}) 与 真正最优解 f(x^*) 就越接近。若要保证 f(\hat{x}) - f(x^*) < \epsilon，只需令
M=\frac{L}{2\epsilon} \\
由于 M 是整数，我们可以将上式改写为：
M=\lfloor \frac{L}{2\epsilon} \rfloor +1, \quad (3.1) \\
4 零阶算法求解多维优化问题的缺陷
在上一节中我们针对的是一维的优化问题采用均匀网格法来求解，需要计算 M=\lfloor \frac{L}{2\epsilon} \rfloor +1 次目标函数才能得到 \epsilon 近似的最优解。那么接下来我们就讨论如下二维优化问题：
\underset{x\in D}{\min\text{ }}f\left( x \right) \quad (4.1) \\D=\left\{ x\in R^2|0\le x_i\le 1,\ i=1,2 \right\} \quad \left( 4.2 \right) \\
如下图所示是采用均匀网格法来求解二维的优化问题的情况
https://www.zhihu.com/video/1542477338273181696
显然从图中不难看出，想要得到和之前一维问题一样的\epsilon 近似的最优解我们计算目标函数的点数需要平方的量级，即 M 需满足如下表达式：
M=\left( \lfloor \frac{L}{2\epsilon} \rfloor +1 \right) ^2 \quad (4.3) \\
至此我们会发现一个很残酷的事实就是，随着优化问题维数的增加，均匀网格法需要计算目标函数的次数会大大增加。实际上对于一般的 N 维优化问题，我们有
M=\left( \lfloor \frac{L}{2\epsilon} \rfloor +1 \right) ^N \quad (4.4) \\
这一结论的严谨证明过程可以见参考文献【1】（page11-13），其证明思路和我们上一节中证明一维优化问题的过程完全一样。
那么接下来我们带入一组具体数值大致估算一下这个 M 到底有多大？不妨令
L=1,\epsilon =0.01,N=10 \\
将上述数值带入式(4.4)中可得： M=\left( \lfloor \frac{1}{0.02} \rfloor +1 \right) ^{100}=5.71502\times 10^{170} 秒
假设我们拥有一台超级计算机1秒钟可以计算目标函数 10^9次，那么要完成上述任务也需要 \left( \lfloor \frac{1}{0.02} \rfloor +1 \right) ^{100}=5.71502\times 10^{162} 秒 约等于1.87\times 10^{155}年。由此可见即使是面对问题规模还不算大的情况下，采用零阶方法的均匀网格法的计算量也是相当惊人的。
从这里我们可以得到一个初步的结论：
- 零阶方法在面对 1维优化问题的时候效率还可以，但是一旦优化问题维数稍微大一点的时候其计算量可能会非常非常巨大。
- 零阶方法是一种最直接最简便的方法，它不要求目标函数可微可导等苛刻条件(相对于我们后边要介绍的一阶方法和高阶方法来说的)，即使在上面的证明过程中我们也仅仅是假设了李普希兹连续。
零阶优化方法作为一种最直接最直观的方法是最容易被人想到的一种算法，但是正是因为零阶优化方法有以上缺陷，所以在求解高维数优化问题的时候我们必然要引入一阶优化方法乃至于高阶优化方法。当然零阶优化方法也并非一无是处，在后边求解梯度法步长的时候，经常会用到零阶优化方法，主要是因为那个优化问题是一个一维的优化问题。
参考文献：
【1】Nesterov Y. Lectures on convex optimization[M]. Berlin: Springer International Publishing, 2018.
【2】Wright S, Nocedal J. Numerical optimization[J]. Springer Science, 1999, 35(67-68): 7.
【3】高立，数值最优化[M]. 北京大学出版社，2014. |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有账号？立即注册
×
|
窥视卡
雷达卡
发表于 2022-8-18 16:55
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡