模式搜索术语
构型
模式是一组向量 {v i},模式搜索算法使用它来确定每次迭代时要搜索哪些点。集合 {v i} 由目标函数中的独立变量的数量 N 和正基集定义。模式搜索算法中两个常用的正基集是最大基(具有 2 个 N 向量)和最小基(具有 N+1 个向量)。
对于 GPS,形成模式的向量集合是固定方向的向量。例如,如果优化问题中有三个独立变量,则 2 N 个正基础的默认值由以下模式向量组成:
N +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
通过以下方式形成网格
通过将每个模式向量 v i 乘以标量 Δ m 来生成一组向量 {d i}。Δ m 被称为网格大小。
将 添加到当前点-上一步找到的具有最佳目标函数值的点。
例如,使用 GPS 算法。假设:
当前点是
[1.6 3.4]
。该模式由向量组成
当前网格大小 Δ 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。