什么是凸二次规划问题
我们从凸二次规划的基本概念出发，然后解释它与支持向量机的关系。
一、凸二次规划问题的详细介绍
凸二次规划问题是优化问题的一类，目标是最小化一个凸的二次函数，受一组线性约束的限制。凸二次规划是一类特殊的二次规划问题，其中目标函数是凸的。凸函数意味着在函数的任何两点之间，函数的值总是在这两点连接的线段之下，这保证了有唯一的全局最优解。
凸二次规划问题的通用形式
min 1 2 x T Q x + c T x \min \quad \frac{1}{2} \mathbf{x}^T Q \mathbf{x} + \mathbf{c}^T \mathbf{x} min21xTQx+cTx
其中：
- x \mathbf{x} x 是决策变量向量，需要优化的目标。
- Q Q Q 是对称的正定矩阵，定义了二次项。如果 Q Q Q 是正定的（即 y T Q y > 0 \mathbf{y}^T Q \mathbf{y} > 0 yTQy>0 对于任何 y ≠ 0 \mathbf{y} \neq 0 y=0），则优化问题是凸的。
- c \mathbf{c} c 是线性项的系数向量。
目标是最小化上述二次函数。
线性约束
除了目标函数外，凸二次规划问题还受到一些线性约束的限制。约束条件通常可以有两类：
-
不等式约束：
A x ≤ b A \mathbf{x} \leq \mathbf{b} Ax≤b其中 A A A 是矩阵， b \mathbf{b} b 是约束向量，约束条件要求某些线性组合不能超过某个值。
-
等式约束：
E x = d E \mathbf{x} = \mathbf{d} Ex=d其中 E E E 是矩阵， d \mathbf{d} d 是约束向量，表示某些线性组合必须等于某个值。
解决凸二次规划问题的目标是找到最优的 x \mathbf{x} x，使得目标函数值最小化，并满足这些约束条件。
二、凸二次规划在支持向量机中的应用
SVM 中的目标：最大化间隔
支持向量机的核心思想是找到一个最佳的分类超平面，使得不同类别的数据点被最大间隔地分开。我们希望找到这样的超平面：
w
T
x
+
b
=
0
\mathbf{w}^T \mathbf{x} + b = 0
wTx+b=0
其中 w \mathbf{w} w 是法向量， b b b 是偏置项。
在SVM中，我们要最大化分类间隔，即最小化超平面法向量 w \mathbf{w} w 的范数 ∥ w ∥ 2 \|\mathbf{w}\|^2 ∥w∥2。这个过程可以转化为一个优化问题。
软间隔支持向量机的目标函数
在软间隔 SVM 中，我们允许一些数据点有一定的误分类，但同时我们会引入“松弛变量”
ξ
i
\xi_i
ξi 来表示每个样本的误分类程度。目标函数变成了：
min
1
2
∥
w
∥
2
+
C
∑
i
=
1
n
ξ
i
\min \quad \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^{n} \xi_i
min21∥w∥2+Ci=1∑nξi
其中：
- 第一项 1 2 ∥ w ∥ 2 \frac{1}{2} \|\mathbf{w}\|^2 21∥w∥2 是希望最小化法向量的长度，从而最大化分类的间隔。
- 第二项 C ∑ i = 1 n ξ i C \sum_{i=1}^{n} \xi_i C∑i=1nξi 是用于控制误分类点的惩罚。 C C C 是一个正则化参数，平衡间隔最大化和误分类惩罚之间的权重。
约束条件
SVM 的分类结果还必须满足线性可分性约束（允许误差的情况下是软约束）：
y
i
(
w
T
x
i
+
b
)
≥
1
−
ξ
i
,
∀
i
=
1
,
2
,
…
,
n
y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i, \quad \forall i = 1, 2, \ldots, n
yi(wTxi+b)≥1−ξi,∀i=1,2,…,n
ξ i ≥ 0 , ∀ i \xi_i \geq 0, \quad \forall i ξi≥0,∀i
这意味着每个数据点 x i \mathbf{x}_i xi 的分类结果要满足其真实类别标签 y i y_i yi （为1或-1）所期望的约束，允许误差由 ξ i \xi_i ξi 控制。
二次规划形式
现在，我们可以看到 SVM 的优化问题已经转化为一个标准的凸二次规划问题：
min
1
2
w
T
w
+
C
∑
i
=
1
n
ξ
i
\min \quad \frac{1}{2} \mathbf{w}^T \mathbf{w} + C \sum_{i=1}^{n} \xi_i
min21wTw+Ci=1∑nξi
subject to y i ( w T x i + b ) ≥ 1 − ξ i \text{subject to} \quad y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i subject toyi(wTxi+b)≥1−ξi
ξ i ≥ 0 , ∀ i \xi_i \geq 0, \quad \forall i ξi≥0,∀i
这里，目标函数有一个凸的二次项（ 1 2 w T w \frac{1}{2} \mathbf{w}^T \mathbf{w} 21wTw ），同时伴随着一组线性约束，因此这是一个典型的凸二次规划问题。
三、求解凸二次规划问题
求解凸二次规划问题可以使用各种算法，包括：
- 拉格朗日乘子法：用于处理带有约束的优化问题。在 SVM 中，通过引入拉格朗日乘子，我们可以将原问题转化为其对偶问题，通过求解对偶问题来获得最优解。
- 内点法：是一类求解凸规划问题的高效算法。
- 序列最小优化算法（SMO）：专门用于求解 SVM 中的二次规划问题，通过分解问题为多个较小的子问题来逐步优化。
在 SVM 中，拉格朗日对偶形式被广泛使用，它将原始问题的复杂度降低，使得问题可以更高效地求解。
总结
- 凸二次规划问题是指最小化一个二次函数（目标函数是凸的），受一组线性约束限制的优化问题。
- **支持向量机（SVM）**的目标是找到一个最大化分类间隔的超平面，这个问题可以通过凸二次规划的形式来解决。
- 二次项对应于优化超平面法向量的长度，而线性约束则确保数据点的分类结果符合要求。