最优化 | 凸优化 | 二次规划cvxopt求解，如何确定系数？

目录

• 一、定义
• 二、系数的确定
• 三、例子
• 四、代码

一、定义

在凸优化问题中，特别是在二次规划（Quadratic Programming, QP）问题中，矩阵 P P P 通常用来定义目标函数中的二次项。目标函数的形式一般为：

minimize 1 2 x T P x + q T x \text{minimize} \quad \frac{1}{2} x^T P x + q^T x minimize21​xTPx+qTx

其中：

P P P 是一个对称的正定矩阵，它定义了目标函数中的二次项（即 x T P x x^T P x xTPx）。
q q q 是一个向量，定义了目标函数中的线性项（即 q T x q^T x qTx）。

二、系数的确定

如何确定 P P P 矩阵？

1. 确定目标函数的二次项：首先，你需要明确你的目标函数是什么。如果你的目标函数中有二次项，比如 x 1 2 x_1^2 x12​ , x 2 2 x_2^2 x22​, 或 x 1 x 2 x_1 x_2 x1​x2​这样的项，那么这些项的系数将决定 P P P 矩阵中的元素。

2. 构造 P P P 矩阵：
   ① P P P 矩阵的对角线元素通常是目标函数中各个变量的平方项的系数。例如，如果目标函数有项 2 x 1 2 2x_1^2 2x12​，那么 P P P 中相应的对角线元素就是 2。
   ② P P P 矩阵的非对角线元素对应的是变量之间的交叉项的系数。例如，如果目标函数有项 0.5 x 1 x 2 0.5x_1x_2 0.5x1​x2​，那么 P P P 中相应的非对角线元素就是 0.5。
   ③ 由于 P P P 是对称矩阵，矩阵中 P i j = P j i P_{ij} = P_{ji} Pij​=Pji​的关系必须成立。

三、例子

假设你的目标函数是：

f ( x ) = 2 x 1 2 + x 1 x 2 + x 2 2 + x 1 + x 2 f(x) = 2x_1^2 + x_1x_2 + x_2^2 + x_1 + x_2 f(x)=2x12​+x1​x2​+x22​+x1​+x2​

那么，这个目标函数的二次项是 2 x 1 2 2x_1^2 2x12​、 x 1 x 2 x_1x_2 x1​x2​、和 x 2 2 x_2^2 x22​，其系数分别是 2、0.5（因为 x 1 x 2 x_1x_2 x1​x2​ 的系数是 1，但 P P P 是对称矩阵，所以在 P P P 中是 0.5 0.5 0.5）和 1。因此，矩阵 P P P 为：

P = ( 2 0.5 0.5 1 ) P = \begin{pmatrix} 2 & 0.5 \\ 0.5 & 1 \end{pmatrix} P=(20.5​0.51​)

而线性项 q q q 对应的是 x 1 x_1 x1​和 x 2 x_2 x2​前的系数，因此 q = ( 1 1 ) q = \begin{pmatrix} 1 \\ 1 \end{pmatrix} q=(11​)。

四、代码

对应的标准型为：

以cvxopt求解包为例：

from cvxopt import matrix, solvers

P = 2*matrix([[2, .5], [.5, 1]])
q = matrix([1.0, 1.0])
G = matrix([[-1.0,0.0],[0.0,-1.0]])
h = matrix([0.0,0.0])
A = matrix([1.0, 1.0], (1,2))
b = matrix(1.0)

sol=solvers.qp(P, q, G, h, A, b)
print(sol['x'])
print(sol['primal objective'])