Farkas引理的一種新的證明

錢金娥

（長(zhǎng)江大學(xué) 信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023）

Farkas引理的一種新的證明

錢金娥

（長(zhǎng)江大學(xué) 信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023）

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

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

1 前言

Farkas引理是一個(gè)經(jīng)典的結(jié)果，是最優(yōu)化方法中最為基礎(chǔ)的工具之一.該引理首次由Farkas于1902年提出.我們可以在大多數(shù)最優(yōu)化教程中發(fā)現(xiàn)該引理的證明,如文獻(xiàn)[2]中.這個(gè)引理的早期證明類似于對(duì)偶單純形法，但其證明并未考慮到可能出現(xiàn)的循環(huán)現(xiàn)象，因此并不完整.近期的證明通常基于凸集分離定理.這種方法有一個(gè)簡(jiǎn)單和更直觀的幾何解釋，參見文獻(xiàn)[10].在本文中我們?cè)噲D克服這個(gè)困難通過(guò)一個(gè)簡(jiǎn)單展示一個(gè)簡(jiǎn)單的獨(dú)立的證據(jù)是基于基本的論據(jù).

2 Farkas引理

設(shè)A是m×n實(shí)矩陣，c為非零的n維常向量.Farkas引理聲稱對(duì)于如下兩個(gè)系統(tǒng)：

不能同時(shí)都有解.

注意，cTx＜0意味著x≠0；ATy=c意味著y≠0.（零向量的維數(shù)與對(duì)應(yīng)向量維數(shù)相匹配.）如果系統(tǒng)(1)、(2)滿足不等式：

與cTx＜0矛盾.因此，兩個(gè)系統(tǒng)都有解是不可能的.兩個(gè)系統(tǒng)都可解的問題又可以通過(guò)考慮約束最小二乘問題來(lái)回答：

這里|| ||表示歐幾里得范數(shù).

令y*是Rm中給定的一點(diǎn)，令

表示相應(yīng)的余向量.我們將證明，由下面的引理2，y*為(3)式的解，當(dāng)且僅當(dāng)y*和r*滿足下列條件:

這些條件下面還會(huì)被用在建立存在一點(diǎn)y*∈Rm為 (3)式的解.

結(jié)合(4)、(5)可得：

由此我們將得出以下結(jié)論.

定理1 令y*為方程(3)的解，令r*=ATy*-c，表示相應(yīng)的余向量.如果r*=0，y*為(2)的解.否則，r*為(1)的解，cTr*=-||r*||2.

引理2 令y*=(y1*,…,ym*)T是Rm中給定的一點(diǎn)，令r*由(4)定義，因此，y*為(3)的解，當(dāng)且僅當(dāng)y*、r*滿足(5).

證明 假設(shè)y*為(3)的解，考慮單參數(shù)求積函數(shù)

由此得到(5).

相反地，假設(shè)(5)有效，令z為Rm中的任意點(diǎn)，有z≥0，令m維向量u=(u1,…,um)T由z的性質(zhì)可知u=z-y*，因此，yi*=0意味著ui≥0，可得uTAr*≥0.

因此，由恒等式:

可以得到||ATz-c||2≥||ATy*-c||2.則需要建立存在一個(gè)點(diǎn)y*為(3)的解.

上述定理可以由一個(gè)簡(jiǎn)單的迭代運(yùn)算完成需要k次迭代，k=1,2,….具體實(shí)現(xiàn)由以下兩個(gè)步驟組成.

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

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

注意到0為此問題的解.當(dāng)且僅當(dāng)Akrk=0.在這種情況下，跳到第二步.定義一個(gè)非零搜索方向由分量為ui=wi，i=1,…,t和ui=0,i=t+1,…,m.記號(hào)和則下一點(diǎn)被定義為y(k+1)=u(k)+θku(k)，其中θk＞0為區(qū)間[0,1]中的最大數(shù)保持點(diǎn)y(k)+θu(k)對(duì)上述問題可行.換句話說(shuō)，θk是區(qū)間{1}∪中的最小數(shù).

第二步：測(cè)試最佳性和遠(yuǎn)離無(wú)意義的點(diǎn)，這里有Akrk=0，則意味著y(k)為以下問題的解：

在這種情況下，y(k)被稱為“無(wú)意義點(diǎn)”，為測(cè)試y(k)是否為最佳的，我們估算指數(shù)j為

的最優(yōu)解.

上述運(yùn)算具有有限終止屬性，同時(shí)有如下結(jié)果：

(a)在每個(gè)迭代中，目標(biāo)函數(shù)是嚴(yán)格遞減的，即

(b)對(duì)上述提到的θk有0≤θk≤1.則有，如果θk=1，則y(k+1)是無(wú)意義的點(diǎn).否則，當(dāng)0＜θk＜1，t遞減.因此，這是不可能的去完成超過(guò)m次迭代而不到達(dá)無(wú)意義點(diǎn).

(c)我們每次到達(dá)一個(gè)無(wú)意義的點(diǎn)，當(dāng)前的點(diǎn)y(k)為(6)式的解.

(d)對(duì)這些問題的數(shù)量是有限的，然而，由于存在(6a)式，故訪問同樣的問題(6)兩次是不可能的.

上述迭代過(guò)程本質(zhì)上屬于有效集法.有效集是指那些在最優(yōu)點(diǎn)有效的不等式約束所組成的集合.如果我們能提前知道在最優(yōu)點(diǎn)處有效的約束，那我們就可以把那些未有效的不等式約束剔除掉并把原命題轉(zhuǎn)化成更易求解的等式約束命題.然而，在求解之前我們往往對(duì)最優(yōu)點(diǎn)處的有效約束知之甚少.因此如何找到最優(yōu)點(diǎn)處的有效約束也就是有效集法的主要工作.

將新的證明方法與其他的方法相比而言是有趣的.一個(gè)傳統(tǒng)的方法去證明點(diǎn)y*為(3)式的解的存在性是在觀察Z= {ATy|y≥0}為Rn上的閉集的基礎(chǔ)上的.

證明這一要求的確要詳細(xì)的闡述.如[2,P.332-334]或[8, P.10].利用閉集Z,可得B={z|z∈Z,||z-c||≤||c||}是Rm上的一個(gè)非空的閉集.同時(shí)注意：φ(x)=||x-c||2是x的一個(gè)連續(xù)函數(shù).因此，由魏爾施特拉斯定理，φ(x)可得出它的最小值在B上.令z*∈B表示最小值點(diǎn).若B?Z,則存在一點(diǎn)y*∈Rm，使y*≥0和z*=ATy*；因此，y*為(3)式的解.點(diǎn)z*=ATy*是c在Z上的映射.若Z是一個(gè)凸集，φ(x)是一個(gè)嚴(yán)格凸函數(shù)，z*是唯一的.然而，y*不是唯一的. 這一特征與r*性質(zhì)密切相關(guān)，雖然眾所周知，但是通常注意較少[4].

推論3 令y*和r*同定理1中所定義的，假設(shè)r*≠0，則向量r*/||r*||為最速下降問題的解：

證明 令x滿足約束條件(7b)，則(y*)TAx≥0，由柯西-施瓦茲不等式有：

綜上所述有：

因此，cTr*/||r*||=-||r*||，即得證.

證明Farkas引理的一種常見方法是應(yīng)用分離超平面定理，參見文獻(xiàn)[2,3,4,5,6,7].這個(gè)方法需要運(yùn)用分離超平面定理和閉集Z，c為Z上一個(gè)映射.在我們的證明中，定理1代替分離超平面定理，前面兩個(gè)步驟給出的本質(zhì)上是有效集法，而y*則是通過(guò)一個(gè)典型的“有效集”的方法得出的.因此，這種相似的證明方法也能在其他的定理中使用.例如最小二乘問題結(jié)合最速下降方向,能夠計(jì)算出最速下降法為解決有效集方法退化提供了一種有效的方法，這個(gè)問題在參考文獻(xiàn)[2]中有詳細(xì)的討論.

〔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