Farkas引理的一種新的證明

錢金娥

（長江大學 信息與數學學院，湖北 荊州 434023）

Farkas引理的一種新的證明

錢金娥

（長江大學 信息與數學學院，湖北 荊州 434023）

關于Farkas引理的證明有很多種不同的方法，主要包括三類：初等證明，代數證明和幾何證明.而本文中給出了其中的一類方法，屬于初等證明.

Farkas引理；初等證明；有效集法

1 前言

Farkas引理是一個經典的結果，是最優化方法中最為基礎的工具之一.該引理首次由Farkas于1902年提出.我們可以在大多數最優化教程中發現該引理的證明,如文獻[2]中.這個引理的早期證明類似于對偶單純形法，但其證明并未考慮到可能出現的循環現象，因此并不完整.近期的證明通常基于凸集分離定理.這種方法有一個簡單和更直觀的幾何解釋，參見文獻[10].在本文中我們試圖克服這個困難通過一個簡單展示一個簡單的獨立的證據是基于基本的論據.

2 Farkas引理

設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)的解，考慮單參數求積函數

由此得到(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,….具體實現由以下兩個步驟組成.

第一步：解決一個不受約束的最小二乘問題.

若t=0或rk=0，則跳到第二步.

注意到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為

的最優解.

上述運算具有有限終止屬性，同時有如下結果：

(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:A review,Ann.Oper.Res.,46(1993),pp.11-60.

〔10〕Yuan Y X,Sun W Y.Optimization Theory and Algorithms.Beijing:Science Press,(1997).

O221

A

1673-260X（2017）03-0001-02

2016-11-21