如何将点集与分隔线转化为Python可解的线性规划（Marriage before conquest算法）

我们可以将问题完全转化为线性规划形式，适配scipy.optimize.linprog的求解要求，核心是明确决策变量、目标函数与约束条件的对应关系：

1. 定义决策变量 #

我们的优化变量是直线y = ax + b的两个参数：

• 斜率a
• 截距b

2. 目标函数转化 #

需要最小化直线与分隔线交点的y值y_m = a*x_m + b（其中x_m是分隔线的x坐标，为已知常量）。将其写成线性规划标准最小化形式：

最小化：f(a, b) = x_m * a + 1 * b
对应linprog的参数c = [x_m, 1]

3. 约束条件转化 #

所有点(x_i, y_i)必须在直线下方或在直线上，即y_i <= a*x_i + b。将其整理为linprog要求的**不等式约束（A_ub @ x <= b_ub）**形式：
对每个点移项得：-x_i * a - 1 * b <= -y_i

• 构造矩阵A_ub：每行对应一个点，元素为[-x_i, -1]
• 构造向量b_ub：每个元素为-y_i

4. 变量边界设置 #

斜率a和截距b无上下限限制，因此设置bounds = [(-np.inf, np.inf), (-np.inf, np.inf)]

5. 代码实现示例 #

import numpy as np
from scipy.optimize import linprog

# 示例输入：点集与分隔线x坐标
points = np.array([[1, 2], [3, 1], [5, 3], [2, 4]])
x_m = 3  # 分隔线的x值

# 构建线性规划参数
c = [x_m, 1]  # 目标函数系数：x_m*a + 1*b
A_ub = np.column_stack((-points[:, 0], -np.ones(len(points))))  # 每行对应[-x_i, -1]
b_ub = -points[:, 1]  # 每个元素对应-y_i
bounds = [(-np.inf, np.inf), (-np.inf, np.inf)]

# 求解线性规划
result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

if result.success:
    a_opt, b_opt = result.x
    y_m_opt = x_m * a_opt + b_opt
    print(f"最优直线：y = {a_opt:.4f}x + {b_opt:.4f}")
    print(f"与分隔线交点y值：{y_m_opt:.4f}")
else:
    print("求解失败：", result.message)

对偶性原理的辅助理解 #

你提到的对偶性在这里对应：原问题中每个点的约束对应对偶问题的一个变量，本质上我们是在寻找点集凸包的上边界支撑线——这恰好匹配Marriage before conquest算法中"桥"的定义：两个点集之间最低的上支撑线。

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