具有非简单约束的 BFGS 的解决方法?

计算科学 优化 约束优化
2021-12-09 03:48:37

在一句话中(感谢@Brian Borchers),我想最小化函数f(x,y,...),梯度g(x,y,...),受未明确给出的约束,但由计算 f 和 g 的例程返回错误的情况定义。

的域f不是线性的,改变变量并不简单。我近似了一个盒装约束,其中参数只是偶尔(仍然无限多)落在域之外。

(想想fg作为一个黑盒子,当参数不在域中时它会抛出异常。我只能创建包装器以捕获异常并返回一些值。)

所以,我使用了L-BFGS-B,并且f在参数不在域中时要非常大。我将g这些点设置为 1。

在大多数情况下,优化工作正常。然而,有时它会触发像“ABNORMAL_TERMINATION_IN_LNSRCH”这样的错误,我想这只是因为我g不同意f那些讨厌的点。

在这种情况下,一般的最佳做法是什么?

2个回答

不幸的是,L-BFGS-B 根本不是为处理此类问题而设计的。

以下是一些可能会有所帮助的建议。

  1. 如果您可以为函数定义一个平滑扩展,该扩展在可行区域之外的值会非常迅速地增加,那么您可以使用 L-BFGS-B 或其他一些无约束或有边界约束的优化代码获得合理的结果. f(x)

  2. 如果您可以定义一个平滑函数使得在可行域外且在可行域内,那么您可以使用约束优化例程来尝试解决问题.g(x)g(x)<0g(x)0

  3. 如果目标函数是凸的并且可行域是凸的,那么可以应用的方法很多。例如,您可以使用最陡下降法。您也可以使用 L-BFGS-B 并在每次方法尝试跨出可行区域时以最陡的下降步骤重新启动该方法。 f(x)

  4. 是非凸的或可行域是非凸 的一般情况下,这个问题是没有希望的。f

这取决于你关心什么。另一种可能性是选择可行的最大框,您知道它不包含域之外的任何点。假设是光滑和凸的,解决这个问题将为您提供最佳目标函数值的上限。有时,这个上限可能会有所帮助。其他时候,它根本就没有足够的信息。fgfg

不过,一般来说,我会尝试 BrianBorchers 方法中的 2 和 3 的某种组合。如果您对使用 BFGS 类型的方法感觉非常强烈,请使用他的建议,您可以使用梯度投影方法对其进行扩充,其中 BFGS 步骤被投影到可行集上,以确保每次迭代仍然可行。如果被扩展以使其在其域之外人为地非常大,那么使用梯度下降重新开始可能是一种很好的方法,而梯度投影有点过大了。f