半定规划

半定规划（SDP）是一个形式如下的最优化问题：

\[\begin{split}\begin{array}{ll} \mbox{minimize} & \mathbf{tr}(CX) \\ \mbox{subject to} & \mathbf{tr}(A_iX) = b_i, \quad i=1,\ldots,p \\ & X \succeq 0, \end{array}\end{split}\]

其中 \(\mathbf{tr}\) 是迹函数, \(X \in \mathcal{S}^{n}\) 是优化变量， \(C, A_1, \ldots, A_p \in \mathcal{S}^{n}\), 以及 \(b_1, \ldots, b_p \in \mathcal{R}\) 是问题的数据, \(X \succeq 0\) 是一个矩阵不等式。

在这里，\(\mathcal{S}^{n}\) 表示 \(n\)-by-\(n\) 对称矩阵的集合。

一个SDP的例子是用缺失条目 \(M \subset \{1,\ldots,n\} \times \{1,\ldots,n\}\) 完成 \(\tilde \Sigma \in \mathcal{S}^{n}_+\) 的协方差矩阵：

\[\begin{split}\begin{array}{ll} \mbox{minimize} & 0 \\ \mbox{subject to} & \Sigma_{ij} = \tilde \Sigma_{ij}, \quad (i,j) \notin M \\ & \Sigma \succeq 0, \end{array}\end{split}\]

例子

在接下来的代码中，我们使用CVXPY解决一个SDP问题。

# Import packages.
import cvxpy as cp
import numpy as np

# 生成一个随机SDP。
n = 3
p = 3
np.random.seed(1)
C = np.random.randn(n, n)
A = []
b = []
for i in range(p):
    A.append(np.random.randn(n, n))
    b.append(np.random.randn())

# 定义并解决CVXPY问题。
# 创建一个对称矩阵变量。
X = cp.Variable((n,n), symmetric=True)
# 运算符 >> 表示矩阵不等式。
constraints = [X >> 0]
constraints += [
    cp.trace(A[i] @ X) == b[i] for i in range(p)
]
prob = cp.Problem(cp.Minimize(cp.trace(C @ X)),
                  constraints)
prob.solve()

# 打印结果。
print("最优值为", prob.value)
print("一个解 X 为")
print(X.value)

最优值为 2.654348003008652
一个解 X 为
[[ 1.6080571  -0.59770202 -0.69575904]
 [-0.59770202  0.22228637  0.24689205]
 [-0.69575904  0.24689205  1.39679396]]