外文翻译-最小化对称矩阵的最大特征值

中文：2782字

英文：6007字符

最小化对称矩阵的最大特征值

ON MINIMIZING THE MAXIMUM EIGENVALUE

OF A SYMMETRIC MATRIX

摘要：一个重要的优化问题是使一个函数φ(x)最小化，其中φ(x)是一个关于x 的对称矩阵的最大特征值（取绝对值）。如果这个矩阵函数是仿射的，那么φ(x)就是凸的。然而，φ(x)是不可微的，因为特征值是不可微在它们聚结点。本文提出的一个算法用来取得最小化的φ(x)是具有二次速率的。二阶导数都无须取得二次收敛的情况下，这个解是唯一的。该算法的一个重要特征是能够分割的多个特征值，如果必要的话，以取得下降方向。在这些方面，该算法对第一类Polak-Wardi-Doyle 方法显示出显著改进。这种新方法与Fletcher 对半定约束和Friedland ，Nocedal 和Overton 逆特征值问题的近期工作有很多共同之处。并会给出一些数值例子。

关键字：非光滑的优化，不可微的优化，凸规划，半定约束，最大奇异值的最小化

1、简介。很多重要的优化问题涉及特征值的约束。举个例子，结构工程，我们不妨以尽量减少一些结构受限于它的固有频率约束的成本。一个相当常见的产生于控制工程的问题是

(1.1) min φ(x)

条件是

(1.2) φ(x) = max |λi(A(x))|,

A(x)是一个关于x 的仿射函数的实对称矩阵，且

{λi(A(x)),I = 1,…,n}

是A(x)的特征值。既然A(x)是一个仿射函数，那么它可以写作

A(x) = A0 + Σxk Ak

函数φ(x)是凸的，因为一个矩阵的最大特征值关于矩阵的元素是一个凸函数。一个重要的特殊例子是

(1.3)Ak = ekekT

这里ek 是单位矩阵的第k 行，所以

(1.4)A(x) = A0 + Diag(x)

需要注意的是，非对称矩阵的最大奇异值的最小化问题的G(x)可以写作(1.1)的形式，其中矩阵 0 G(x)

G(x)T 0

的特征值（或加或减）形成G(x)的奇异值。（毫无疑问的，结果可以通过更直接地处理奇异值问题来获得。）

最小化φ(x)的困难在于，这个方程是不可微的，因为特征值是不可微在它们聚结点。此外，我们通常可以想到的解决方案是在一个不可微点，由于φ(x)的最小化一般驱动多个特征值，以得到相同的最小值。

在这篇文章中，我们提出一个算法来解决(1.1) 具有二次渐近收敛。此外，二阶导数并不总是需要获得二次收敛。为了让这篇文章显得短小精悍，我们不会给出收敛的证明以及，我们会忽略一些算法的细节，但是主旨为非常的清晰。我们相信这是第一次有二次收敛算法，或任何实用的高精度算法，用来描述最小化φ(x)问题。该算法的一个重要特征是，从任何一点不是最优得到下降方向的能力，即使这要求分裂的特征值一开始是相等的。（退化情况的例外。）这显然是一个崭新的算法。

在这些方面，这里给出的算法表示的一阶方法通过Polak 和Wardi （1982）和Doyle （1982）中描述的相同的问题有显著改善。本文受到两个工作：Fletcher （1985）和Friedland ，Nocedal 和Overton （1987）的严重影响，给予充分肯定。与Doyle 个人通信也非常有帮助。另外一个重要的早期参考Cullum ，Donath 和Wolfe （1975），对相关问题给予一阶的方法。毫无疑问，这里给出的算法的一个变种可以导出为那个问题的解。最后，我们不应忽视相关的结构工程文献（见Olhoff 和Taylor （1983，第1146页）进行了有益的调查）。

2. 与Fletche 和Friedland,Nocedal, 和Overton 的工作的联系。问题(1.1)可以重写为一个不可微约束优化问题

(2.1)minω