Main Content

本页采用了机器翻译。点击此处可查看英文原文。

模式搜索术语

构型

模式是一组向量 {v i}，模式搜索算法使用它来确定每次迭代时要搜索哪些点。集合 {v i} 由目标函数中的独立变量的数量 N 和正基集定义。模式搜索算法中两个常用的正基集是最大基（具有 2 个 N 向量）和最小基（具有 N+1 个向量）。

对于 GPS，形成模式的向量集合是固定方向的向量。例如，如果优化问题中有三个独立变量，则 2 N 个正基础的默认值由以下模式向量组成：

v1=[100]v2=[010]v3=[001]v4=[−100]v5=[0−10]v6=[00−1]

N +1 个正基础由以下默认模式向量组成。

v1=[100]v2=[010]v3=[001]v4=[−1−1−1]

对于 GSS，该模式与 GPS 模式相同，除非存在线性约束并且当前点靠近约束边界。有关 GSS 如何形成具有线性约束的模式的描述，请参阅 Kolda、Lewis 和 Torczon [1]。当有线性约束时，GSS 算法比 GPS 算法更有效。有关显示效率提升的示例，请请参阅 比较轮询选项的效率。

使用 MADS，形成模式的向量集合由算法随机选择。根据轮询方法的选择，选择的向量数量将是 2 N 或 N+1。与 GPS 一样，2 个 N 向量由 N 向量及其 N 负数组成，而 N+1 向量由 N 向量和一个为其他向量之和的负数的向量组成。

参考

[1] Kolda, Tamara G., Robert Michael Lewis, and Virginia Torczon. “A generating set direct search augmented Lagrangian algorithm for optimization with a combination of general and linear constraints.” Technical Report SAND2006-5315, Sandia National Laboratories, August 2006.

网格

在每个步骤中，patternsearch 都会搜索一组点（称为网格），以寻找可以改善目标函数的点。patternsearch 通过以下方式形成网格

  1. 通过将每个模式向量 v i 乘以标量 Δ m 来生成一组向量 {d i}。Δ m 被称为网格大小。

  2. 将 {di} 添加到当前点-上一步找到的具有最佳目标函数值的点。

例如，使用 GPS 算法。假设：

  • 当前点是 [1.6 3.4]。

  • 该模式由向量组成

    v1=[10]v2=[01]v3=[−10]v4=[0−1]

  • 当前网格大小 Δ m 为 4。

该算法将模式向量乘以 4，并将其添加到当前点以获得以下网格。

[1.6 3.4] + 4*[1 0] = [5.6 3.4] 
[1.6 3.4] + 4*[0 1] = [1.6 7.4] 
[1.6 3.4] + 4*[-1 0] = [-2.4 3.4] 
[1.6 3.4] + 4*[0 -1] = [1.6 -0.6]

产生网格点的模式向量称为其方向。

轮询

在每个步骤中，该算法通过计算目标函数值来轮询当前网格中的点。当完全轮询选项具有（默认）设置 Off 时，算法一旦找到目标函数值小于当前点的点，就会停止轮询网格点。如果发生这种情况，则称轮询成功，并且它找到的点将成为下一次迭代的当前点。

该算法仅计算停止轮询之前的网格点及其目标函数值。如果算法未能找到能够改善目标函数的点，则轮询被称为不成功，并且当前点在下一次迭代中保持不变。

当完整轮询选项的设置值为 On 时，该算法会计算所有网格点处的目标函数值。然后，算法将目标函数值最小的网格点与当前点进行比较。如果该网格点的值小于当前点，则轮询成功。

扩张与收缩

轮询后，算法改变网格大小的值 Δ m。默认情况下，轮询成功后将 Δ m 乘以 2，轮询不成功后乘以 0.5。

相关主题