线性规划最优分隔线求解疑问：新增变量的使用方法困惑

核心变量定义 #

• 直线参数：w₁, w₂, b（待求解的分隔线参数，对应直线方程 w₁x + w₂y + b = 0）
• 0-1分类标记变量：对每个样本点 (xᵢ, yᵢ)，定义 zᵢ ∈ {0,1}：
  • zᵢ=0：该点被正确分类
  • zᵢ=1：该点被错分
• 松弛变量：sᵢ ≥ 0，用于放宽错分点的约束条件

约束条件设定 #

假设两组点分别为正类（需要落在直线一侧）和负类（落在另一侧）：

• 正类点约束：w₁xᵢ + w₂yᵢ + b ≥ 1 - M*zᵢ
• 负类点约束：w₁xᵢ + w₂yᵢ + b ≤ -1 + M*zᵢ

其中M是一个足够大的正数（需大于所有点代入直线方程后的最大绝对值），作用是：

• 当zᵢ=0（正确分类），约束退化为硬间隔要求：正类点满足w₁xᵢ + w₂yᵢ + b ≥1，负类点满足w₁xᵢ + w₂yᵢ + b ≤-1，保证点在分隔线的正确侧且有最小间隔
• 当zᵢ=1（错分），M*zᵢ会让约束完全松弛，允许点落在对侧

目标函数 #

我们的核心目标是最小化错分点的总数，因此目标函数为：

minimize Σ(zᵢ) （对所有样本点的zᵢ求和）

关键注意点 #

• M的取值要合理：足够大以确保错分点的约束能被松弛，但不能过大引发数值计算不稳定
• 这是0-1整数线性规划问题，需要用支持整数变量的求解器（如Gurobi、CPLEX，或开源的PuLP搭配CBC求解器）
• 如果不想用整数规划，软间隔SVM可作为近似方案，但软间隔最小化的是错分的“程度”（松弛变量之和），而非错分点的数量，结果可能存在差异

内容的提问来源于stack exchange，提问作者Malte