5.4.1. 二次约束规划建模
二次约束规划(Quadratically Constrained Programming, QCP)问题可以用以下数学形式表示:
\[\begin{split}\begin{matrix} \min & & x^T Q_0 x &+& c^Tx &-& c^f \\
\mbox{s.t.} & & x^T Q_i x &+& a_i^\top x & \leq & u_i^r, & \quad i = 1, 2, \cdots, m \\
& & l^c &\leq& x &\leq& u^c,
\end{matrix}\end{split}\]
- 其中
\(x \in \mathbb{R}^{n}\) 是决策变量,
\(l^c \in \mathbb{R}^{n}\) 和 \(u^c \in \mathbb{R}^{n}\) 分别为 \(x\) 的下界和上界,
\(c^f \in \mathbb{R}\) 是目标函数中的常量,
\(c \in \mathbb{R}^{n}\) 是目标函数中线性项的系数向量,
\(Q_0 \in \mathbb{R}^{n\times n}\) 是目标函数中二次项的系数矩阵,
\(\{a_i \in \mathbb{R}^{n}\mid i=1,2,\cdots,m\}\) 是约束中线性项的系数向量,
\(\{Q_i \in \mathbb{R}^{n\times n}\mid i=1,2,\cdots,m\}\) 是约束中二次项的系数矩阵,
\(u^r \in \mathbb{R}^{m}\) 分别为是约束的上界。
备注
目前 MindOpt 支持求解凸二次约束规划,因此要求目标函数中的二次项系数 \(Q_0\) 与约束中的二次项系数 \(\{Q_i \mid i=1,2,\cdots,m\}\) 均为 半正定矩阵 。当用户以 \(\geq\) 的形式输入二次约束时,则要求对应二次项系数为 半负定矩阵 。
使用 MindOpt 的步骤为:
创建优化模型;
输入优化问题并设置算法参数;
求解优化问题并获取解。
备注
MindOpt 仅存储中的问题系数中的 非零元;因此,使用时只需要输入 非零元 在约束矩阵中的 行列位置 (row/column index) 以及对应的 非零数值 (nonzero value)。
5.4.1.1. 二次约束规划问题示例
在下文中,我们将考虑下列二次约束规划问题:
\[\begin{split}\begin{matrix} \min & & 1 x_0 & + & 1 x_1 & + & 1 x_2 & + & 1 x_3 \\
& + & \frac{1}{2}x_0^2 & + & \frac{1}{2}x_1^2 & + & \frac{1}{2} x_2^2 & + & \frac{1}{2} x_3^2 & + & \frac{1}{2} x_0 x_1 \\
\mbox{s.t.} & & 1 x_0 & + & 1 x_1 & + & 2 x_2 & + & 3 x_3 \\
& - & \frac{1}{2}x_0^2 & - & \frac{1}{2}x_1^2 & - & \frac{1}{2} x_2^2 & - & \frac{1}{2} x_3^2 & - & \frac{1}{2} x_0 x_1 & \geq & 1 \\
& & 1 x_0 & & & - & 1 x_2 & + & 6 x_3
& + & \frac{1}{2} x_1^2 & \leq & 1
\end{matrix}\end{split}\]
\[\begin{split}\begin{matrix} 0 & \leq & x_0 & \leq & 10 \\
0 & \leq & x_1 & \leq & \infty \\
0 & \leq & x_2 & \leq & \infty \\
0 & \leq & x_3 & \leq & \infty
\end{matrix}\end{split}\]
我们将展示如何使用不同编程语言调用 MindOpt 建模和求解这个优化问题。