2

我有一个非常复杂的模型,其中包含许多需要解决的参数。尽管模型很复杂,但每一步的函数形式并不是不规则的。

我看到一些带有起始值的奇怪行为。如果我从标准的随机值(全为 0)开始,求解器会在 673 秒内以“找到局部最优解”、0 次 CG 迭代收敛。

如果我从我知道的接近解的值开始,求解器会在 1718 秒内收敛于“无法改进原始可行解估计。”,493 次 CG 迭代。

请注意,在这两种情况下,最终值都相同(或非常相似)。

2个问题:

  • 共轭梯度迭代的次数究竟是多少,例如求解器何时需要计算共轭梯度?在 1 种情况下,我看到 0 次 CG 迭代,在另一种情况下,我看到 493 次 CG 迭代。这意味着什么?(请注意,我确实知道 CG 方法是什么,只是不确定为什么在一种情况下与 0 存在巨大差异。)
  • “更好的”初始值会显着减慢优化收敛的所有可能解释是什么?
4

3 回答 3

5

从您的第一个问题中,我们了解到您正在使用“智能”求解器,即动态调整算法以优化收敛。共轭梯度法是“长程”寻找最优值的好方法,但在接近浅层最优值时收敛速度较慢。

与所有“智能”代码一样,存在启发式失败的情况,而您遇到过这种情况。我假设您的最优值相当浅,因此如果您的参数稍有变化,目标函数(即您尝试优化的实际标准)变化很小。现在求解器无法知道参数已经非常接近最优值。据它所知,在目标函数非常平坦的区域中,它可能与解决方案相去甚远。经过一些初始测试,因此默认使用共轭梯度法,这是一种接近最优值的缓慢但安全的方法。但是,由于经过大量搜索,它实际上并没有走得很远,它告诉你,如果你很幸运,你开始接近最优,但如果你不走运,你的解决方案很远,

如果您知道您的初始猜测会非常好,那么您可能需要检查您的求解器是否允许指定应该/不应该使用哪些算法。

于 2012-04-21T17:24:43.667 回答
5

共轭梯度是一种梯度型优化算法(也称为“最速下降”),在某些情况下可能容易收敛缓慢。即使您接近最佳状态。

WikiPedia 上,您可以找到说明这种行为的数字,我在这里改编了其中一个:

优化收敛问题

您看到的是等高线图上的等成本(或等目标)线。假设我们从第 1 点开始,这是一个很好的起始值。红线表示达到最佳状态的路径。我们看到它曲折走向最优,这需要大量的功能评估,因此需要时间。

如果我们将其与选择 A 点作为起始值时的性能进行比较,我们会获得更快的收敛(或者至少,这是我在这种情况下所期望的)。假设在这种情况下只需要一次迭代。

现在看看第 5 点,它显然已经接近最优,但是需要大量的迭代才能达到最优。当您接近一个狭窄的山谷时,该算法将从一侧跳到另一侧,在途中只取得很小的进步。当您从山谷较宽的一侧接近时,您会看到梯度更倾向于最佳值,这会导致更快的收敛。

在您的情况下,可能是您的初始值有点像上面的第 5 点,而通用起始值与 A 点相当。这是假设您的起始值收敛到真实值,这可能不是案子。如果您的起始值很接近,但在它和全局最优值之间有一个峰值,您将不会收敛到正确的值,如下图所示。

在此处输入图像描述

当 knitro 更改为 CG 或其他算法之一时,应该在文档中提及或者只有 knitro 的开发人员知道。

于 2012-04-21T17:41:38.543 回答
-1

嗯,这是因为起始值只是问题解决方案的近似值,因为迭代解决方案试图通过尝试收敛到最终值来接近,那么,越接近答案起始值,越少您需要收敛的迭代。收敛阈值也应该计算在内。

这是典型的知情与非知情问题,如果您从 ad-hoc 值开始,如果您从良好的非 ad-hoc 值开始,结果将更难找到。

于 2012-04-21T16:09:36.603 回答