半正定规划(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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南