半正定规划（SDP）例：最小化矩阵范数（2-norm of a matrix）

正所谓我不能直接搜到答案就得让以后的小朋友能直接搜到答案。主要是不小心通了个宵，乱吃了好些很不健康还大概确乎过期了的东西，刚刚还喝了口过期牛奶（很绝），脑子不大清醒，不想搞作业，反正也不会还搞不完。正所谓作业写不完，习学不完的时候就爱干些其他的，比如写几句。

半正定规划(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}$$

欢迎指正，但我都已经交了。

参考

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

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

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