通过扭曲参数空间来处理Nelder-Mead优化中的箱体约束问题。

Question

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

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

预期的方法是使用一个惩罚函数，并确保所有的实例都是：------。f(x) 是 "没有吸引力 "的，当x出界时。

该算法的工作原理不同：有关的实现并不触及 f(x). 相反，它使用反双曲正切来扭曲参数空间。atanh(f). 现在，简单运算法则可以在一个没有边界的空间里自由操作，随便选一个点。在它得到 f(x) 为了评估x处的解，算法会切换回正常空间。

乍一看，我觉得这个想法很巧妙。这样我们就避免了惩罚函数的缺点。但现在我有了怀疑。扭曲的空间会影响终止行为。一个终止标准是简单化的大小。通过将参数空间膨胀到 atanh(x) 我们还夸大了单数的大小。

对该算法的实验也表明，它并没有按照预期的方式工作。我还不明白这种情况是如何发生的，但我确实得到了出界的结果。我可以说，几乎一半的返回的局部最小值都是出界的。

作为一个例子，看看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实现，这个包调用了另一个包dfoptim中的nmkb函数。

Answer 1

(这个问题与 optimx它只是一个提供无约束优化的R包的封装器）。)

这个函数是 nmkb() 在 dfoptim 包，用于无梯度优化例程。将有界区域转化为无界空间的方法是一种常见的方法，可以使用许多不同的变换函数，有时取决于边界的种类和目标函数的类型。它也可以应用，例如，将无界积分域转化为有界域。

如果最优点位于边界，这种方法就会出现问题，因为最优点会被送到(接近)无穷大，最终无法达到。例程将不会收敛或解相当不准确。

如果你认为该算法工作不正确，你应该写信给该包的作者，并且--这很重要--为你认为的错误或不正确的解添加一两个例子。如果没有明确的代码例子，这里没有人能够帮助你。

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

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

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

编辑 (与Erwin Kalvelagen讨论后)

出现了局部最小值(有些坐标为负).如果将下限设置为0。nmkb() 将找到全球最小值 (1,1,1,1,1,1) 在任何情况下。注意：起始值必须是可行的，就是它们的坐标都要大于0。