混合整数二次规划

混合整数二次规划（MIQP）是一个形式为

\[\begin{split}\begin{array}{ll} \mbox{最小化} & x^T Q x + q^T x + r \\ \mbox{约束条件} & x \in \mathcal{C}\\ & x \in \mathbf{Z}^n, \end{array}\end{split}\]

的优化问题，其中 \(x \in \mathbf{Z}^n\) 是优化变量 (\(\mathbf Z^n\) 是具有整数值分量的 \(n\) 维向量集合)， \(Q \in \mathbf{S}_+^n\) （由 \(n \times n\) 对称正半定矩阵组成）， \(q \in \mathbf{R}^n\) 和 \(r \in \mathbf{R}\) 是问题数据， \(\mathcal C\) 是某个凸集。

混合整数最小二乘是 MIQP 的一个例子，它的形式为

\[\begin{split}\begin{array}{ll} \mbox{最小化} & \|Ax-b\|_2^2 \\ \mbox{约束条件} & x \in \mathbf{Z}^n, \end{array}\end{split}\]

其中 \(x \in \mathbf{Z}^n\) 是优化变量， \(A \in \mathbf{R}^{m \times n}\) 和 \(b \in \mathbf{R}^{m}\) 是问题数据。该问题的解 \(x^{\star}\) 是一个在 \(\mathbf Z^n\) 中将 \(\|Ax-b\|_2^2\) 最小化的向量。

例子

在下面的代码中，我们使用CVXPY解决了一个混合整数最小二乘问题。 在运行此示例之前，您需要安装一个混合整数非线性求解器。 CVXPY首选的开源混合整数非线性求解器是SCIP。 可以使用``pip install pyscipopt``或``conda install -c conda-forge pyscipopt``进行安装。

import cvxpy as cp
import numpy as np

# 生成一个随机问题
np.random.seed(0)
m, n= 40, 25

A = np.random.rand(m, n)
b = np.random.randn(m)

# 构造一个CVXPY问题
x = cp.Variable(n, integer=True)
objective = cp.Minimize(cp.sum_squares(A @ x - b))
prob = cp.Problem(objective)
prob.solve()

13.66000322824753

print("状态: ", prob.status)
print("最优值为", prob.value)
print("一个解 x 是")
print(x.value)

状态:  最优
最优值为 13.66000322824753
一个解 x 是
[-1.  1.  1. -1.  0.  0. -1. -2.  0.  0.  0.  1.  1.  0.  1.  0. -1. -1.
 -1.  0.  2. -1.  2.  0. -1.]