5.3.1. 二次规划建模¶
二次规划问题可以用以下数学形式表示:
\[\begin{split}\min \quad&-c^f + c^Tx + \frac{1}{2}x^T Q x \\
\mbox{s.t.} \quad&l^r \leq Ax \leq u^r, \\
& l^c \leq x \leq u^c,\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 \in \mathbb{R}^{n\times n}\) 是目标函数中二次项的系数,
\(A \in \mathbb{R}^{m \times n}\) 是约束矩阵,
\(l^r \in \mathbb{R}^{m}\) 和 \(u^r \in \mathbb{R}^{m}\) 分别为是约束的下界和上界。
使用 MindOpt 的步骤为:
创建优化模型;
输入优化问题并设置算法参数;
求解优化问题并获取解。
Note
MindOpt 仅存储中的约束矩阵 \(A\) 和二次矩阵 \(Q\) 中的 非零元;因此,使用时只需要输入 非零元 在约束矩阵中的 行列位置 (row/column index) 以及对应的 非零数值 (nonzero value)。
5.3.1.1. 二次规划问题示例¶
在下文中,我们将考虑下列二次规划问题:
\[\begin{split}\begin{matrix} \min & & 1 x_0 & + & 1 x_1 & + & 1 x_2 & + & 1 x_3 \\
& + 1/2 [ & x_0^2 & + & x_1^2 & + & x_2^2 & + & x_3^2 & + & x_0 x_1 & ] \\
\mbox{s.t.} & & 1 x_0 & + & 1 x_1 & + & 2 x_2 & + & 3 x_3 & \geq & 1 \\
& & 1 x_0 & & & - & 1 x_2 & + & 6 x_3 & = & 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 建模和求解这个优化问题。二次规划与线性规划的区别在于二次项矩阵的输入。对于线性约束的建模,依然可以通过以下两种形式来输入矩阵中的非零元:
按 行(约束) 排列;
按 列(变量) 排列。
具体可以参考 线性规划建模。对于二次项系数矩阵 \(Q\),为了保证对称性,用户只需输入其下三角的部分,并且在求解器内部会乘以 1/2.
接下来,我们将针对不同语言分别给出示例。