求集合$S=\{x:x_1+2x_2\le 4\}$的极点与极方向及相关疑问

你完全没搞错！集合$S={x:x_1+2x_2\le 4}$确实没有极点，你的判断是正确的。下面我详细拆解这个问题的各个部分：

一、为什么S没有极点？ #

先明确极点的核心定义：凸集里的一个点是极点，当且仅当它不能被表示成集合中两个不同点的凸组合（也就是找不到两个不同点$x_1,x_2\in S$和$\lambda\in(0,1)$，使得$x=\lambda x_1+(1-\lambda)x_2$）。

我们分两种情况验证：

• 内部点：随便取一个满足$x_1+2x_2<4$的点$(a,b)$，只要选足够小的$t>0$（比如$t<4-(a+2b)$），就能得到两个点$(a-t,b)$和$(a+t,b)$，这两个点都满足约束条件属于S，而$(a,b)$正好是这两个点的中点（凸组合，$\lambda=0.5$），所以内部点不可能是极点。
• 边界点：再取边界上的点$(a,b)$（满足$a+2b=4$），我们构造两个点：
  $x_1=(a-2t, b+t)$，$x_2=(a+2t, b-t)$（$t>0$）。
  计算约束：$x_1$的$x_1+2x_2=(a-2t)+2(b+t)=a+2b=4\le4$，满足；$x_2$的$x_1+2x_2=(a+2t)+2(b-t)=a+2b=4\le4$，也满足。
  此时$(a,b)=\frac{1}{2}x_1+\frac{1}{2}x_2$，也就是这个边界点是两个不同点的凸组合，所以边界点也不是极点。

综上，S里没有任何点符合极点的定义，确实不存在极点。

二、S的极方向 #

先搞清楚方向的定义：一个非零向量$d$是S的方向，当且仅当对任意$x\in S$，$x+\lambda d\in S$对所有$\lambda\ge0$都成立。

代入S的约束推导：
$$(x_1+\lambda d_1)+2(x_2+\lambda d_2)\le4 \implies \lambda(d_1+2d_2)\le4-(x_1+2x_2)$$
因为$x\in S$，右边是非负的，要让这个不等式对所有$\lambda\ge0$成立，必须满足**$d_1+2d_2\le0$**（否则当$\lambda$足够大时，左边会超过右边）。

接下来找极方向：极方向是S的方向中，不能被表示成S中两个不共线方向的正线性组合的方向。

分析后可知，S的极方向是所有满足**$d_1+2d_2=0$且$d\neq0$**的向量（或者说，所有与$(-2,1)$共线的正倍数向量，比如$(-2,1)$、$(-4,2)$等，它们属于同一个极射线）。

原因很简单：假设$d$是满足$d_1+2d_2=0$的方向，如果尝试把它写成两个不共线方向$d',d''\in S$的正线性组合$d=\alpha d'+\beta d''$（$\alpha,\beta>0$），那么必须有$d'_1+2d'_2\le0$、$d''_1+2d''_2\le0$。代入$d$的约束：
$$\alpha(d'_1+2d'_2)+\beta(d''_1+2d''_2)=d_1+2d_2=0$$
因为$\alpha,\beta>0$，且两个括号里的项都是非正的，所以只能是$d'_1+2d'_2=0$且$d''_1+2d''_2=0$，也就是$d'$和$d''$都和$d$共线，不符合“不共线”的要求，因此这类方向是极方向。

而像$(-1,0)$、$(0,-1)$这类满足$d_1+2d_2<0$的方向，都可以表示为极方向与其他方向的正线性组合（比如$(-1,0)=0.5\times(-2,1)+0.5\times(0,-1)$），所以它们不是极方向。

三、S中点的表示问题 #

你提到的“极点凸组合加极方向非负线性组合”是多面体凸集的经典表示定理，但S是一个半空间，不属于多面体凸集（它无界且没有极点），所以这个定理对S不适用。

由于S没有极点，自然无法用“极点的凸组合”来表示其中的点。不过我们可以换一种方式描述：任意$x\in S$都可以表示为S中某个固定点（比如边界上的$(4,0)$）加上S的方向锥中向量的非负线性组合。举两个例子：

• 点$(0,0)$可以表示为$(4,0)+2\times(-2,1)+2\times(0,-1)$，其中$(-2,1)$是极方向，$(0,-1)$是S的方向；
• 点$(-1,-1)$可以表示为$(4,0)+2.5\times(-2,1)+3.5\times(0,-1)$。

但这和你提到的“极点凸组合加极方向非负组合”形式不同，因为S没有极点，凸组合部分为空（通常空组合定义为0向量，但0向量无法用来表示S中所有点）。

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