半正定规划(SDP)例:最小化矩阵范数(2-norm of a matrix)

2022/3/19 6:29:45

本文主要是介绍半正定规划(SDP)例:最小化矩阵范数(2-norm of a matrix),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

正所谓我不能直接搜到答案就得让以后的小朋友能直接搜到答案。主要是不小心通了个宵,乱吃了好些很不健康还大概确乎过期了的东西,刚刚还喝了口过期牛奶(很绝),脑子不大清醒,不想搞作业,反正也不会还搞不完。

目录
  • 半正定规划(Semidefinite program)
  • 矩阵的2-范数(2-norm of a matrix)
  • 以SDP描述最小化矩阵范数
  • 参考

半正定规划(Semidefinite program)

半正定规划长这样:

\[\begin{aligned} \text{min} ~~~ & C \bullet X \\ \text{s.t.} ~~~ & A_i \bullet X = b_i, ~~~ i = 1, \dots, m \\ & X \succeq 0; \end{aligned} \]

其对偶问题是:

\[\begin{aligned} \text{max} ~~~ & b^Ty \\ \text{s.t.} ~~~ & \sum_{i = 1}^{m} y_i A_i + S = C, \\ & S \succeq 0, \end{aligned} \]

其中给定了常量 \(A_i \in \mathcal{SR}^{n \times n}\), \(b \in \mathcal{R}^m\), \(C \in \mathcal{SR}^{n \times n}\),而变量是 \(X, S \in \mathcal{SR}^{n \times n}\),\(y \in \mathcal{R}^m\)。

矩阵的2-范数(2-norm of a matrix)

向量 \(u \in \mathcal{R}^{n}\) 的2范数,即其欧式空间长度为:

\[\Vert u \Vert_2 = u^T u. \]

矩阵 \(H \in \mathcal{R}^{m \times n}\) 的2-范数相应为:

\[\Vert H \Vert_2 = \max_{\Vert u \Vert_2 = 1} \Vert H u \Vert_2. \]

这个东西可以被证明是矩阵 \(H^T H\) 的最大特征值的平方根,即 \(H\) 的最大奇异值。大致过程如下。

\[\Vert H u \Vert_2 = \sqrt{(Hu)^T (Hu)} = \sqrt{u^T H^T H u}. \]

\(H^T H \in \mathcal{SR^{n \times n}}\),即 \(H^T H\) 是对称半正定矩阵,那么可以特征分解(Eigendecomposition)

\[H^T H = Q \Lambda Q^T, \]

其中 \(\Lambda \in \mathcal{R^{n \times n}}\) 为其特征值构成的对角矩阵,\(Q \in \mathcal{R^{n \times n}}\) 为对应的特征向量构成的正交矩阵。

分别用 \(\lambda_{\max} ( \cdot)\) 以及 \(\lambda_{\min} ( \cdot)\) 来表示矩阵的最大特征值和最小特征值,那么

\[\begin{aligned} u^T H^T H u &= u^T Q \Lambda Q^T u \\\\ &\leq u^T Q ~ [\lambda_{\max} ( H^T H) I ] ~ Q^T u \\\\ &= \lambda_{\max} ( H^T H) ~ u^T Q^T Q u \\\\ &= \lambda_{\max} ( H^T H) ~ \Vert H u \Vert_2. \end{aligned} \]

那么代入原来的式子可以得到结果

\[\begin{aligned} \Vert H \Vert_2 &= \max_{\Vert u \Vert_2 = 1} \Vert H u \Vert_2 \\\\ &\leq \max_{\Vert u \Vert_2 = 1} \sqrt{\lambda_{\max} ( H^T H) ~ \Vert H u \Vert_2} \\\\ &= \sqrt{\lambda_{\max} ( H^T H)}. \end{aligned} \]

好了写到这里发现这里不等式传递的好像有点不对,whatever,交都交了,我也懒得深究了。

以SDP描述最小化矩阵范数

用矩阵簇 \(H_i \in \mathcal{R}^{n \times n}\),\(i = 0, 1, \cdots, k\),和向量 \(x = (x_1, x_2, \cdots, x_k) \in \mathcal{R}^k\) 定义矩阵 \(H(x) = H_0 + x_1H_1 + \dots + x_kH_k\). 最小化其2-范数(\(\Vert H(x) \Vert_2\))的问题可以被写为一个线性半正定优化问题。

由前文得到最小化 \(\Vert H(x) \Vert_2\),即为最小化 \(\sqrt{\lambda_{\max} ( H(x)^T H(x))}\). 而

\[\begin{aligned} &\sqrt{\lambda_{\max} ( H(x)^T H(x))} \leq t \\\\ \Longleftrightarrow ~~~ & \lambda_{\max} ( H(x)^T H(x)) \leq t^2 \\\\ \Longleftrightarrow ~~~ & \lambda_{\max} ( H(x)^T H(x) - t^2 I) \leq 0 \\\\ \Longleftrightarrow ~~~ & \lambda_{\min} (t^2 I - H(x)^T H(x)) \geq 0 \end{aligned} \]

最小的特征值大于等于零则所有的特征值都大于等于零,则 \(t^2 I - H(x)^T H(x) \succeq 0\). 等价于

\[\begin{bmatrix} tI&H(x)^T \\ H(x)&tI \end{bmatrix} \succeq 0. \]

所以原问题可以写成

\[\begin{aligned} \text{min} ~~~ & t \\ \text{s.t.} ~~~ & \begin{bmatrix} tI&H(x)^T \\ H(x)&tI \end{bmatrix} \succeq 0. \end{aligned} \]

欢迎指正,但我都已经交了。这课迟早挂。希望是个反向Flag。

参考

(PDF) Large Scale Optimization with Interior-Point Methods | Jacek Gondzio - Academia.edu

矩阵奇异值与矩阵范数之间有什么联系? - 知乎 (zhihu.com)

03-凸优化问题 - 二十三岁的有德 - 博客园 (cnblogs.com)



这篇关于半正定规划(SDP)例:最小化矩阵范数(2-norm of a matrix)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程