极射线

极射线的定义：

\begin{aligned} \{\boldsymbol{x} \in R^n|\boldsymbol{x}=\boldsymbol{x^{0}}+\theta\boldsymbol{d},\theta > 0,\forall \boldsymbol{x^{0}} \in X \} \in X \end{aligned}

其中 $X$ 代表可行域。上式的含义为，对 $n$ 维可行域中的任意一点，其沿着向量 $\boldsymbol{d}$ 的方向前进，所到达的位置仍为可行域

💡简单来说，当且仅当可行域为unbound的情况时，可行域才会存在极射线，沿极射线方向，目标函数会不断向着其优化方向前进，取到 $-\infty$ 或者 $+\infty$ ，下面是一个简单示意图 Pasted image 20240311133753.png#pic_center 其中两条蓝线和坐标轴构成了问题的可行域，但该可行域是无界的，所有的可行解沿着两条蓝线方向和两条蓝线开口内方向前进，仍在可行域范围内，即极射线的存在是可行域无界的特征

💡基于上述内容，我们可推出优化问题无界的充要条件：对于一个最小化问题：

\begin{aligned} min\,c^Tx \\ s.t \, Ax \geq b \\ x \geq 0 \end{aligned}

对于可行解 $x^{0}$ ，其对应的目标函数值为 $c^Tx^0$ ，按照极射线的定义， $x^{0}+\theta d$ 也是可行解，此时的目标函数值为 $c^T(x^{0}+\theta d)$ ，如果 $c^Td < 0$ ，那么我们很容易知道，目标函数可以无穷无尽地减小下去，此时的目标函数最优值为 $-\infty$ ，该问题无界（最大化问题同理）

总结如下： 假设可行域中至少存在一个极点，则最优解为 $-\infty$ 的充要条件为当且仅当存在某个极射线 $\boldsymbol{d}$ 使：

c^Td \leq 0

极点

极点的定义：可行域 $n$ 维空间中的基可行解对应的点，即为“凸包”中的”顶点“