二次规划问题

二次规划问题是一个具有二次目标函数和仿射等式和不等式约束的优化问题。一种常见的标准形式如下：

\[\begin{split}\begin{array}{ll} \mbox{minimize} & (1/2)x^TPx + q^Tx\\ \mbox{subject to} & Gx \leq h \\ & Ax = b. \end{array}\end{split}\]

这里 \(P \in \mathcal{S}^{n}_+\), \(q \in \mathcal{R}^n\), \(G \in \mathcal{R}^{m \times n}\), \(h \in \mathcal{R}^m\), \(A \in \mathcal{R}^{p \times n}\), 和 \(b \in \mathcal{R}^p\) 是问题的数据，而 \(x \in \mathcal{R}^{n}\) 是优化变量。不等式约束 \(Gx \leq h\) 是逐元素定义的。

一个简单的二次规划问题的例子在金融领域中出现。假设我们有 \(n\) 支不同的股票，每支股票的预期收益的估计值为 \(r \in \mathcal{R}^n\)，并且收益的协方差的估计值为 \(\Sigma \in \mathcal{S}^{n}_+\)。然后我们求解以下优化问题

\[\begin{split}\begin{array}{ll} \mbox{minimize} & (1/2)x^T\Sigma x - r^Tx\\ \mbox{subject to} & x \geq 0 \\ & \mathbf{1}^Tx = 1, \end{array}\end{split}\]

以找到最佳平衡预期收益和收益方差的投资组合分配 \(x \in \mathcal{R}^n_+\)。

当我们求解二次规划问题时，除了得到一个解 \(x^\star\) 之外，我们还会得到对应于不等式约束的对偶解 \(\lambda^\star\)。正的 \(\lambda^\star_i\) 表示约束 \(g_i^Tx \leq h_i\) 在 \(x^\star\) 处以等式成立，并且表明改变 \(h_i\) 会改变最优值。

示例

在下面的代码中，我们使用CVXPY解决一个二次规划问题。

# 导入包。
import cvxpy as cp
import numpy as np

# 生成一个随机非平凡二次规划问题。
m = 15
n = 10
p = 5
np.random.seed(1)
P = np.random.randn(n, n)
P = P.T @ P
q = np.random.randn(n)
G = np.random.randn(m, n)
h = G @ np.random.randn(n)
A = np.random.randn(p, n)
b = np.random.randn(p)

# 定义并解决CVXPY问题。
x = cp.Variable(n)
prob = cp.Problem(cp.Minimize((1/2)*cp.quad_form(x, P) + q.T @ x),
                 [G @ x <= h,
                  A @ x == b])
prob.solve()

# 打印结果。
print("\n最优值为", prob.value)
print("一个解x是")
print(x.value)
print("对应于不等式约束条件的对偶解是")
print(prob.constraints[0].dual_value)

最优值为 86.89141585569918
一个解x是
[-1.68244521  0.29769913 -2.38772183 -2.79986015  1.18270433 -0.20911897
 -4.50993526  3.76683701 -0.45770675 -3.78589638]
对应于不等式约束条件的对偶解是
[ 0.          0.          0.          0.          0.         10.45538054
  0.          0.          0.         39.67365045  0.          0.
  0.         20.79927156  6.54115873]