如何判断3维及更高维中线性不等式组Ax < b是否构成闭合有界区域

核心判断逻辑 #

线性不等式Ax < b对应的可行域是开多面体，其有界性等价于对应的非严格齐次系统Ax ≤ 0不存在非零解。

原理很简单：如果存在非零向量d满足Ad ≤ 0，那么从可行域内任意一点x0出发，沿着d方向延伸的所有点x = x0 + t*d (t≥0)都会满足Ax = Ax0 + t*Ad < b + 0 = b，意味着可行域会沿d方向无限延伸，属于无界区域。
你提到的闭合性要求可以直接通过非严格不等式的计算覆盖，严格不等式的有界性和对应非严格不等式的有界性完全一致，不需要额外处理严格不等的约束。

Python 实现 #

基于scipy的线性规划模块实现，思路是遍历每个维度的正负方向做极值求解，只要有一个方向无界就说明整个可行域无界：

import numpy as np
from scipy.optimize import linprog

def is_polyhedron_bounded(A, b):
    n_dim = A.shape[1]
    # 遍历每个维度分别求最大值、最小值，判断是否有限
    for i in range(n_dim):
        # 最大化第i维分量，linprog默认最小化，所以目标系数取负
        c = np.zeros(n_dim)
        c[i] = -1
        res = linprog(c, A_ub=A, b_ub=b, method='highs')
        # 状态码3代表无界
        if res.status == 3:
            return False
        # 最小化第i维分量
        c[i] = 1
        res = linprog(c, A_ub=A, b_ub=b, method='highs')
        if res.status == 3:
            return False
    return True

你给出的二维示例测试代码：

# 把原始不等式转成Ax <= b的格式：-x1<=0、-x2<=0、x1<=2、x2<=3
A = np.array([[-1, 0], [0, -1], [1, 0], [0, 1]])
b = np.array([0, 0, 2, 3])
print(is_polyhedron_bounded(A, b)) # 输出True

Matlab 实现 #

逻辑和Python版本一致，调用Matlab自带的linprog函数即可：

function bounded = is_polyhedron_bounded(A, b)
    n_dim = size(A, 2);
    bounded = true;
    for i = 1:n_dim
        % 最大化第i维分量
        c = zeros(n_dim, 1);
        c(i) = -1;
        [~, ~, exitflag] = linprog(c, A, b);
        % 退出码-3代表无界
        if exitflag == -3
            bounded = false;
            return
        end
        % 最小化第i维分量
        c(i) = 1;
        [~, ~, exitflag] = linprog(c, A, b);
        if exitflag == -3
            bounded = false;
            return
        end
    end
end

二维示例测试代码：

A = [-1 0; 0 -1; 1 0; 0 1];
b = [0; 0; 2; 3];
is_polyhedron_bounded(A,b) % 输出1

补充说明 #

• 该方法对任意维度的线性不等式系统都适用，仅受线性规划求解器的矩阵规模处理能力限制
• 如果需要先验证可行域非空，可以先求解一次最小化0·x的线性规划，判断是否存在可行解
• 实际使用时如果矩阵规模很大，可以改用更高效的线性规划求解器（比如Gurobi、CPLEX的Python/Matlab接口）替换上述示例中的默认求解器，逻辑不需要改动

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