通过扭曲参数 space 处理 Nelder-Mead 优化中的框约束

Question

我对 Nelder-Mead 算法 (1) 的具体实现有疑问，该算法以不寻常的方式处理框约束。我在任何论文（25 篇论文）、教科书（搜索其中 4 篇）或互联网上都找不到任何关于它的信息。

我有一个典型的优化问题：min f(x) 带有框约束 -0.25 <= x_i <= 250

预期的方法是使用惩罚函数，并确保当 x 超出范围时 f(x) 的所有实例都是 "unattractive"。

算法的工作方式不同：所讨论的实现不涉及 f(x)。相反，它使用反双曲正切 atanh(f) 扭曲了参数 space。现在，单纯形算法可以在 space 中无限制地自由运行并选择任意点。在获得 f(x) 以评估 x 处的解决方案之前，算法切换回正常 space.

乍一看，我觉得这个想法很巧妙。这样我们就避免了惩罚函数的缺点。但现在我有疑问了。扭曲的 space 会影响终止行为。一个终止标准是单纯形的大小。通过用 atanh(x) 膨胀参数 space 我们也膨胀了单纯形的大小。

对该算法的实验还表明它没有按预期工作。我还不明白这是怎么发生的，但我确实得到了超出范围的结果。我可以说返回的局部最小值几乎有一半是越界的。

举个例子，当我们逐渐改变框约束的宽度时，看一下 nmkb() 优化 rosenbrook 函数：

rosbkext <- function(x) {
  # Extended Rosenbrock function
  n <- length(x)
  sum (100*(x[1:(n-1)]^2 - x[2:n])^2 + (x[1:(n-1)] - 1)^2)
}

np <- 6 #12
for (box in c(2, 4, 12, 24, 32, 64, 128)) {
  set.seed(123)
  p0 <- rnorm(np)
  p0[p0 > +2] <- +2 - 1E-8
  p0[p0 < -2] <- -2 + 1E-8

  ctrl <- list(maxfeval = 5E4, tol = 1E-8)
  o <- nmkb(fn = rosbkext, par = p0, lower = -box, upper = +box, control = ctrl)
  print(o$message)
  cat("f(", format(o$par, digits = 2), ") =", format(o$value, digits=3), "\n")
}

输出表明它声称会收敛，但在三种情况下并没有。它对 (-2,2) 和 (-12,12) 的边界执行此操作。我可能会接受，但它也会在 (-128, 128) 处失败。我也对无约束的 dfoptim::nmk() 进行了同样的尝试。那里没有麻烦。完美收敛

[1] "Successful convergence"
f( -0.99  0.98  0.97  0.95  0.90  0.81 ) = 3.97 
[1] "Successful convergence"
f( 1 1 1 1 1 1 ) = 4.42e-09 
[1] "Successful convergence"
f( -0.99  0.98  0.97  0.95  0.90  0.81 ) = 3.97 
[1] "Successful convergence"
f( 1 1 1 1 1 1 ) = 1.3e-08 
[1] "Successful convergence"
f( 1 1 1 1 1 1 ) = 4.22e-09 
[1] "Successful convergence"
f( 1 1 1 1 1 1 ) = 8.22e-09 
[1] "Successful convergence"
f( -0.99  0.98  0.97  0.95  0.90  0.81 ) = 3.97

为什么约束算法比无约束算法更难收敛？

脚注 (1)：我指的是在 R 中的 optimx 包中使用的 Nelder-Mead 实现。这个包使用 nmkb 函数调用另一个包 dfoptim。

Answer 1

（这个问题与optimx无关，它只是提供无约束优化的R包的包装器。）

有问题的函数是 dfoptim 包中的 nmkb()，用于无梯度优化例程。将有界区域转换为无界空间的方法是一种常见的方法，可以应用于许多不同的转换函数，有时取决于边界的种类 and/or 和 objective 函数的类型。它也可以应用于，例如，将无界积分域转换为有界积分域。

如果最佳点位于边界处，则该方法存在问题，因为最佳点将被发送到（接近）无穷大并且最终无法达到。例程不会收敛或解法很不准确

如果您认为该算法无法正常工作，您应该写信给该程序包的作者，并且——这很重要——为您认为是错误或不正确的解决方案添加一两个示例。如果没有明确的代码示例，这里没有人能够帮助您。

(1) 这些变换定义了有界区域和无界区域之间的双射映射，这种方法背后的理论是显而易见的。您可以在有关多元微积分的书籍中了解可能的变换。

(2)边界外惩罚的方法有其自身的缺点，例如目标函数在边界处将不平滑，BFGS方法可能不再适用。

(3) 您可以在同一个 dfoptim 包中通过函数 hjkb() 尝试 Hooke-Jeeves 算法。它会更慢，但使用不同的方法来处理边界，不涉及转换。

编辑（在上面与 Erwin Kalvelagen 的讨论之后）

似乎存在局部最小值（某些坐标为负值）。如果将下限设置为 0，nmkb() 将在任何情况下找到全局最小值 (1,1,1,1,1,1)。
注意：起始值必须是可行的，即它们的所有坐标都大于 0。

通过扭曲参数 space 处理 Nelder-Mead 优化中的框约束

Handling box constraints in Nelder-Mead optimisation by distorting the parameter space

algorithm

heuristics

r

nonlinear-optimization