对于一个由一堆线性不等式定义的凸区域，如何识别并删除无效线性不等式超平面约束？

Question

对于一个由一堆线性不等式定义的凸区域，如何识别并删除无效线性不等式超平面约束？

Answer 1

本答案参考 多次询问 ChatGPT-3.5 后选择的最佳回答，若是满意，还请采纳，谢谢

以下是识别并删除无效线性不等式超平面约束的一般方法：

一、基本概念

1. 凸区域
   • 凸区域是指对于区域内的任意两点，连接这两点的线段完全包含在该区域内的区域。在由线性不等式定义的凸区域中，每个线性不等式都对应一个超平面，超平面将空间划分为两个半空间，而线性不等式所定义的凸区域是这些半空间的交集。
2. 线性不等式超平面约束
   • 对于线性不等式$ ax + by+cz+\cdots\leqslant d $（在高维空间中，$ x,y,z,\cdots $是变量，$ a,b,c,\cdots $是系数），它定义了一个超平面$ ax + by + cz+\cdots=d $，这个超平面及其一侧的半空间构成了一个约束条件。

二、识别和删除无效约束的方法

（一）顶点检查法

1. 计算凸区域的顶点
   • 可以通过求解线性规划问题的顶点来得到凸区域的顶点。对于由$ n $个线性不等式$ A_i x\leqslant b_i $，$ i = 1,\cdots,n $定义的凸区域（其中$ x=(x_1,\cdots,x_m)^T $，$ A_i $是$ 1\times m $的系数矩阵，$ b_i $是标量），我们可以通过将$ n $个不等式中的$ m $个不等式取等号（这$ m $个不等式对应的超平面相交得到一个顶点），然后求解得到的线性方程组来找到顶点。
   • 例如，在二维空间中，由$ a_1x + b_1y\leqslant c_1 $，$ a_2x + b_2y\leqslant c_2 $，$ a_3x + b_3y\leqslant c_3 $定义的凸区域。我们可以通过联立$ \begin{cases}a_1x + b_1y = c_1\a_2x + b_2y = c_2\end{cases} $求解得到一个顶点（假设这个方程组有解）。
2. 检查顶点是否满足不等式
   • 对于每个顶点$ v $，将其代入到每个线性不等式$ A_i x\leqslant b_i $中进行检查。如果对于某个不等式$ A_j v\leqslant b_j $，在所有顶点处都严格成立（即$ A_j v < b_j $），那么这个不等式$ A_j x\leqslant b_j $可能是无效约束。
   • 例如，在二维凸多边形中，如果一个顶点$ (x_0,y_0) $满足$ a_1x_0 + b_1y_0 < c_1 $，$ a_2x_0 + b_2y_0 < c_2 $，$ \cdots $，$ a_nx_0 + b_ny_0 < c_n $，且对于所有顶点都有这种情况，那么$ a_1x + b_1y\leqslant c_1 $这个约束可能是无效的，可以考虑删除。

（二）冗余检查法

1. 两两比较不等式
   • 对于两个线性不等式$ A_1x\leqslant b_1 $和$ A_2x\leqslant b_2 $，如果由$ A_1x\leqslant b_1 $定义的半空间完全包含由$ A_2x\leqslant b_2 $定义的半空间，那么$ A_2x\leqslant b_2 $是冗余的（即无效约束）。
   • 在二维空间中，例如$ x + y\leqslant 1 $和$ 2x+2y\leqslant 2 $，第二个不等式所定义的半空间完全包含在第一个不等式所定义的半空间内，所以$ 2x + 2y\leqslant 2 $是冗余的。
   • 可以通过检查系数之间的比例关系来初步判断。如果存在$ \lambda>0 $，使得$ A_2=\lambda A_1 $且$ b_2=\lambda b_1 $，那么$ A_2x\leqslant b_2 $是冗余的。
2. 多不等式比较（更复杂的情况）
   • 对于多个不等式，可以构建一个不等式组的层次结构。如果一个不等式所定义的半空间可以由其他几个不等式所定义的半空间的交集得到，那么这个不等式是冗余的。
   • 例如，在三维空间中，由$ x\leqslant1 $，$ y\leqslant1 $，$ z\leqslant1 $和$ x + y+z\leqslant3 $定义的凸区域，$ x + y+z\leqslant3 $这个约束可能是冗余的，可以通过分析顶点或者更复杂的线性代数方法来确定。