logo标签列表

寻找整数x和y使得函数f(x,y)取得最小值

c#algorithmnumerical-analysisminimization
6
我想知道有没有人对于最小化一个函数f(x,y)（其中x和y是整数）有任何建议。我已经研究了很多最小化和优化技术，比如BFGS和GSL中的其他技术，以及Numerical Recipes中的一些技术。到目前为止，我已经尝试了几种不同的方案。第一种方案是选择下降最快的方向f(x+1,y),f(x-1,y),f(x,y+1),f(x,y-1)，并沿着该方向进行线性最小化。我还尝试使用下山单纯形（Nelder-Mead）方法。两种方法都会远离最小值而卡住。它们似乎适用于更简单的函数，比如找到抛物面的最小值，但我认为它们都（特别是前者）是为实值（双精度）的x和y设计的函数。还有一个问题是我需要尽可能少地调用f(x,y)。它与外部硬件通信，每次调用需要几秒钟的时间。如果有任何想法，将不胜感激。
这里是误差函数的示例。很抱歉我之前没有发布它。这个函数需要几秒钟的时间来评估。此外，如果设备查询的信息低于我们所需的值，则不会增加误差，只有当高于我们所需的值时才会增加。
double Error(x,y)
{
  SetDeviceParams(x,y);
  double a = QueryParamA();
  double b = QueryParamB();
  double c = QueryParamC();
  double _fReturnable = 0;
  if(a>=A_desired)
  {
    _fReturnable+=(A_desired-a)*(A_desired-a);
  }
  if(b>=B_desired)
  {
    _fReturnable+=(B_desired-b)*(B_desired-b);
  }
  if(c>=C_desired)
  {
    _fReturnable+=(C_desired-c)*(C_desired-c);
  }
  return Math.sqrt(_fReturnable)
}
1
任何关于您的函数类和行为的想法也将不胜感激。 - EFraim
1
有趣的问题。有趣的是，数学在你开始学习分数和实数时首先变得困难，然后一旦你去掉这些内容并回到自然数，它又变得困难了。=) - Jan Aagaard
1
你知道 f(x, y) 的方程式吗？ - Noldorin
2
当然这是一个编程问题。除非你认为算法不是程序。我认为任何不是算法的东西都不是编程问题。例如，在语言Y中如何做X——这是一个语言问题，而不是编程问题。 - Daniel C. Sobral
这是一个算法问题，但它涉及到纯数学中非常深入研究的主题。如果我有这样的问题，我会去数学新闻组或类似的地方寻求帮助。 - Daniel Earwicker
显示剩余2条评论
8个回答
4

这里有很多解决方案。事实上，整本书和学术学科都是基于这个主题的。我现在正在阅读一本优秀的书：如何解决问题：现代启发式。

没有一个正确的解决方案 - 不同的解决方案根据对函数的特定知识有不同的优势。甚至已经证明，没有一个启发式可以在所有优化任务中表现最佳。

如果您知道您的函数是二次的，您可以使用牛顿-高斯一步找到最小值。遗传算法可以是一个很好的通用工具，或者您可以尝试较不复杂的模拟退火。

为什么我的链接失效了？在预览中看起来不是这样。 - Brian Ramsay
3
你看过遗传算法吗？它们非常擅长寻找最小值和最大值，同时避免局部极值。
嗯，它们逐代逐渐变得更好！ - Daniel Earwicker
它们虽然非线性 :) - Indy9000
2
如果这是一个任意函数，那么没有简单的方法来实现此功能。
假设我们定义了一个函数:
f(x, y) = 0 for x==100, y==100
          100 otherwise

任何算法如何才能真实地将(100, 100)找到作为最小值？它可能是任何可能的数值组合。

您是否了解正在测试的函数的任何信息？

f(x,y) 是一个校准误差函数。我感兴趣的有两个参数，它们都受 x 和 y 的变化影响。该函数相当连续，但其导数可能不是，因为只要其中任何一个参数在规格内，我就将其设置为 0。 - Tim
2
@Jon Skeet：当然，这是假设函数可以是任何东西，这确实迫使你尝试每个(x, y)的组合。如果您知道函数是伪连续的，则事情会大大简化。 - Noldorin
@Noldorin: 这就是为什么我问OP对该函数了解多少。在我发帖的时候，我提供的函数已经满足了我们所知道的一切。 - Jon Skeet
@Jon Skeet：确实，您发布的函数是相当任意的函数示例。但是，很不可能该函数不完全是任意的（因为我们现在知道它是一个错误函数），这意味着一种更好的方法肯定是可行的。 - Noldorin
2
你有没有关于学习遗传算法的好资源建议？ - Tim
1
有很多关于这个主题的书籍。让我开始的是Goldberg的书。 http://www.amazon.com/Genetic-Algorithms-Optimization-Machine-Learning/dp/0201157675 - Indy9000
1

你通常在数学中寻找的是称为优化技术。一般来说，它们适用于实值函数，但许多可以适应于整数值函数。

特别地，我建议您研究非线性规划和梯度下降。两者都似乎非常适合您的应用。

如果您可以提供更多细节，我可能能够建议一些更具体的内容。

正如我之前所说，它将用于校准程序，因此会有许多具有类似但不完全相同误差函数形状的设备。我不知道确切的形状是什么，因为我需要获取大量数据。x和y都在0到65535之间，并且收集一条数据需要几秒钟的时间。 - Tim
@Tim：好的。你能否提供一下这个错误函数的形式？如果请求需要几秒钟的时间，我对成功并不是非常乐观！ - Noldorin
这基本上是发生的事情。如果有点模糊，我很抱歉。 double Error(x,y) { SetDeviceParams(x,y); double a = QueryParamA(); double b = QueryParamB(); double c = QueryParamC();double _fReturnable = 0 if(a>=A_desired) { _fReturnable+=(A_desired-a)*(A_desired-a); } if(b>=B_desired) { _fReturnable+=(B_desired-b)*(B_desired-b); } if(c>=C_desired) { _fReturnable+=(C_desired-c)*(C_desired-c); } return Math.sqrt(_fReturnable) } - Tim
为了避免陷入局部最小值，请尝试从随机起始点运行几次梯度下降算法。 - Gabe Moothart
@Gabe：是的，完全正确。除非你非常清楚最小值在哪里附近，否则需要从一系列起始点运行算法。 - Noldorin
1

Jon Skeet的回答是正确的。即使f在所有地方都连续，您确实需要关于f及其导数的信息。

欣赏您所要求的（仅在整数值处最小化f）困难之最简单方法就是考虑一个f：R->R（f是实变函数的实值函数），它在各个整数之间进行大幅波动。您可以轻松构造这样的函数，以便在实线上的局部最小值与整数处的最小值之间没有任何相关性，并且与一阶导数也没有关系。

对于任意函数，我看不到除了蛮力之外的其他方法。

根据我所做的测试，梯度在任何地方都很小，因此函数在整数值之间变化不大，但我无法预测它将朝哪个方向变化。暴力破解行不通，因为获取单个数据需要太长时间。 - Tim
那么，您现在是说除了只查看整数值的问题之外，您甚至不知道 f，并且您只会对 {(x,y)} 的子集进行采样并尝试从有限的子集中得出结论？ - pgast
@pgast 很不幸，这就是我的意思。我有足够的数据来猜测一个好的起点，但仅此而已。好消息是，我并不一定关心“最佳”解决方案，只要我得到的解决方案符合规格即可。 - Tim
如果这是一个关乎生命的应用程序，那么我会开始寻找另一份工作，因为你被要求做的事情将是一级过失。如果不是，那么我可能会使用智能子集的暴力方法。你可以采取多少个样本？我会尝试在64Kx64上覆盖一个网格，使得网格点的数量为nsamples，在网格点处进行采样并选择最小值。 - pgast
1
如果您对该函数有真正的了解，则初始网格可能会少一些点，比如nsamples-m，并且您可以使用最后m个采样来在前(nsamples-m)个采样的最小值周围进行蛮力搜索。如果我理解正确，您正在寻找一个(x,y)参数对，以便设置设备，使误差很小。 - pgast
1

让我们用数学术语来看看你的问题。这一切都是在我完全理解你的问题的前提下。如果我有误，请随时纠正我。

我们想要最小化以下内容：

\sqrt((a-a_desired)^2 + (b-b_desired)^2 + (c-c_desired)^2)

或者用其他符号表示为 ||Pos(x - x_desired)||_2

其中x = (a,b,c)，而Pos(y) = max(y, 0)表示我们想要“正部分”（这解释了您的if语句）。最后，我们希望将自己限制在x为整数值的解决方案中。

与上面的帖子不同，我认为遗传算法根本不是你想要的。
实际上，我认为解决方案要简单得多（假设我理解了你的问题）。

1）在上述函数上运行任何优化例程。这将给出解决方案x^* = (a^*, b^*,c^*)。由于该函数随着变量的增加而增加，因此您可以期望的最佳整数解为(ceil(a^*),ceil(b^*),ceil(c^*))。

现在你说你的函数可能难以评估。存在一些不基于启发式的工具来解决这个问题，它们被称为无导数优化。人们使用这些工具来基于模拟优化目标（我甚至听说过一个目标函数是基于庄稼产量的案例！）

这些方法各有不同的特性，但通常它们不仅试图最小化目标，还试图减少目标函数的评估次数。

对于无导数优化而言，这是一个好的建议，但是数学上的陈述应该明确提到“x”是一个函数，并且或许可以重新命名“x”，以避免与已发布源代码中的变量相冲突。 - outis
x不是一个函数，它只是将变量a、b、c集合成一个向量。 - SplittingField
1
Tim不想将Err_A（x）= ||Pos（x-A）||₂最小化，而是将目标转向于Err_A（Dev（u）），其中Dev(u)：Z²-> R³。如果解在x中，它不需要是整数。此外，ceil · x'可能不是x中的有效解，因为可能不存在u'使得ceil · x'=Dev(u')。对于某些Dev'(u):R²-> R³的扩展（如梯田、网格），u的解将是整数值。如果一个奇特的Dev'(u)在u'∉Z²处有一个最小值，则{ceil，floor}²· u'元素可能不是解。 - outis
有趣的...我需要稍微思考一下这个问题，但显然我在他的函数定义中误解了某些东西。不过，我认为还有其他非启发式解决方案可用于此类问题，我知道工业界使用的一个例子是MADS。 - SplittingField
Dev 代表设备。这是他的 Error(x,y) 函数的前四行。 - outis
0

抱歉之前格式很糟糕。这是一个错误函数的示例

double Error(x,y)
{
SetDeviceParams(x,y);
double a = QueryParamA();
double b = QueryParamB();
double c = QueryParamC();
double _fReturnable = 0;
if(a>=A_desired)
{
  _fReturnable+=(A_desired-a)*(A_desired-a);
}
if(b>=B_desired)
{
 _fReturnable+=(B_desired-b)*(B_desired-b);
}
if(c>=C_desired)
{
  _fReturnable+=(C_desired-c)*(C_desired-c);
}
return Math.sqrt(_fReturnable)
}
啊，好的，我已经为您完成了。格式最终有所不同，因为我愚蠢地从显示文本而不是编辑文本中复制了内容。 - Daniel C. Sobral
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接