Farkas引理及其应用

Farkas引理的一种新的证明钱金娥【摘要】关于Farkas引理的证明有很多种不同的方法,主要包括三类:初等证明,代数证明和几何证明.而本文中给出了其中的一类方法,属于初等证明.【期刊名称】《赤峰学院学报（自然科学版）》【年(卷),期】2017(033)006【总页数】2页(P1-2)【关键词】Farkas引理;初等证明;有效集法【作者】钱金娥【作者单位】长江大学信息与数学学院, 湖北荆州 434023【正文语种】中文【中图分类】O221Farkas引理是一个经典的结果，是最优化方法中最为基础的工具之一.该引理首次由Farkas于1902年提出.我们可以在大多数最优化教程中发现该引理的证明,如文献[2]中.这个引理的早期证明类似于对偶单纯形法，但其证明并未考虑到可能出现的循环现象，因此并不完整.近期的证明通常基于凸集分离定理.这种方法有一个简单和更直观的几何解释，参见文献[10].在本文中我们试图克服这个困难通过一个简单展示一个简单的独立的证据是基于基本的论据.设A是m×n实矩阵，c为非零的n维常向量.Farkas引理声称对于如下两个系统：不能同时都有解.注意，cTx＜0意味着x≠0；ATy=c意味着y≠0.（零向量的维数与对应向量维数相匹配.）如果系统(1)、(2)满足不等式：与cTx＜0矛盾.因此，两个系统都有解是不可能的.两个系统都可解的问题又可以通过考虑约束最小二乘问题来回答：这里|| ||表示欧几里得范数.令y*是Rm中给定的一点，令表示相应的余向量.我们将证明，由下面的引理2，y*为(3)式的解，当且仅当y*和r*满足下列条件:这些条件下面还会被用在建立存在一点y*∈Rm为 (3)式的解.结合(4)、(5)可得：由此我们将得出以下结论.定理1 令y*为方程(3)的解，令r*=ATy*-c，表示相应的余向量.如果r*=0，y*为(2)的解.否则，r*为(1)的解，cTr*=-||r*||2.引理2 令y*=(y1*,…,ym*)T是Rm中给定的一点，令r*由(4)定义，因此，y*为(3)的解，当且仅当y*、r*满足(5).证明假设y*为(3)的解，考虑单参数求积函数其中代表A的第i行元素，θ是一个实变量，ei代表m×n单位矩阵的第i列.因此，明显有θ=0是下列问题的解：因此，若意味着意味着由此得到(5).相反地，假设(5)有效，令z为Rm中的任意点，有z≥0，令m维向量u=(u1,…,um)T由z的性质可知u=z-y*，因此，yi*=0意味着ui≥0，可得uTAr*≥0.因此，由恒等式:可以得到||ATz-c||2≥||ATy*-c||2.则需要建立存在一个点y*为(3)的解.上述定理可以由一个简单的迭代运算完成需要k次迭代，k=1,2,….具体实现由以下两个步骤组成.第一步：解决一个不受约束的最小二乘问题.令表示当前解决方案的估计在k次迭代的开始.定义：，Wk中指数（标量）的数量由t表示，Vk和Wk中的应该为第k次迭代中第i个分量，定义t为一个非零的自然数.若t=0或rk=0，则跳到第二步.令为t×n阶矩阵，其行元素为其中行的次序是无关紧要的.因此，简单假设用t维向量解决无约束的最小二乘问题注意到0为此问题的解.当且仅当Akrk=0.在这种情况下，跳到第二步.定义一个非零搜索方向由分量为ui=wi，i=1,…,t和ui=0,i=t+1,…,m.记号和则下一点被定义为y(k+1)=u(k)+θku(k)，其中θk＞0为区间[0,1]中的最大数保持点y(k)+θu(k)对上述问题可行.换句话说，θk是区间{1}∪中的最小数.第二步：测试最佳性和远离无意义的点，这里有Akrk=0，则意味着y(k)为以下问题的解：在这种情况下，y(k)被称为“无意义点”，为测试y(k)是否为最佳的，我们估算指数j为如果，则y(k)和rk满足(5)式，因此，由引理2有，y(k)为(3)式的解，算法终止.否则，下一点被定义为y(k+1)=y(k)-其中ej表示m×m阶单位矩阵的第j列.注意-为下列问题的最优解.上述运算具有有限终止属性，同时有如下结果：(a)在每个迭代中，目标函数是严格递减的，即(b)对上述提到的θk有0≤θk≤1.则有，如果θk=1，则y(k+1)是无意义的点.否则，当0＜θk＜1，t递减.因此，这是不可能的去完成超过m次迭代而不到达无意义点.(c)我们每次到达一个无意义的点，当前的点y(k)为(6)式的解.(d)对这些问题的数量是有限的，然而，由于存在(6a)式，故访问同样的问题(6)两次是不可能的.上述迭代过程本质上属于有效集法.有效集是指那些在最优点有效的不等式约束所组成的集合.如果我们能提前知道在最优点处有效的约束，那我们就可以把那些未有效的不等式约束剔除掉并把原命题转化成更易求解的等式约束命题.然而，在求解之前我们往往对最优点处的有效约束知之甚少.因此如何找到最优点处的有效约束也就是有效集法的主要工作.将新的证明方法与其他的方法相比而言是有趣的.一个传统的方法去证明点y*为(3)式的解的存在性是在观察Z= {ATy|y≥0}为Rn上的闭集的基础上的.证明这一要求的确要详细的阐述.如[2,P.332-334]或[8, P.10].利用闭集Z,可得B={z|z∈Z,||z-c||≤||c||}是Rm上的一个非空的闭集.同时注意：φ(x)=||x-c||2是x的一个连续函数.因此，由魏尔施特拉斯定理，φ(x)可得出它的最小值在B上.令z*∈B表示最小值点.若B⊆Z,则存在一点y*∈Rm，使y*≥0和z*=ATy*；因此，y*为(3)式的解.点z*=ATy*是c在Z上的映射.若Z是一个凸集，φ(x)是一个严格凸函数，z*是唯一的.然而，y*不是唯一的. 这一特征与r*性质密切相关，虽然众所周知，但是通常注意较少[4].推论3 令y*和r*同定理1中所定义的，假设r*≠0，则向量r*/||r*||为最速下降问题的解：证明令x满足约束条件(7b)，则(y*)TAx≥0，由柯西-施瓦兹不等式有：综上所述有：因此，cTr*/||r*||=-||r*||，即得证.证明Farkas引理的一种常见方法是应用分离超平面定理，参见文献[2,3,4,5,6,7].这个方法需要运用分离超平面定理和闭集Z，c为Z上一个映射.在我们的证明中，定理1代替分离超平面定理，前面两个步骤给出的本质上是有效集法，而y*则是通过一个典型的“有效集”的方法得出的.因此，这种相似的证明方法也能在其他的定理中使用.例如最小二乘问题结合最速下降方向,能够计算出最速下降法为解决有效集方法退化提供了一种有效的方法，这个问题在参考文献[2]中有详细的讨论. 〔1〕AChiya Dax.An Elementary proof of Farkas’Lemma*.39(3)(1997),pp.503-507,September.〔2〕P.G.Ciarlet,Introduction to Numerical Linear Algebra and Optimization,Cambridge university Press,Cambridge, 1989.〔3〕P.E.Gill,W Murray,and M.H.Wright,Numerical Linear and Optimization,1(1991),Addison-Wesley Reading,MA,.〔4〕M.J.D.Powell,Introduction to Constrained Optimization, in Numerical Methods for Constrained Optimization,P. E.Gill and Wurray,eds.,Academic Press,New York,(1970), pp.1-28,.〔5〕R.Fletcher,Practical Methods of Optimization.2(1981): Constrained Optimization,John.Wiley,New York.〔6〕G.P.McComick,Nonlinear Programming,McGraw-Hill, New York,(1969). 〔7〕G.Zoutendijk,Methods of Feasible Directions,Elsevier-North Holland,Amsterdam,(1960).〔8〕M.R.Osborne,Finite Algorithms in Optimization and Data Analysis,John.Wiley&Sons,Chichester,(1985).〔9〕A.DAX,The relationship between theorems of the alternation,least norm descent directions,And degeneracy:Areview,Ann.Oper.Res.,46(1993),pp.11-60.〔10〕Yuan Y X,Sun W Y.Optimization Theory and Algorithms.Beijing:Science Press,(1997).。

farkas引理的几个等价形式及其推广farkas引理的几个等价形式及其推广引言：Farkas引理是线性规划领域中一个重要的定理，它描述了一组线性不等式是否具有解的问题。

这个引理起初由匈牙利数学家László Farkas于1894年提出，被广泛应用于优化、运筹学、计算机科学等多个领域。

在本文中，将介绍Farkas引理的几个等价形式，并进一步探讨其在不同应用中的推广。

一、标准形式的Farkas引理：Farkas引理最经典的形式是标准形式的描述。

假设给定一个矩阵 A 和一个向量 b，我们希望确定一个向量 x，使得Ax ≤ b。

Farkas引理指出，存在一个非负的向量 y，使得 A^T y = 0，且 b^T y < 0，当且仅当线性不等式组Ax ≤ b 无解。

这个形式的Farkas引理成为许多后续推广的基础。

二、齐次标准形式的Farkas引理：在实际问题中，我们可能会遇到线性等式组 Ax = 0 的问题。

所谓齐次问题，是指限制条件中等号成立的情况。

针对这个问题，Farkas引理有如下等价形式：存在一个非负的向量 y，使得 A^T y = 0，当且仅当线性等式组 Ax = 0 至少有一个非零解。

这个形式的引理在研究齐次问题时非常有用，并且与标准形式的Farkas引理之间有着密切的联系。

三、半正定形式的Farkas引理：Farkas引理还可以推广到矩阵 A 是半正定的情况下。

半正定矩阵是指对任意非零向量 x，都有 x^T Ax ≥ 0。

这个推广形式的Farkas引理表示：当且仅当存在一个非负的向量 y，使得 A^T y = 0，线性条件Ax ≤ b 具有解时，必须满足 y^T b ≥ 0。

这个推广对于解决一些特殊类型的优化问题非常有帮助，尤其是在半正定约束下的最优化问题中。

四、多目标形式的Farkas引理：Farkas引理的最后一个推广形式是针对多目标优化问题的。

在多目标优化中，我们希望在多个目标中找到一个最优解。