Farkas引理的几种证明方法.pdf

Farkas引理是凸优化领域中一个非常重要的理论工具，它在数学的多个分支中都扮演着关键的角色，尤其是在线性规划、非线性规划以及最优控制理论中。引理的基本内容涉及到线性不等式系统解的存在性问题，并提供了一种通过线性规划的对偶理论来证明解集为空集的条件。 预备知识部分涉及到凸分析中的几个重要概念，包括凸集与点的分离定理、锥与极锥理论以及对偶理论。 凸集与点的分离定理是凸分析的基础定理之一，它说明如果一个点不属于一个闭凸集，那么存在一个分离超平面将这个点和这个凸集分离，即存在一个向量和一个标量，使得凸集内的所有点都在向量的一侧，而该点在向量的另一侧，且该点到超平面的距离大于零。 锥和极锥的定义是凸分析中的基本概念。锥是定义在向量空间中的一个子集，如果对于任意的向量和非负实数λ，锥内的向量的λ倍也在锥内，则称这个集合为锥。一个闭凸锥的极锥是所有和锥内向量正交的向量所构成的集合的闭包。极锥的一个重要性质是，一个闭凸锥的极锥的再次极锥就是它本身。 对偶理论是线性规划的基础理论之一，它是通过建立原始问题和对偶问题的关系来研究问题的解的结构和性质，以及如何通过解对偶问题来获得原始问题的解的信息。 Farkas引理的具体表述是：设A为一个m×n维矩阵，c为一个n维列向量，那么以下两个问题恰好有一个有解：(1) 对某个x，有Ax≤c；(2) 对某个y，有y≥0且yTA=0且yTc<0。如果问题(2)有解，则问题(1)无解，反之亦然。 证明Farkas引理的一种方法是利用凸集与点的分离定理。证明的关键在于构建一个适当定义的闭凸集，并证明问题(1)和问题(2)的解的存在性分别对应着这个闭凸集能够被一个超平面严格分离于原点的不同情况。如果问题(2)有解，那么可以找到一个向量和标量，使得凸集内的所有点都在向量的一侧，而原点在另一侧，这表明问题(1)无解；反之亦然。 另一种证明方法是使用锥和极锥理论。证明过程中，构建锥和极锥，通过对偶性的分析，确定问题(1)和问题(2)的解的存在性与锥和极锥的关系。通过构造适当的锥和极锥，可以证明问题(1)有解意味着问题(2)无解，反之亦然。 对偶理论也被应用于Farkas引理的证明中，通过线性规划问题和其对偶问题的关系，可以证明如果一个线性规划问题无解，则其对偶问题要么无界要么无解。通过将Farkas引理与线性规划问题及其对偶问题联系起来，可以用对偶理论的视角来证明引理的结论。 Farkas引理的多种证明方法揭示了凸分析、锥与极锥理论以及对偶理论在证明数学定理时的强大能力。这些证明方法不仅深化了对Farkas引理的理解，也为解决实际问题提供了多种途径和视角。