以矩阵行列式为约束的优化

计算科学 矩阵 非线性规划
2021-12-17 11:16:42

我正在解决矩阵的约束优化A尺寸为 6x6,其中一个约束是det(A)>0. 我使用NLopt包来解决我的问题并提供目标和约束的 value&&gradient 例程。矩阵食谱中所述,矩阵行列式的梯度计算为det(A)A=det(A)(A1)T并涉及矩阵求逆。在优化迭代期间,一个中间解决方案可能会违反约束并导致奇异矩阵A. 单数A将停止优化,因为对约束梯度的评估会引发“不可逆”异常。

一种可能的解决方案是使用不需要约束梯度的优化算法。但我想知道如果我使用基于梯度的算法是否有任何解决方法。据我所知,使用梯度信息的方法会收敛得更快。

===============编辑=================

目标函数的形式为:

minAi12(EiTAEiti)2

其中Ei是已知的 6x1 向量,而ti是已知的标量。对\mathbf{A}实施的其他约束A是: (1) A是对称矩阵 (2) A的条目是非负的

2个回答

替换为可以稳定且廉价地计算行列式的因式形式。例如,为某个固定置换矩阵添加新的三角变量以及约束通常恒等排列就足够了。这意味着您将的重要条目视为附加变量。然后行列式及其梯度很容易计算。如果是对称的,则可以改用ALRA=PLRPP=ILRAA=LDLT

或者,您可以通过在 A 出现的任何地方代替它因此,代替最小化服从,比如说,你会最小化服从,(为了简单起见,假设是单位下三角形并且没有应用排列),并使用APLRf(A,detA)F(A)=0f(LR,detR)F(LR)=0LdetR=Rii

如果解决方案没有这种分解,则需要在初步最小化后PP=I

约束非常不稳定绝对可怕您是否相信在实际的、非人为的 6 x 6 对称矩阵上,将矩阵的一个元素更改 1e-15 可以使以双精度计算的行列式从 1e20 摆动到 -1e20?祝你好运,尝试有意义地确定是否det(A)>0det(A)在任何时候 > 或 < 0。渐变是您最不必担心的问题。除非您以超高精度计算,否则约束本身将不起作用,或者您可能只处理 2 或 3 维问题。Neumaier 教授为您提供了一个数值更稳定的解决方法。但我可以根据我的经验说,施加 Cholesky 分解类型约束似乎效果不佳,并且即使原始问题是凸问题,也会使问题成为非凸问题;您可能会成功,但最终可能会在您的问题中添加一堆虚假的局部最优值(甚至是鞍点?),这不是一件好事。

矩阵(约束为)对称吗,你真的希望强加并且所有领先的主子矩阵都有,即是正定的吗?如果是这样,而不是使用约束(除了其可怕的数值特性之外,它还不足以确保正定性,除非它被强加(也许你这样做?)在所有领先的主要子矩阵上),使用半定约束,Adet(A)>0det>0Adet(A)>0AA>0在线性矩阵不等式 (LMI) 意义上。即,A 是正定的约束。然而,实际的优化软件要么不接受严格的不等式约束,要么将其视为非严格的不等式约束。如果正半定是可以的,你的约束将是(在 LMI 意义上)。如果你真的需要 A 是严格正定的(det(A) 严格正),那么你需要确定一个最小可接受的特征值,然后施加约束(在 LMI 意义上)。您确实需要为约束可行性评估中使用的求解器容差留出一些余量(即求解器将允许稍微违反约束,例如 1e-6 或 1e-8)。A0min_eigA - min_eig * (Identity matrix of correct size) >= 0

在这一点上,了解您的目标函数和其他约束是什么会有所帮助。如果目标函数和其余约束是凸的(假设是最小化问题),您可以使用 CVX 或 YALMIP(两者都是免费的)来解决您的问题。你在评论中说(属于问题,所以你应该编辑)目标是二次的,但它是凸的吗?如果是非凸的,您可能仍然可以使用 YALMIP,也许与让 YALMIP 调用免费求解器 PENLAB 结合使用。如果您使用 CVX 或 YALMIP,它们会为您处理任何差异化问题。

针对问题的编辑进行编辑:如问题的编辑版本所示,被限制为对称非负并且,但不受限制为正定。实际上,维度 >= 3 的非负对称矩阵可能具有正行列式但不是正定矩阵。你愿意允许这种情况吗?如果是这样,我在上述编辑上方的回答不适用。如果实际上您要求是肯定的,那么我在编辑上方的回答确实适用,您应该进一步编辑您的问题以反映是肯定的约束。Adet(A)>0AAA