计算科学 - 最小化多个变量的不可微凸函数的数值方法 - 吾爱随笔录

计算科学线性代数优化本征系统凸优化

2021-11-27 16:46:06

我有一个不可微分的多变量凸连续函数。我有兴趣了解用于此的不同数值技术，也可能是对它们的引用。

只有你想知道我想最小化的函数（这是一个凹函数，我想最大化它，相当于最小化它的负数）时才阅读以下内容。

\begin{aligned} f (t_{1}, t_{2}) = min_{u^{T} u = 1, u \in R^{N}} u^{T} (A_{0} + t_{1} A_{1} + t_{2} A_{2}) u \end{aligned}

$\begin{align} f(t_1,t_2)=\min_{u^Tu=1,u\in \mathbb{R}^{N}}u^T(A_0+t_1A_1+t_2A_2)u \end{align}$

A_{0}, A_{1}, A_{2}

$A_0,A_1,A_2$ 都是

N \times N

$N \times N$ 实对称矩阵。实际上

f (t_{1}, t_{2})

$f(t_1,t_2)$ 是矩阵的最低特征值

A_{0} + t_{1} A_{1} + t_{2} A_{2}

$A_0+t_1A_1+t_2A_2$ 对于给定的

t_{1}, t_{2}

$t_1,t_2$ . 我知道这可以通过半定编程来解决。

1个回答

您描述的问题具有非常专业的结构。这类特征值优化问题已被广泛研究，因此您最好查看有关该主题的文献并从那里开始。您真的不想查看完全通用的不可微凸优化求解器，它们不会利用您确定的问题结构。

你没有告诉我们有多大 $N$ 是。这可能非常重要，因为这里的另一个尺寸参数是 $t$ 向量，对于您的特定特征值问题来说，这绝对是很小的。

您已经提到了这个问题的 SDP 公式。如果 $N$ 相当小（比如说小于 $N=10000$ )，那么现成的半定编程工具（SeDuMi、SDPA、CSDP等）使用原始对偶内点法应该很容易适用于这个问题。就您的时间而言，这可能是解决问题的最快方法。

另一方面，如果 $N$ 真的很大，你会想看看更专门用于特征值优化问题的方法。

其它你可能感兴趣的问题