计算科学 - 半定规划中的 log(det(X)) - 吾爱随笔录

半定规划中的 log(det(X))

计算科学优化凸优化半定规划

2021-12-11 02:50:34

我一直在解决形式的问题

m a x l o g (d e t (A)) s . t . A = A^{T} ⪰ 0, p_{i}^{T} A p_{i} \leq b_{i}

$max \ log(det(A)) \\ s.t. \ A = A^{T} \succeq 0, \\ p_{i}^{T}Ap_{i} \leq b_{i}$ 在哪里

b_{i}

$b_{i}$ 和

p_{i}

$p_{i}$ 是输入向量（要清楚有不止一个向量

b_{i}

$b_{i}$ 和

p_{i}

$p_{i}$ )，使用 CVXPY 和 SCS。我发现转换为规范形式需要大量时间（实际上，它比实际解决生成的 SDP 需要更长的时间）。我的第一个想法是事先手动进行转换（即以 SCS 期望的形式表达问题），但我无法弄清楚如何表达

l o g (d e t (A))

$log(det(A))$ 形式为

c^{T} x

$c^{T}x$ .

作为参考，SCS 解决了形式的问题

m i n c^{T} x s . t . A x = b, A \in K

$min \ c^{T}x \\ s.t. Ax=b, \\ A \in K$ 在哪里

K

$K$ 是一个凸锥（在本例中为正半定锥）。

我的第一个想法是定义一个新变量 $L=log(A)$ 现在计算 $tr(L)$ ，但 $L=log(A)$ 不是线性约束，所以这似乎没有让我到任何地方。我知道这可以以某种形式完成（否则 CVXPY 将无法首先将问题发送到 SCS），但这对我来说非常不透明。

编辑：澄清有不止一个输入向量，因此对范围的约束不止一个 $A$ .

2个回答

行列式是所有特征值的乘积 $\lambda_i(A)$ , 所以它的对数是特征值的对数之和。因此，您可以编写如下目标函数：

min_{A} - \sum_{i} \log λ_{i} (A) .

$\min_A \quad-\sum_i \log\lambda_i(A).$ 现在，假设您有一个试图变为零的特征值，那么它的对数将变为负无穷大，因此它的负对数将变为正无穷大。换句话说，目标函数也隐含地是一种对数障碍法，确保矩阵的正定性。您的第一个约束简化为

s.t. A = A^{T} .

$\text{s.t.}\quad A=A^T.$ 第二个约束意味着

min_{i} λ_{i} (A) \leq \frac{b}{‖ p ‖^{2}} .

$\min_i \lambda_i(A) \le \frac{b}{\|p\|^2}.$ 这有点难以理解，但您可以通过以下方式看到这一点：假设您有一个矩阵

A

$A$ 和

v_{i}

$v_i$ 是它的特征向量。然后

p^{T} A p = \sum_{i} λ_{i} (p \cdot v_{i})^{2} .

$p^T A p = \sum_i \lambda_i (p\cdot v_i)^2.$ 这是因为对称正定矩阵的特征向量形成正交基。作为结果，

p^{T} A p \geq (min_{i} λ_{i}) ‖ p ‖^{2} .

$p^T A p \ge (\min_i \lambda_i) \|p\|^2.$ 如果达到最小值

p ∥ v_{min}

$p \parallel v_\text{min}$ .

那么这里是你如何构建一个最大化你的目标函数（或最小化我的）的矩阵：

选择一个特征向量等于的矩阵 $v_1=\frac{p}{\|p\|}$ 和对应的特征值 $\lambda_1=\frac{b}{\|p\|^2}$ .
选择剩下的 $n-1$ 任何你喜欢的特征向量，但它们形成一个标准正交基。随意选择它们的特征值——包括大于 $\lambda_1$ .

因为您可以随心所欲地选择其他特征值，所以现在很明显您可以使您的目标函数尽可能大。换句话说，构造表明您提出的问题没有解决方案：您认为可以达到的矩阵集没有最大值。

（例如，选择 $p=(1,0)^T$ 和 $b=1$ . 然后任何形式的矩阵

A = (\begin{matrix} 1 & 0 \\ 0 & α \end{matrix})

$A=\begin{pmatrix}1 & 0 \\ 0 & \alpha\end{pmatrix}$ 满足您的约束

α > 0

$\alpha>0$ . 你的目标函数是

\log det A = \log α

$\log\text{det}A=\log\alpha$ ，你可以把它做成你喜欢的大小。）

首先，使用 Epigraph 公式将目标移动到约束条件

最大吨

以 log_det(A) 为准 $\ge$ 吨

加上你的其他限制。

Mosek Modeling Cookbook https://docs.mosek.com/modeling-cookbook/sdo.html#semidefinite-modeling的第 6.2.3 节展示了如何制定 log_det(A) $\ge$ t 根据 SDP 和指数锥约束的组合，SCS 都支持这两种约束。

但是，在您的情况下，您也可以最大化 A 的行列式的第 n 个根，这消除了对数，从而避免了指数锥，有利于幂锥或二阶锥约束。根据第 6.2.3 节末尾的提示，您可以使用第 4.2.4 节中的公式https://docs.mosek.com/modeling-cookbook/powo.html来使用 SCS 的功率锥约束来处理几何A 的特征值的平均值，它又是为 SDP 约束引入的矩阵“Z”的对角元素，如第 6.2.3 节所示。或者，您可以根据二阶锥约束来制定几何平均值。

把这些都打出来很麻烦，所以我把它留给你。

其它你可能感兴趣的问题

上一篇有限元法的 Gauss-Lobatto 正交和节点下一篇近似函数，使得近似的逆是“简单的”