为何Scipy.optimize.linprog未找到线性规划问题的最优解？

你遇到的问题完全是因为线性规划的约束条件构造错误，导致linprog求解的是一个和你目标无关的问题，自然得不到正确结果。

正确的约束推导 #

你的目标是找到仿射空间v+span(W)中无穷范数最小的点，等价于求解：
$$\min_{x,t} \quad t$$
$$\text{s.t.} \quad -t \leq v_i + (Wx)_i \leq t \quad \forall i$$

将不等式拆分为两组：

1. 上界约束：$v_i + (Wx)_i \leq t$ → 整理为 $Wx - t \leq -v$
2. 下界约束：$-(v_i + (Wx)_i) \leq t$ → 整理为 $-Wx - t \leq v$

你的约束构造错误 #

你当前代码中构造的约束是：
$$-t - Wx \leq v \quad \text{和} \quad -t + Wx \leq -v$$
这和正确约束完全颠倒，导致linprog求解的是一个错误的优化问题，结果自然不符合预期。

修正后的代码 #

替换原代码中约束构造的部分，改为正确的形式：

def random_orthonormal_basis(n):
    random_matrix = np.random.normal(size=(n, n))
    q, _ = np.linalg.qr(random_matrix)
    return q

def affine_max_norm_min(dim_space, dim_subspace):
    U = random_orthonormal_basis(dim_space)
    v = U[:,0]
    W = U[:,1:dim_subspace+1]

    # 正确构造线性规划约束
    from scipy.optimize import linprog
    c = np.zeros(dim_subspace + 1)
    c[0] = 1  # 目标是最小化t（第一个变量）
    
    # 第一组约束：Wx - t ≤ -v
    constraint1 = np.hstack([-np.ones((dim_space, 1)), W])
    b1 = -v
    # 第二组约束：-Wx - t ≤ v
    constraint2 = np.hstack([-np.ones((dim_space, 1)), -W])
    b2 = v
    
    A_ub = np.vstack([constraint1, constraint2])
    b_ub = np.hstack([b1, b2])

    res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=None)

    # 手动构造的可行点验证
    k = np.linalg.norm(v)**2 / np.linalg.norm(v, ord=1)
    hand_vec = k * np.sign(v)
    hand_x = np.linalg.lstsq(W, hand_vec-v, rcond=None)[0]
    hand_x_withone = np.concatenate((np.array([k+1e-8]), hand_x), axis=0)

    print("手动构造点是否可行：", np.all(np.dot(A_ub, hand_x_withone) <= b_ub + 1e-6))  # 加容差避免浮点误差
    print("手动构造点的目标值：", np.dot(c, hand_x_withone))
    print("linprog求解的最优目标值：", res.fun)

    return res.fun

affine_max_norm_min(10,9)

修正后，linprog求解的结果会和手动构造的可行点目标值一致（或更优，因为手动构造的点只是可行点而非必然最优）。

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