凸优化系列二:确定步长一维搜索算法

项目github地址&＃xff1a;bitcarmanlee easy-algorithm-interview-and-practice
欢迎大家star&＃xff0c;留言&＃xff0c;一起学习进步

1.精确一维搜索与非精确一维搜索

在上一篇文章中&＃xff0c;我们提到第k次的迭代公式为:
xk&＃43;1&＃61;xk&＃43;αkdkx_{k&＃43;1} &＃61; x_k &＃43; \alpha_kd_kxk&＃43;1​&＃61;xk​&＃43;αk​dk​
其中&＃xff0c;αk\alpha_kαk​表示步长。接下来我们讨论一下怎么确定步长。
我们令
φ(αk)&＃61;f(xk&＃43;αkdk)\varphi(\alpha_k) &＃61; f(x_k &＃43; \alpha_k d_k)φ(αk​)&＃61;f(xk​&＃43;αk​dk​)
假设我们从点xkx_kxk​出发&＃xff0c;沿着方向dkd_kdk​进行搜索&＃xff0c;确定φ(αk)\varphi(\alpha_k)φ(αk​)值最小&＃xff0c;这个过程就叫一维搜索。注意我们在这个搜索过程中假设xkx_kxk​与dkd_kdk​都已经确定&＃xff0c;只有αk\alpha_kαk​未知。

如果能直接求出这个最优解αk\alpha_kαk​&＃xff0c;那么我们这个αk\alpha_kαk​就被称为最优步长&＃xff0c;这种方法被称为最优一维搜索&＃xff0c;或者说精确一维搜索。
但是实际情况往往是问题比较复杂&＃xff0c;数据维度也很高&＃xff0c;直接求精确的最优步长αk\alpha_kαk​可能比较困难&＃xff0c;这个时候往往会选择不精确一维搜索来进行代替。
不精确的一维搜索也可以成为近似一维搜索。通常的方法是选择合适的αk\alpha_kαk​&＃xff0c;使得目标函数有一定的下降量&＃xff0c;即f(xk&＃43;αkdk)f(xk​&＃43;αk​dk​)<f(xk​)。或者说&＃xff0c;只需要找到一个步长&＃xff0c;使得目标函数有一定的下降量就可以了。

2.精确一维搜索之试探法

精确一维搜索主要包括试探法(区间搜索法)与函数逼近法。
其中&＃xff0c;常用的试探法又包括进退法&＃xff0c;黄金分割法&＃xff0c;二分法等。

2.1进退法

算法的步骤如下:
1.确定搜索的起点与初始步长。
2.以起点开始以初始步长向前试探。如果函数值变大&＃xff0c;改变步长方向。
3.如果函数值下降&＃xff0c;维持原来的试探方向&＃xff0c;并将步长加倍。

算法的大致流程如下

2.2 黄金分割法

0.618法&＃xff0c;又叫黄金分割法&＃xff0c;是优选法的一种。它在试验时&＃xff0c;把试点安排在黄金分割点上来寻找最佳点。而生产生活中&＃xff0c;我们常常取其近似值0.618&＃xff0c;因此得名。0.618法是最常用的单因素单峰目标函数优选法之一。(参考文献1)
用0.618法寻找最佳点时&＃xff0c;虽然不能保证在有限次内准确找出最佳点&＃xff0c;但随着试验次数的增加&＃xff0c;最佳点被限定在越来越小的范围内&＃xff0c;即存优范围会越来越小。用存优范围与原始范围的比值来衡量一种试验方法的效率&＃xff0c;这个比值叫精度。用0.618法确定试点时&＃xff0c;每一次实验都把存优范围缩小为原来的0.618.因此&＃xff0c;n次试验后的精度为&＃xff1a;
δn&＃61;0.618n−1\delta_n &＃61; 0.618^{n-1}δn​&＃61;0.618n−1

具体的算法细节可以查阅更为详细的文献与参考资料。

2.3 二分法

具体原理与黄金分割类似。

3.精确一维搜索之函数逼近法

如果原函数具有比较好的解析性质&＃xff0c;那么可以使用函数逼近(插值)的方法。

3.1 牛顿法

牛顿法的思路就是利用某一点的函数值&＃xff0c;一阶导数值&＃xff0c;二阶导数值构造二次插值函数。牛顿法最大的优势就是收敛速度快&＃xff0c;具有局部二阶收敛的速度。

将$f(x)$在xkx_kxk​点处泰勒展开
f(x)&＃61;f(xk)&＃43;f′(xk)(x−xk)&＃43;f′′(xk)2!(x−xk)2&＃43;o(x−xk)2f(x) &＃61; f(x_k) &＃43; f&＃39;(x_k)(x-x_k) &＃43; \frac{f&＃39;&＃39;(x_k)}{2!}(x - x_k)^2 &＃43; o(x-x_k)^2f(x)&＃61;f(xk​)&＃43;f′(xk​)(x−xk​)&＃43;2!f′′(xk​)​(x−xk​)2&＃43;o(x−xk​)2

要求上面函数的极值&＃xff0c;由高等数学的知识&＃xff0c;易知f′(x)&＃61;0f&＃39;(x) &＃61; 0f′(x)&＃61;0&＃xff0c;那么有
f′(xk)&＃43;f′′(xk)(x−xk)&＃61;0f&＃39;(x_k) &＃43; f&＃39;&＃39;(x_k)(x - x_k) &＃61; 0f′(xk​)&＃43;f′′(xk​)(x−xk​)&＃61;0
求解可知
x&＃61;xk−f′(xk)f′′(xk)x &＃61; x_k - \frac{f&＃39;(x_k)}{f&＃39;&＃39;(x_k)}x&＃61;xk​−f′′(xk​)f′(xk​)​

对应到一维搜索中&＃xff0c;步长$\alpha$的迭代方式为:
αk&＃43;1&＃61;αk−f′(αk)f′′(αk)\alpha_{k&＃43;1} &＃61; \alpha_k - \frac{f&＃39;(\alpha_k)}{f&＃39;&＃39;(\alpha_k)}αk&＃43;1​&＃61;αk​−f′′(αk​)f′(αk​)​
每次更新该点&＃xff0c;然后迭代查找即可。

3.2 插值法

可以有相应的二次插值&＃xff0c;三次插值方法&＃xff0c;具体可以查看参考文献2关于插值方法的描述。

4.不精确搜索

由于实际问题的复杂性&＃xff0c;使用精确一维搜索往往要付出很高的代价&＃xff0c;还不一定能得到比较好的结果。后来慢慢发现&＃xff0c;只要遵循一定的规律&＃xff0c;算法就很可能达到收敛。

4.1 Armijo-Goldstein准则

Armijo-Goldstein准则的核心思想有两个:
1.目标函数值应该有足够的下降
2.一维搜索的步长$\alpha$不应该太小。

这两个思想的意图非常明显。由于最优化问题的目的就是寻找极小值&＃xff0c;因此&＃xff0c;让目标函数函数值“下降”是我们努力的方向&＃xff0c;所以1正是想要保证这一点。
同理&＃xff0c;2也类似&＃xff1a;如果一维搜索的步长$\alpha$太小了&＃xff0c;那么我们的搜索类似于在原地打转&＃xff0c;可能也是在浪费时间和精力。(参考文献3)

所以最后Armijo准则的表达式为两个式子:
f(xk&＃43;αkdk)≤f(xk)&＃43;αkρgkTdkf(x_k &＃43; \alpha_k d_k) \le f(x_k) &＃43; \alpha_k \rho g_k^Td_kf(xk​&＃43;αk​dk​)≤f(xk​)&＃43;αk​ρgkT​dk​
f(xk&＃43;αkdk)≥f(xk)&＃43;αk(1−ρ)gkTdkf(x_k &＃43; \alpha_k d_k) \ge f(x_k) &＃43; \alpha_k (1 - \rho) g_k^Td_kf(xk​&＃43;αk​dk​)≥f(xk​)&＃43;αk​(1−ρ)gkT​dk​
其中&＃xff0c;$0<\rho <1/2$

为什么上面两个式子就可以满足我们的要求&＃xff0c;可以阅读参考文献3&＃xff0c;或者查阅相关最优化理论的教材。

4.2 Wolfe-Powell准则

Armijo-Goldstein准则可能会把最优步长因子排除在可接受区间外&＃xff0c;因此Wolfe-Powell准则做了相关的改进。
Wolfe-Powell准则也是有两个表达式。第一个表达式与Armijo-Goldstein准则的第一个表达式相同&＃xff0c;而第二个表达式为:
∇f(xk&＃43;αkdk)Tdk≥σgkTdk,σ∈(ρ,1)\nabla f(x_k &＃43; \alpha_k d_k)^Td_k \ge \sigma g_k^T d_k, \quad \sigma \in (\rho, 1)∇f(xk​&＃43;αk​dk​)Tdk​≥σgkT​dk​,σ∈(ρ,1)

上面式子的几何解释为&＃xff1a;在可接受点处的切线斜率大于等于初始斜率的$\sigma$倍&＃xff01;

参考文献&＃xff1a;
1.https://zh.wikipedia.org/wiki/黄金分割法
2.https://blog.csdn.net/bitcarmanlee/article/details/86556744
3.https://www.codelast.com/原创用人话解释不精确线搜索中的armijo-goldstein准则及wo/