二阶锥规划

二阶锥规划（SOCP）是一个形如下式的优化问题：

\[\begin{split}\begin{array}{ll} \mbox{minimize} & f^Tx\\ \mbox{subject to} & \|A_ix + b_i\|_2 \leq c_i^Tx + d_i, \quad i=1,\ldots,m \\ & Fx = g, \end{array}\end{split}\]

其中 \(x \in \mathcal{R}^{n}\) 是优化变量， \(f \in \mathcal{R}^n\), \(A_i \in \mathcal{R}^{n_i \times n}\), \(b_i \in \mathcal{R}^{n_i}\), \(c_i \in \mathcal{R}^n\), \(d_i \in \mathcal{R}\), \(F \in \mathcal{R}^{p \times n}\), 并且 \(g \in \mathcal{R}^p\) 是问题数据。

SOCP 的一个例子是稳健线性规划问题

\[\begin{split}\begin{array}{ll} \mbox{minimize} & c^Tx\\ \mbox{subject to} & (a_i + u_i)^Tx \leq b_i \textrm{ for all } \|u_i\|_2 \leq 1, \quad i=1,\ldots,m, \end{array}\end{split}\]

其中问题数据 \(a_i\) 在半径为一的 \(\ell_2\)-范数球内已知。稳健线性规划问题可以 重写为 SOCP 的形式

mbox{最小化} & c^Tx\ mbox{限制} & a_i^Tx + |x|_2 leq b_i, quad i=1,ldots,m, end{array}

当我们求解SOCP时，除了得到一个解 \(x^\star\)，我们还得到了与每一个二阶锥约束对应的对偶解 \(\lambda_i^\star\)。非零的 \(\lambda_i^\star\) 表示约束 \(\|A_ix + b_i\|_2 \leq c_i^Tx + d_i\) 在 \(x^\star\) 处成立，并且建议改变 \(d_i\) 会改变最优值。

示例

在下面的代码中，我们使用CVXPY求解一个SOCP。

# 引入库。
import cvxpy as cp
import numpy as np

# 生成一个随机可行的SOCP。
m = 3
n = 10
p = 5
n_i = 5
np.random.seed(2)
f = np.random.randn(n)
A = []
b = []
c = []
d = []
x0 = np.random.randn(n)
for i in range(m):
    A.append(np.random.randn(n_i, n))
    b.append(np.random.randn(n_i))
    c.append(np.random.randn(n))
    d.append(np.linalg.norm(A[i] @ x0 + b, 2) - c[i].T @ x0)
F = np.random.randn(p, n)
g = F @ x0

# 定义并求解CVXPY问题。
x = cp.Variable(n)
# 我们使用 cp.SOC(t, x) 来创建约束 ||x||_2 <= t 的二阶锥约束。
soc_constraints = [
      cp.SOC(c[i].T @ x + d[i], A[i] @ x + b[i]) for i in range(m)
]
prob = cp.Problem(cp.Minimize(f.T@x),
                  soc_constraints + [F @ x == g])
prob.solve()

# 打印结果。
print("最优值为", prob.value)
print("一个解 x 为")
print(x.value)
for i in range(m):
    print("SOC 约束 %i 对偶变量的解" % i)
    print(soc_constraints[i].dual_value)

最优值为 -9.582695716265503
一个解 x 为
[ 1.40303325  2.4194569   1.69146656 -0.26922215  1.30825472 -0.70834842
  0.19313706  1.64153496  0.47698583  0.66581033]
SOC 约束 0 对偶变量的解
[ 0.61662526  0.35370661 -0.02327185  0.04253095  0.06243588  0.49886837]
SOC 约束 1 对偶变量的解
[ 0.35283078 -0.14301082  0.16539699 -0.22027817  0.15440264  0.06571645]
SOC 约束 2 对偶变量的解
[ 0.86510445 -0.114638   -0.449291    0.37810251 -0.6144058  -0.11377797]