单峰函数求极值 - 黄金分割法

黄金分割法,又称 0.618 法, 在数学上用于搜索一维单峰函数的极值的方法,和 二分法 类似, 是一种区间缩进的搜索方法。

数学上的黄金分割法

方便起见,我们只看下单峰函数,上单峰函数雷同。

假设 $f(x)$ 函数是区间 $[a, b]$ 上的一个下单峰函数,其极值的位置是 $t$ 。 就是说, $t$ 左边是单调递减的,右边是单调递增的

如果我们往区间上放置两个点 $a_1$ 和 $b_1$ ,对区间进行分割,这时候,只有两种情况:

  • 如果 $f(a_1) < f(b_1)$ ,则必然 $t$ 在区间 $[a, b_1]$ 内,就是下图中左边的情况。
  • 如果 $f(a_1) >= f(b_1)$ ,则必然 $t$ 在区间 $[a_1, b]$ 内,就是下图中右边的情况。
图1.1-分割后极值的两种情况

先只考虑上面所说的第一种情况,我们把左边的 $[a, b_1] $ 当做新的区间,代替原来的 $[a, b]$ ,也就是舍弃最右端的区间段; 同理对于上面所说的第二种情况,此时舍弃最左端的区间段。 然后继续比较、舍弃,如此反复进行,区间大小会不断变小,不断逼近 $t$ 。 如下图所示,绿色的线段表示不断缩小的区间:

图1.2-不断迭代,区间会不断缩小

直到误差达到理想水平,我们即可以获得单峰极值的近似值。

0.618 的由来

现在要问,区间的大小一次缩小多少比较合适呢?

黄金分割法的方法是,每次选择区间的 $0.618$ 处和它的对称点 $0.382$ 处作为一对分割点。

如下图 2.1 所示,左右分割点分别在 $0.382$ 比例处和 $0.618$ 比例处,且两个点关于中轴对称。

图2.1-两个黄金分割点

假设原始线段 $ab$ 的长度是 $L$ , 每次缩短的比例是小数 $r$ 。具体来说,我们希望的是:

  • 每次的两个分割点是对称的

    事先并不知道极值点在哪里,对于不对称的分割点,会出现一侧区间大,一侧区间小的情况,如果极值不断落入大的区间, 会恶化迭代的速度。

    在下面图 2.2 中的上图中,对称意味着: 线段 $aa_1$ 的长度和线段 $b_1b$ 一样,即 $(1-r)L$ 。

  • 分割点可以复用

    在下面的图 2.2 中,第一次的分割点 $a_1$ 复用 为第二次的分割点 $b_2$ 。

    最好上一次的分割点也可以用作下一次迭代的分割点,这样避免重复计算,每次只需要计算一个分割点的函数值。

    则下面的线段 $ab_2$ 和上面中的线段 $aa_1$ 一样长,即 $r^2L = (1-r)L$。

    解方程 $r^2 + r = 1$ 得 $r = \frac {\sqrt{5} \ -\ 1} {2}$ ,约等于 $0.618$ 。

图2.2 - 区间缩小比例的图示

复杂度分析

假设总共需要迭代 $k$ 次,区间才可以缩小到单位长度,假设总共的区间长度是 $n$ 个单位长度, 则有 $ n * (0.618) ^ k = 1$ 。假设 $c = 1 / 0.618$ ,则有 $ k = log_{c}{n}$ 。

根据 换底公式 可以知道:

\[log_{c} {n} = \frac {log_{2} {n}} {log_{2}{c}} = C * log_{2}{n}\]

也就是说时间复杂度是 $log{n}$ 。

计算机中的三分法求单峰

在计算机编程上,可以用同样的方式对单峰数组求极值。 不过,不像数学中 $0.618$ 是连续区间的分割点,离散的数组上,使用 三分法

下面仍然以下单峰数组为例,上单峰数组雷同。

下图是一个算法过程的示意图,其中红色框内的是每次缩减后的区间段,绿色的元素是分割点:

图3.1 - 三分法求单峰的示意图

此算法只对存在单峰的数组有效。

算法过程:

  • 步骤 1:初始化查找范围为整个数组,即低位 $low = 0$ ,高位 $high = n - 1$ ,$n$ 是数组的大小。
  • 步骤 2:选择分割点:

    • 计算整个范围的三分之一大小:$delta = (high - low) / 3$ 。
    • 左分割点是 $partition\text{_}left = low + delta$ 。
    • 右分割点与左分割点对称,是 $partition\text{_}left = high - delta$ 。
  • 步骤 3:按以下情况进行比较,然后回到步骤 2 继续迭代。

    • 如果左分割点的值严格小于右分割点的值,则舍弃右侧区间段,即 $high$ 缩小为 $partition\text{_}right - 1$ 。

      这里同样舍弃了 $partition\text{_}right$ 位置上的值,因为此数据肯定不是单峰。

    • 同理对于右分割点的值严格小于左分割点的情况, $ low = partition\text{_}left + 1$ 。

    • 如果两个分割点的值相等,则两个点都不是极值,两端都舍弃。

  • 步骤 4:直到 $low < high$ 不再满足,即 $low$ 和 $high$ 相等,终止迭代,此时已收敛到一个元素上,即峰值的位置。

复杂度分析

和黄金分割法一样,要把查找范围收缩到 $1$,迭代次数 $k$ 满足 $n * (1/3) ^ k = 1$ , 则时间复杂度为 $O(log_{3} {n})$ ,由 换底公式 可换算到 $O(log_{2} {n})$ 。

非递归实现的空间复杂度是 $O(1)$ 。

C 语言实现

C 语言的三分法查找数组内的单峰
// 给出大小为 n 的数组 a 的单峰的下标位置。
int TernarySearchPeak(int a[], int n) {
    int low = 0;
    int high = n - 1;
    int delta = 0;

    int partition_left = 0;
    int partition_right = 0;

    while (low < high) {
        delta = (high - low) / 3;
        partition_left = low + delta;
        partition_right = high - delta;

        if (a[partition_left] < a[partition_right]) {
            high = partition_right - 1;
        } else if (a[partition_left] > a[partition_right]) {
            low = partition_left + 1;
        } else {
            low = partition_left + 1;
            high = partition_right - 1;
        }
    }

    return low;
}

(完)

* * *
评论 首页 订阅 打印 ↑顶部