🔢 mathematics

In ratio section method and algorithms for minimizing unimodal functions

本文提出了一种新的比例分割法用于最小化单峰函数，该方法通过高效识别单调函数和平底函数，显著减少了所需的函数评估次数，其性能优于经典二分法、黄金分割法以及改进的布伦特算法。

原作者： Vladimir Kodnyanko

发布于 2026-04-30

📖 1 分钟阅读🧠 深度阅读

原作者： Vladimir Kodnyanko

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一片广阔而雾气弥漫的山谷中找到最低点。你无法一眼看清整个地貌；你只能站在一个点上，环顾四周，然后迈出一步。你的目标是用尽可能少的步数找到山谷底部（即最小值）。这正是数学家们在尝试“最小化”一个函数时所做的事情。

本文介绍了一种更快迈出这些步数的新方法。以下是作者思想的分解，使用简单的类比说明：

问题：旧有的搜索方式

长期以来，数学家们一直使用两种主要策略来寻找那个山谷底部：

二分法（“对半切割”法）：想象你有一根代表山谷的长绳。你将其精确地从中间切断，检查高度，然后扔掉较高的一半。你重复这一过程，每次都把剩余的绳子对半切断。这种方法可靠，但略显缓慢且僵化。
黄金分割搜索法（“黄金比例”法）：这是第一种方法的更高级版本。你不是将绳子精确地从中间切断，而是在一个特殊的“黄金”位置（大约 61.8% 处）切断。这通常比对半切割更快，但它仍然遵循严格、预设的模式。

新想法：“比例分割”法

作者弗拉基米尔·科德尼亚科（Vladimir Kodnyanko）提出了一种新的切绳方式。他建议不要总是对半切割或按黄金比例切割，而是以可定制的比例来切割绳子。

可以这样理解：如果你正走下山坡，你并不总需要迈出一大步或一小步。有时，采取一个略微更接近你推测底部位置的步幅，而不是严格遵循规则，能让你更快到达那里。

本文介绍了该新方法的两个版本：

1. “被动”算法（RatioP）

这是基础版本。它就像一个拥有固定步幅偏好的聪明徒步者。

工作原理：它根据特定比例选择一个点（作者发现，将绳子在约**20%**处切断，而非 50% 或 61%，对大多数山坡效果最佳）。
超能力：它拥有一种特殊的“视力”功能。如果山谷实际上是一个平坦的高原（即“平底”），或者地面只是稳定地向上或向下倾斜（即“单调”函数），该方法能立即识别出来。
结果：由于它能快速识别这些特殊形状，因此不会浪费时间进行不必要的步幅。在测试中，它比旧的“对半切割”方法快2.26 倍，比“黄金比例”方法快1.72 倍。

2. “主动”算法（RatioA）

这是“超级徒步者”。它不仅仅遵循比例；它在行进过程中不断学习。

工作原理：它使用与被动版本相同的智能比例切割，但还会检查最近三个已检测的点。如果这三个点看起来形成了一条曲线（抛物线），它就会利用一个数学技巧瞬间猜出曲线底部，而不是迈小步。
结果：这是所有方法中最快的。它比“对半切割”方法快3.31 倍，比黄金比例方法快2.52 倍。

“布伦特方法”的升级

有一种著名且非常快速的方法叫做布伦特方法（Brent's Method），它将黄金分割的可靠性与曲线猜测的速度结合起来。作者对这一著名方法进行了改进，将其中的“黄金比例”步骤替换为他新的“比例分割”步骤。

升级：这个现代化版本（称为 BrentM）变得极其强大。它比原始的布伦特方法快1.69 倍。
安全网：原始的布伦特方法有时会在地面完全平坦或笔直向上/向下倾斜时感到困惑。新版本通过立即识别这些形状解决了这一问题，因此绝不会犯错或陷入停滞。

结论

本文在 20 种不同类型的数学“山坡”（有些平滑，有些平坦，有些崎岖）上测试了这些新方法。

获胜者：新的比例分割方法是已知寻找单变量山谷底部的最快方法。
重要性：在计算机优化领域，“更快”意味着更少的计算量。更少的计算量意味着计算机可以用更少的时间和更少的能量解决复杂问题。

简而言之，作者找到了一种更好的方法来分割不确定性区间（即“绳子”），这使得计算机能够比以往更快地找到曲线的最低点，尤其是在曲线具有平坦区域或直线斜坡的情况下。

以下是弗拉基米尔·科德尼亚科（Vladimir Kodnyanko）所著论文《最小化单峰函数的比例区间法与算法》的详细技术总结。

1. 问题陈述

本文探讨了最小化单变量单峰函数的挑战。虽然二分搜索、**黄金分割搜索（GSS）和布伦特方法（Brent's Method）**等经典方法已确立，但它们存在局限性：

二分搜索：计算冗余，通常速度较慢。
黄金分割搜索：可靠，但缺乏针对特定函数类型（如单调函数或平底函数）加速收敛的机制。
通用效率：现有方法通常对所有单峰函数一视同仁，未能利用特定特征（如单调性或平底）来实现更快的终止。

目标是开发一种方法，通过适应被最小化函数的具体特性，减少找到最小值所需的函数评估次数。

2. 方法论

作者提出了一种新的比例区间法（Ratio Section Method），并基于此开发了三种具体算法：

A. 函数分类

该方法依赖于将单峰函数分为三类，以应用特定的优化策略：

常数函数：整个定义域均为平底。
单调函数：严格递增或递减（可能在一侧带有平底）。
严格单峰函数：具有单一最小值，可能带有平底区域（ $\alpha < \beta$ ）。

B. 核心算法

RatioP（被动算法）：
- 机制：按特定比例 $c$ 划分不确定性区间 $[a, b]$ 。新点 $p$ 根据比例 $c$ 放置在当前最小值 $m$ 的更近处。
- 优化：与二分法（ $c=0.5$ ）不同，研究发现最优比例为 $c \approx 0.2$ 。这将新的评估点放置在当前最佳估计值更近的位置，更激进地压缩不确定性区间。
- 特殊处理：包含一个逻辑块以尽早检测单调性和平底。如果找到三个纵坐标相同的点，算法立即终止。如果检测到单调性，则在边界处识别最小值。
RatioA（主动算法）：
- 机制：在 RatioP 的基础上构建，并引入了抛物线插值步骤（一种二阶方法）。
- 逻辑：一旦建立满足特定条件的三个点（在最小值周围形成“括号”），算法便计算通过这三点的抛物线顶点以预测最小值。
- 混合方法：它使用 RatioP 找到初始括号，然后切换到抛物线步骤以加速收敛；如果抛物线失败，则回退到比例划分。
现代化布伦特方法（BrentM）：
- 修改：经典的布伦特方法结合了抛物线插值与黄金分割搜索。作者用RatioP过程替换了黄金分割组件。
- 增强：现代化版本还集成了 RatioP 算法中发现的单调性和平底检测逻辑，这是原始布伦特方法所缺乏的。

3. 主要贡献

新的比例区间策略：引入了一种使用比例 $c$ （优化值为 0.2）而非固定值 0.5（二分法）或黄金比例（约 0.618）的区间划分方法。
早期终止逻辑：开发了特定的算法块（Mnt）以快速识别单调函数和常数/平底函数，使得在这些特定情况下搜索可在仅需 3–6 次评估时终止。
比例 $c$ 的优化：经验确定 $c=0.2$ 能在各种函数类型下为 RatioP 算法带来最佳性能。
布伦特方法的现代化：成功将比例区间和单调性检测集成到标准布伦特算法中，创建了一个性能优于原始版本的混合算法。

4. 实验结果

这些算法在20 种不同类型的单峰函数（平滑、平底、单调、分段）上进行了测试，并与二分法、黄金分割法和标准布伦特方法进行了比较。

性能指标：以函数评估总次数（ $\Sigma k$ ）衡量。
RatioP 与经典方法（所有 20 个函数）：
- RatioP（ $c=0.2$ ）比二分搜索快 2.26 倍。
- RatioP 比黄金分割搜索快 1.72 倍。
- 对于严格单峰函数（排除单调/平底情况），RatioP 仍比 GSS 快 1.40 倍。
RatioA 与 RatioP：
- 主动算法（RatioA）显著更快，与被动 RatioP 相比进一步减少了评估次数。
现代化布伦特（BrentM）与经典布伦特：
- BrentM 比原始布伦特方法快 1.69 倍。
- BrentM 比二分法快 约 4 倍，比 GSS 快 约 3 倍。
鲁棒性：现代化的布伦特方法消除了原始算法在最小化单调函数时出现的错误，为该类函数提供了精确结果。

5. 意义与结论

本文证明，比例区间法是传统区间消除技术的优越替代方案。

效率：通过优化划分比例并添加检测非严格单峰函数的逻辑，该方法大幅降低了计算成本。
通用性：与 GSS 或标准布伦特方法相比，该方法能更有效地处理更广泛的函数行为（单调、平底）。
实际影响：现代化的布伦特方法（BrentM）为 1D 优化设立了新基准，结合了区间消除的可靠性、抛物线插值的速度以及基于比例的加速优势。

作者得出结论，所提出的方法，特别是主动算法 RatioA 和现代化布伦特算法 BrentM，代表了目前已知最小化单峰函数的最快方法，在特定比较中比既定标准高出显著幅度（最高达 3–4 倍）。