含线性约束的θ依赖欠定线性系统解的存在性条件探究

咱们一步步来拆解这个带线性约束的欠定线性系统可行解存在性的充要条件问题——毕竟这类问题结合了线性代数基础和凸分析的知识，得把逻辑理清楚：

首先先明确问题的定义：

给定欠定线性系统：
$$
\begin{align}
& A(\theta)x = b\
s.t. \quad & Cx > 0,
\end{align}
$$
其中 $x \in \mathbb{R}^{n}$，$b \in \mathbb{R}^{m}$（已知常向量），$C \in \mathbb{R}^{k\times{n}}$（已知常矩阵），$A(\theta) \in \mathbb{R}^{m\times{n}}$（仅依赖实变量 $\theta$，且满足 $m < n$），我们需要找出该系统可行集非空（即存在解）的充要条件。

一、先从无约束欠定系统的解存在性基础入手 #

首先得回忆：无约束的线性方程组 $A(\theta)x = b$ 有解的充要条件是 $b$ 属于 $A(\theta)$ 的列空间，用秩的语言描述就是：$\text{rank}(A(\theta)) = \text{rank}([A(\theta) \mid b])$。这是线性代数的基本结论，但这里我们还要加上 $Cx > 0$ 的严格不等式约束，所以必须把这个基础条件和约束结合起来分析。

二、结合不等式约束的充要条件推导 #

我们可以把问题转化为：是否存在 $x$ 同时满足线性等式 $A(\theta)x = b$ 和严格线性不等式 $Cx > 0$。这里提供两种等价的推导思路：

思路1：利用解的参数化形式 #

因为 $m < n$（欠定），如果 $A(\theta)x = b$ 有解，那么它的通解可以写成：
$$x = x_p + Nz$$
其中：

• $x_p$ 是 $A(\theta)x = b$ 的任意一个特解；
• $N \in \mathbb{R}^{n\times(n-m)}$ 是 $A(\theta)$ 的零空间的一组基（满足 $A(\theta)N = 0$）；
• $z \in \mathbb{R}^{n-m}$ 是任意的参数向量。

把通解代入不等式约束 $Cx > 0$，就得到了关于 $z$ 的严格线性不等式组：
$$Cx_p + CN z > 0$$
也就是：$(CN)z > -Cx_p$。

现在问题变成了：这个关于 $z$ 的不等式组是否有解？根据严格形式的Farkas引理，该不等式组有解的充要条件是：

不存在非零的非负向量 $y \in \mathbb{R}^k_+$（即 $y_i \geq 0$ 且至少有一个分量大于0），使得 $y^T(CN) = 0$ 且 $y^T(-Cx_p) \geq 0$。

整理一下，结合前面的基础条件，整个系统有解的充要条件就是：

• $\text{rank}(A(\theta)) = \text{rank}([A(\theta) \mid b])$（保证 $A(\theta)x = b$ 有解）；
• 不存在非零的 $y \geq 0$，满足 $y^T C N = 0$ 且 $y^T C x_p \leq 0$。

思路2：利用凸分析的分离定理 #

可行集是线性方程组的解空间（一个仿射子空间）和开凸集 ${x \mid Cx > 0}$ 的交集。根据凸集分离定理，两个凸集交集非空的充要条件是不存在能分离它们的非零线性泛函，翻译成向量语言就是：

不存在非零向量 $(\lambda, y)$，其中 $\lambda \in \mathbb{R}^m$，$y \in \mathbb{R}^k_+$（非负），使得：
$$\lambda^T A(\theta) + y^T C = 0 \quad \text{且} \quad \lambda^T b \geq 0$$

这里需要注意：如果 $y = 0$，那么 $\lambda^T A(\theta) = 0$ 且 $\lambda^T b \geq 0$，但此时若 $A(\theta)x = b$ 有解，那么 $\lambda^T b = \lambda^T A(\theta)x = 0$，这就要求 $\lambda^T b = 0$，但如果 $\lambda \neq 0$，这和 $A(\theta)x = b$ 有解的条件矛盾（因为此时 $b$ 不在 $A(\theta)$ 的列空间里），所以当第一个条件满足时，$y=0$ 的情况不会出现，我们只需要考虑 $y \neq 0$ 的情况。

这个条件和思路1的结论是完全等价的，你可以通过代数推导互相转换。

三、针对依赖θ的特殊情况 #

因为 $A(\theta)$ 是依赖实变量 $\theta$ 的矩阵，所以上述所有条件都需要针对每个具体的θ值来判断：

• 先检查当前θ对应的 $A(\theta)$ 的秩与增广矩阵的秩是否相等，确保 $A(\theta)x =b$ 有解；
• 再在此基础上，检查是否存在满足条件的非负向量 $y$（或者等价地，检查参数化后的不等式组是否有解）。

如果要找所有使得可行集非空的θ的集合，就是同时满足上述两个条件的θ的全体。

总结 #

把所有条件整合起来，该系统可行集非空（即解存在）的充要条件是以下两点同时成立：

• 线性方程组 $A(\theta)x = b$ 有解，即 $\text{rank}(A(\theta)) = \text{rank}([A(\theta) \mid b])$；
• 不存在非零的非负向量 $y \in \mathbb{R}^k_+$，使得 $y^T C$ 属于 $A(\theta)$ 行空间的正交补（即 $y^T C \in \text{row}(A(\theta))^\perp$）且 $y^T C x_p \leq 0$（其中 $x_p$ 是 $A(\theta)x =b$ 的任意特解）。

或者用分离定理的等价表述：不存在非零的 $\lambda \in \mathbb{R}^m$ 和非零的 $y \in \mathbb{R}^k_+$，使得 $\lambda^T A(\theta) + y^T C = 0$ 且 $\lambda^T b \geq 0$。

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