计算科学 - 增广拉格朗日的高效预处理器 - 吾爱随笔录

增广拉格朗日的高效预处理器

计算科学线性求解器预处理约束优化

2021-12-09 02:44:00

我想解决具有非线性等式约束的非线性问题，并且我正在使用带有惩罚正则化项的增强拉格朗日算子，众所周知，它破坏了我的线性化系统的条件数（我的意思是在每次牛顿迭代时） . 惩罚项越大，条件数越差。有人知道在那种特定情况下摆脱这种不良条件的有效方法吗？

更具体地说，我使用的是经典的增广拉格朗日，因为我有很多通常可能是多余的约束。所以盲目地将约束直接合并到原始变量中是非常方便的。我直接在 KKT 系统上尝试了基于变量消除或有效预处理器的其他更复杂的方法，但是由于约束冗余，我遇到了一些麻烦。

关于问题 $\mathbf u =[u_1,\cdots,u_n]$ 变量被公式化为遵循我的拉格朗日形式

L (u, λ) := W (u) + ρ λ^{T} c (u) + \frac{ρ}{2} c^{2} (u)

$\mathcal L(\mathbf u,\lambda):= \mathcal W(\mathbf u) + \rho \lambda^T \,c(\mathbf u) + \frac{\rho}{2} c^2(\mathbf u)$

所以一般来说，每次牛顿迭代的目标是解决以下形式的问题

A Δ u = b

$A \Delta u = b$ 使用（我们放弃约束的粗麻布）

A (u, ρ) := \nabla_{u}^{2} W (u) + ρ C^{T} (u) C (u)

$A(\mathbf u,\rho): = \nabla_{\mathbf u}^2 \mathcal W(\mathbf u) + \rho C^T(\mathbf u)C(\mathbf u)$ 和

b (u, ρ) := - (\nabla_{u} W (u) + (ρ + λ^{T} c (u)) \nabla_{u} (u))

$b(\mathbf u,\rho) :=- \big(\nabla_{\mathbf u}\mathcal W(\mathbf u) +(\rho +\lambda^Tc(\mathbf u)) \nabla_{\mathbf u}(\mathbf u)\big)$ 和首都

C

$C$ 是为了

C (u) := \nabla_{u} c (u)

$C(\mathbf u) := \nabla_{\mathbf u} c(\mathbf u)$ .

谢谢你。

2个回答

根据问题结构，您可以直接求解病态增广拉格朗日系统。例如，BDDC/FETI-DP 可以求解原始形式的几乎不可压缩的弹性，其收敛速度与泊松比无关（子域上的分段常数，但具有任意跳跃）。类似地，精确再现体积模式的多重网格方法可以具有此属性。这种方法是针对特定问题的，一般来说，较大的惩罚会导致系统难以进行预处理。

为了让预处理器选择更加灵活，我建议引入显式对偶变量并编写更大的鞍点系统

(\begin{matrix} A & C^{T} \\ C & - ρ^{- 1} \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} b \\ 0 \end{matrix})

$\begin{pmatrix}A & C^T \\ C & -\rho^{-1} \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} b \\ 0 \end{pmatrix}$

正如阿诺德·纽迈尔所建议的那样。该系统的条件要好得多，可以让您准确评估残差。如果某个惩罚系统的预处理器 $A - \tilde\rho C^T C$ 存在（其中 $\tilde \rho \le \rho$ )，您可以将其用作鞍点系统的块预处理器。有关这方面的示例，请参见Dohrmann 和 Lehoucq (2006)，其中使用 BDDC 对可压缩问题应用混合形式的不可压缩弹性的前提条件。另一类流行的方法是基于近似 Schur 补码 $-\rho^{-1} - C A^{-1} C^T$ 使用“近似换向器”参数。解决鞍点问题的方法种类繁多，参见Benzi、Golub 和 Liesen，Numerical Solution of Saddle Point Problems (2005)的综述。如果您使用的是 PETSc，那么上面评论中描述的许多方法都可以通过PCFIELDSPLIT组件使用运行时选项来构建。

如果您可以更具体地了解问题的根源（您要最小化什么以及限制是什么），我可能会建议更具体的参考资料。

为 KT 条件中的破坏项引入额外变量，您可以找到一个更大的对称系统，该系统在数值上表现良好，只有惩罚因子的倒数进入矩阵。

解决病态系统 $(A+\rho C^TC)x=b~$ 什么时候 $\rho$ 很大，介绍 $y=\rho Cx$ 并以表格形式重新提出您的问题 $Ax+C^Ty=b$ , $Cx-\rho^{-1}y=0$ ，这通常是条件良好的。

其它你可能感兴趣的问题

上一篇有限元奇异摄动反应扩散问题中的振荡下一篇数值稳定性的启发式检查