用于约束优化的软件包?

计算科学 pde 优化 非线性规划
2021-12-15 21:09:27

我正在寻找解决约束优化问题,我知道一些变量的界限(特别是盒装约束)。

argminuf(u,x)

受制于

c(u,x)=0
ad(u,x)b

其中u是设计变量的向量,x是状态变量的向量,c(u,x)是等式约束(通常是 PDE)。下约束和上约束ab可以是空间可变的。

哪些软件包可以处理这种形式的系统?

4个回答

我决定根据一些评论从根本上编辑我的答案。

我没用过TAO。通过阅读文档,似乎 TAO 可以处理约束优化问题(不包括只有框约束的特殊情况)的唯一方法是使用Karush-Kuhn-Tucker (KKT) 条件将问题转换为变分不等式,其中在约束条件下是必要的(我通常看到的类型是Slater 点条件),并且在目标和约束的凸性下是充分的(更一般地说,类型 1 invexity)。如果f是非凸的,使用 KKT 条件的变分不等式公式并不等价于原始优化问题,所以严格来说,如果要对优化问题进行全局最优,则不应将其表示为变分不等式。对于 PDE 约束优化(见下文),无论如何都很难找到全局最优值,所以忽略这个细节可能很好。鉴于 Wolfgang 所说,我对使用 TAO 持怀疑态度。我已经持怀疑态度,因为它没有实现将非线性程序 (NLP) 解决为 NLP 的方法,而不是变分不等式。

我不是 PDE 约束优化方面的专家;我的同事和同事研究 ODE 约束的优化问题。我知道对于侵入式公式,Larry Biegler(和其他人)将使用搭配方法来离散化 PDE 并使其成为一个非常大的稀疏 NLP,然后他将使用内点方法来解决它。要真正解决全局最优性问题,您还需要生成凸松弛,但据我所知,没有采用这种方法,因为 PDE 约束的优化问题会导致如此大的 NLP,以至于很难解决它们全局最优。我之所以提到这些细节,只是因为问题的表述会严重影响求解器包的选择。对于非侵入式公式,重复 PDE 求解优化算法的产量梯度信息。

一些研究 ODE 约束的优化问题的人使用类似的方法,即使用搭配和数值方法对问题进行离散化,然后放松得到的 NLP 以产生用于全局优化算法的凸公式。ODE 约束优化的另一种方法是放松问题,然后离散化 ODE,这是我实验室采用的方法。可以放宽某些类型的 PDE 约束优化问题,但我不知道针对该问题所做的任何现有工作。(这曾经是我实验室的一个潜在项目。)

最终,重要的不是原始 PDE 的可微性,而是离散化相对于决策变量的可微性。

如果离散化问题对于决策变量是二次可微的,则以下包将计算局部解:

  • IPOPT是由 IBM 的 Andreas Wächter 开发的开源内点求解器。这是一个非常高质量的代码。作为内点求解器,它更适合具有大型稀疏雅可比矩阵的目标函数,并且对于 PDE 约束优化很有用
  • SNOPT是一种商业顺序二次规划求解器,是另一种高质量代码。它更适合具有小而密集的雅可比矩阵的目标函数,因此我不希望它对 PDE 约束优化有用,但您可以尝试一下。
  • NLopt是由 MIT 的 Steven Johnson 编写的小型开源代码,其中包含许多非线性优化算法的基本实现。所有算法都应该足以解决有界约束问题。
  • fmincon在 Matlab 中实现了许多用于非线性优化的算法(包括内点和顺序二次规划)
  • GAMSAMPL都是用于制定优化问题的商业建模语言,并包含与大量非线性规划求解器的接口。我知道GAMS有一个试用版,可以用于小问题,问题实例也可以提交到NEOS服务器解决。

但是,离散化可能只能相对于决策变量进行一次微分,在这种情况下,您应该在计算局部解时使用投影最速下降法或其他一些一阶优化方法。由于许多研究都集中在可以使用二阶方法的问题上(当你可以使用它们时,它们优越的收敛性使它们成为更好的选择),我找不到许多不是解决方案的最速下降的实现到作业问题。GNU 科学图书馆一个实现,但它仅用于演示目的。您可能需要编写自己的实现代码。

如果问题仅关于决策变量是连续的,那么您可以使用直接方法在本地解决它。Kolda、Lewis 和 Torczon对直接方法进行了出色的调查这些方法中最广为人知的是Nelder-Mead 单纯形算法它不能保证在多个维度上收敛到局部最小值,但无论如何它已经找到了相当大的实际用途。

包的选择实际上取决于您要用于解决问题的语言,如果解决边界约束问题只是您想要实现的算法的一部分(或者如果它是算法中的唯一步骤,在这种情况下建模语言对于生产代码变得更可行),问题的类型和大小,以及是否需要任何并行性。

我们已经尝试过 TAO,但发现它对于不等式约束问题不是很有用。至少自 2003 年以来,它基本上也仅处于维护模式,除了更新以跟踪构建它的 PETSc 的变化之外,没有真正的新功能。

另一种选择是OPT++它通过高效的非线性内点求解器支持线性和非线性约束,提供对函数精度的控制(如果需要数值微分)、对步长的控制等。我通常优化大型隐式函数(例如 FEM),其中这些类型的控件可能很有用。

如果问题被表述为互补问题,您可以使用TAO(高级优化工具包)。TAO 中的一些方法,例如缩减空间方法(活动集方法的一种变体),目前可作为 PETSc 中的 SNES ( SNESVI ) 的一部分。