基于Python精确线性规划检测点集线性可分性的数值问题

安全阿岳

2026-5-27

解决线性规划判断线性可分性的数值稳定性问题

我之前也碰到过一模一样的状况——用线性规划验证两类点集的线性可分性，理论上逻辑完全通顺，但一旦点集出现近共线、点间距极小的情况，scipy.optimize.linprog就容易出各种数值问题：比如收敛失败、结果偏离预期，甚至直接返回无解，但明明理论上是可分的。

先拆解问题根源

这类数值坑主要来自两个核心原因：

数值病态性：当点接近共线时，约束条件的系数矩阵会变得接近奇异，求解器在计算过程中会出现严重的精度损失，导致结果不可靠；
硬约束的精度冲突：点间距过近时，原本要求严格满足的分隔约束（比如正类点满足w·x_i + b ≥ 1，负类点满足w·x_j + b ≤ -1）会因为浮点精度的限制变得难以满足，求解器很容易陷入无解或错误解的死胡同。

针对scipy linprog的实用优化方案

结合你提到的「生成点云、随机直线划分子集」的场景，给你几个可落地的调整方向：

1. 先给数据做预处理

标准化/归一化：把所有点的坐标缩放到同一尺度（比如用均值为0、方差为1的标准化，或者映射到[0,1]区间），能大幅减少因坐标量级差异导致的数值不平衡，避免求解器被大尺度变量带偏。
示例代码片段：
```
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
normalized_locations = scaler.fit_transform(locations)
```
添加微小扰动：如果点确实接近共线，可以给每个点的坐标加上1e-6量级的随机噪声，既能打破共线性，又不会改变原有的可分性（只要噪声足够小）。

2. 调整linprog的求解参数

scipy.linprog的几个参数 tweak 后能显著提升数值稳定性：

选更鲁棒的求解器：优先用solver='highs'（scipy 1.6+的默认求解器，比旧版simplex稳定得多），复杂场景可以试试solver='highs-ds'或'highs-ipm'；
调整收敛容差：把tol从默认的1e-9放宽到1e-6，避免求解器因为微小的数值误差直接判定不收敛；
启用预处理：设置options={'presolve': True}，让求解器自动预处理约束条件，简化问题结构。

示例调用：

from scipy.optimize import linprog

# 假设c是目标函数系数，A_ub、b_ub是约束条件
result = linprog(c, A_ub=A_ub, b_ub=b_ub, 
                 solver='highs', 
                 tol=1e-6,
                 options={'presolve': True})

3. 重构线性规划的约束形式

传统的硬约束LP模型对数值误差太敏感，你可以改成带松弛变量的软约束形式——这其实就是支持向量机（SVM）的原始问题，鲁棒性强很多：

给每个点引入松弛变量ξ_i ≥ 0，约束调整为：正类点满足w·x_i + b ≥ 1 - ξ_i，负类点满足w·x_j + b ≤ -1 + ξ_j；
目标函数改为minimize ||w|| + C * sum(ξ_i)，其中C是惩罚系数，控制对松弛的容忍程度（C越大越严格，越小越能接受微小的约束违反）。

结合你的点云生成场景的额外建议

在你生成点云并随机直线划分子集的环节，可以提前做两步检查：

生成子集后，先计算两类点的最小间距，如果间距小于1e-5这类阈值，直接跳过这个子集或者调整直线参数，从源头上避免后续LP求解的数值问题；
对于近共线的点集，先做PCA降维，看看在低维空间中是否更容易处理，或者直接判断这类点集是否本质上就是线性不可分（如果点几乎完全重叠的话）。

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