改進(jìn)求解凸二次規(guī)劃中的Lemke算法.

1、改進(jìn)求解凸二次規(guī)劃中的Lemke算法張璐遼寧工程技術(shù)大學(xué)理學(xué)院，遼寧阜新（123000E-mail:zha nglu85517摘要:通過對經(jīng)典的Lemke互補轉(zhuǎn)軸算法求解凸二次規(guī)劃問題的分析，找到了 Lemke算法的局限性。本文在 Lemke算法求解線性互補問題的基礎(chǔ)上修正了經(jīng)典 的Lemke算法的迭代過程，提出了一種改進(jìn)的Lemke算法，通過算例證明了算法能 有效克服解的局限性，減少了凸二次規(guī)劃問題的迭代過程，提高了算法的效率。關(guān)鍵詞:非線性規(guī)劃；凸二次規(guī)劃；線性互補問題;Lemke算法1.引言二次規(guī)劃問題是最簡單而又最基本的非線性規(guī)劃問題，其目標(biāo)函數(shù)是二次函數(shù)約束是線性等式或不等式。對于二

2、次規(guī)劃問題，可行域是凸集，所以當(dāng)目標(biāo)函數(shù)是凸 函數(shù)時，任何K-T點都是二次規(guī)劃問題的極小點。研究二次規(guī)劃問題的算法不僅僅 是為了解決二次規(guī)劃問題本身，同時也是為了更好的求解其他非線性規(guī)劃問題。因 為大多數(shù)最優(yōu)化方法是從二次函數(shù)模型導(dǎo)出的，這種類型的方法在實際中常常是有 效的,其主要是因為一般函數(shù)的極小點附近常可用二次函數(shù)很好地進(jìn)行近似。由于 二次規(guī)劃是特殊的非線性規(guī)劃，因此求解非線性規(guī)劃問題的方法均可用于二次規(guī)劃 問題的求解。同時，由于二次規(guī)劃本身的特殊性，對它的求解可以采用一些更有效的 方法1。因此，不論從數(shù)學(xué)角度還是應(yīng)用角度來看，二次規(guī)劃問題的研究都具有重要 意義。到目前為止，已經(jīng)出現(xiàn)了很

3、多求解二次規(guī)劃問題的算法，并且現(xiàn)在仍有很多學(xué) 者在從事這方面的研究工作。所以，需要我們對現(xiàn)存的有效的求解二次規(guī)劃問題的 算法進(jìn)行改進(jìn)，得到新的求解算法來克服某些算法的缺點，并且給出具體的實例顯示 該算法的有效性。本文主要研究凸二次規(guī)劃的求解算法，以及線性互補問題的性質(zhì)等相關(guān)問題。對Lemke算法進(jìn)行進(jìn)一步研究，對它可能出現(xiàn)退化的原因和迭代過程 以及局限性進(jìn)一步分析。本文通過分析經(jīng)典的Lemke互補轉(zhuǎn)軸算法求解含有等式 約束的凸二次規(guī)劃問題可能出現(xiàn)退化的原因，修正了 Lemke算法的迭代步驟，提出了 一種改進(jìn)的Lemke算法。通過求解具體實例，說明了改進(jìn)算法求解凸二次規(guī)劃問題 的有效性2。2.L

4、emke算法介紹2.1 Lemke算法的基本思想Lemke算法的基本思想是，由一個準(zhǔn)互補基本可行解出發(fā)，通過轉(zhuǎn)軸方法（即主元 消去求出一個新的準(zhǔn)互補基本可行解3。這個過程可以不斷地迭代，力爭使變量0z 稱為非基變量，或者得到一個判據(jù)，說明問題（3-3和（3-4可行域無界。轉(zhuǎn)軸方法（主元 消去遵循以下規(guī)則：（1保持可行性 按照最小比值規(guī)則確定離基變量。（2保持準(zhǔn)互補性 若i w （或i z是離基變量，則i z （或i w是進(jìn)基變量。2.2 Lemke方法的計算步驟（1若Oq級，亭止計算，（,（,0w z q =是互補基本可行解；否則,用表格形式表示成方 程組，設(shè)max1,i i q q i m

5、n -=-= ? ? ? +取s行為主行,0z對應(yīng)的列為主列，進(jìn)行主元消去，令s s y z =（2設(shè)在現(xiàn)行表中變量s y下面的列為s d若Os d則停止計算；否則，按最小比 值規(guī)則確定指標(biāo)r，使min |0i i is rs is q q d d d ?=?如果r行的基變量是Oz，則轉(zhuǎn)步驟（4;否則，進(jìn)行步驟（3。（3設(shè)r行的基變量為I w或I z （對于某個I s變量s y進(jìn)基，以r行為主行,s y對 應(yīng)的列為主列，進(jìn)行主元消去。如果離基變量是I w ,則令s I y z =;如果離基變量是I z，則令s I y w =。轉(zhuǎn)步驟（2（4變量s y進(jìn)基,0z離基。以r行為主行,s y對應(yīng)的列

6、為主列，進(jìn)行主元消去。得到互補基本可行解，停止計算42.3 Lemke互補轉(zhuǎn)軸算法的局限性分析首先，這一算法滿足于一個互補基本可行解。所以用它不可能求得線性互補問 題的多個解其次，這一算法的收斂條件很強，限制了它的使用范圍此算法的收斂定理：（1 0z ?步有 0T z Mz 而且 0（0T z Mz z =蘊涵（0TM M z +=。 （M is said to be copositive-plus;（2每- 個準(zhǔn)互補基本可行解 （aImost compIementary basic feasibIe solution均非退 化。若式（2與（1相容,則Lemke互補轉(zhuǎn)軸算法終止于一個互補基本可

7、行解；若不相 容,則終止于射線，條件（1很強,而且不易檢查。但可以指出：若M的主對角線上出現(xiàn) 負(fù)元素，則條件（1必不滿足5,6,7。3改進(jìn)算法研究3.1改進(jìn)的Lemke算法的基本思想本文研究的改進(jìn)算法主要是求解線性互補問題，雖然向量q都有負(fù)向量，然而不 必引入人工向量0z，可以通過一個簡單公式算的一個互補基本可行解。定理3.1設(shè)矩陣M的第k列無負(fù)元素，即0k M 。若對應(yīng)于q的負(fù)分量（0i q ,而且max 0i k i ik kk q q q m m ?-,0i ik k i w m z q =+,1,i p i k = ? ? ?去 因而由（3-2給出線性互補問題的一個互補基本可行解（非基

8、變量均為零。下面討論離基變量的選取與進(jìn)基變量的確定。設(shè)初始解（0（0（0（0（011（,n n Zw w z z =?其中（0（00i i w z =（1,i n = ? ? ?,不妨設(shè)其中的兩個分量（Ot w和（Osz （t s為負(fù)數(shù)（對一個或多個分量為負(fù)的情形可以類推。顯然，離基變量要在（Ot w和（Os z中產(chǎn)生。同時，進(jìn)基變量要在（Os w和（Ot z中產(chǎn)生。由矩陣的初等行變換知識可知，（0t z和（Os w進(jìn)基后理論上的值應(yīng)為（1.t tt t q z M =或（1s s ss q w M =其中ij M為系數(shù)矩陣M中元素。顯然，進(jìn)基后的（1t z或（1s w的值為非負(fù)時，解的結(jié)構(gòu)才

9、有所改善。若（1Ot z ,（1Os則選取（Ot w為離基變量；若（1Ot z ,（1Os w 則選?。∣s z為離基變量。不妨記以上離基規(guī)則為最大正互補變量規(guī)則3.2改進(jìn)的Lemke算法的算法證明（1算法的可行性分析定義3.1:如果基本可行解中只有一對分量都不是基變量，而其余各對分量都有 一個,而且剛好有一個為基變量的，稱為特互補基本可行解。其中，一對分量指i w ,i z , 即w ,z有相同的足標(biāo)的一對分量。定義3.2:一個特互補基本可行解中如果大于O的分量個數(shù)少于原互補問題的階數(shù),則稱為其退化的互補基本可行解。定義3.3:取非基對的一個變量足標(biāo)定為主元列號，經(jīng)一個主元消去步驟便可得 出

10、另一個特互補基本可行解。用這種方法得到的新的特互補基本可行解稱為相鄰的 特互補基本可行解。定理3.2:一個線性互補問題，若它是非退化的，則任何一個特互補基本可行解最 多有兩個相鄰的特互補基本可行解。證明:我們只要證明對于非退化問題進(jìn)行一個主元消去步時，主元行號唯一就可以了。事實上，OOmin i iks i r q rk sk ik m q q q m m m 。若對應(yīng)于 q的負(fù)分量(Oi q v,都有Oik m ,而且max 0i k i ik kkq q q m m ? -= ?則線性互補問題有一個互補基本可行解/k k kki ik k iz q m w m z q =-=+,1,i p

11、 i k =? ? ?工其余變量均為零。若矩陣 M有多個列都 為正元素，則可有多個互補基本可行解，選取最優(yōu)解。第三步若不滿足Oq也矩陣M的每列不全為負(fù)元素，設(shè)（0（0（0min 0,1,r i i q q q i p =?取r行為主行，則?。?r z作為入基變量，對應(yīng)的（0r w作為出基變量（1,r p =? ? ?,即取主元（0rr d。對系數(shù)矩陣作進(jìn)行主元消去變 換，令（0（0r r w z =。對基向量中（k t z或（k t w有負(fù)分量，求出其負(fù)分量的互補變量（.k k t t k t t q w M =或（.k k t t k t tq z M =（其中（k ij m ,（k t q

12、分別為第k次迭代時M的系數(shù)矩陣和右端列中負(fù)元 素，且t j置,0k =。若（k t q均為非負(fù)元素，則停止計算取基向量的值為（k t q。設(shè)否則，轉(zhuǎn)第三步。第四步在第三步中，在互補變量中挑選出最大的正分量（k tw或（k t z （t r作為入基變量，對應(yīng)的（k t z或（k tw作為出基變量，?。╧ tt d為主元對系數(shù)矩陣作消元變換。置1k k =+,轉(zhuǎn)第三步。4.改進(jìn)算法在求解凸二次規(guī)劃中的實例分析例4.1求解下面的凸二次規(guī)劃22112212121212mi n (2812810.210242+ -,0f x x x x x x x s t x x x x x x =+解:本題中已知數(shù)據(jù)

13、如下24412H ?=?,810c -?=?-? ,1224A -?二？-? ,102b?=?-?,化成線性互補問題得到001200024122424412T A M A H-?- ?=?- ? ,102810b q c?_? =? ?_?,y w v ?=? ,u z x ? ?解法一:根據(jù)經(jīng)典的Lemke互補轉(zhuǎn)軸算法，在引入人工變量后，經(jīng)過4次迭代過互補基本可行解(14,6,0,6,(0,0,4,0T Tw z =。解法二:根據(jù)改進(jìn)的算法，矩陣M的第三列無負(fù)元素，而且33332810max 0max /,224i i i q q q m m ? - ? , 0z , 3,W z R表4-1

14、經(jīng)典的Lemke算法的初始表Tab.4-1 The initial table of classical Lemke algorithm基向量 w 1 w 2 w 3 z 1 z 2 z 3 z 0 q w 1 1 0 0 -2 1-3 -1-1 w 2 0 1 0 1 -10 -2 -1 -10w 3 0 0 1 3 2 0 -1 6表4-2經(jīng)典的Lemke算法的迭代表1Tab.4-2The first iterated table of classical Lemke algorithm基向量 w 1 w 2 w 3 z 1 z 2* z 3 z 0 q w 1 1 -1 0 -3 11*

15、 -1 0 9 z 0 0 -1 0 -1 10 2 110 w 3 0 -1 1 2 12 2 0 16表4-3經(jīng)典的Lemke算法的迭代表2Tab.4-3 The sec ond iterated table of classical Lemke algorithms 向量w 1 w 2 w 3 z 1* z 2 z 3 z 0 q z 21/11 -1/11 0 -3/11 1 -1/11 0 9/11 z 0 -10/11 -1/11 0 19/11* 032/11 1 20/11 w 3-12/11 1/11 1 58/11 0 34/11 0 68/11表4-4經(jīng)典的Lemke算法

16、的迭代表3Tab.4-4The third iterated table of classical Lemke algorithm基向量w 1 w 2 w 3 z 1 z 2 z 3 z 0 q z 2 -1/19 -2/19 0 0 1 7/19 3/19 21/19 z 1 -10/19 -1/19 01 0 32/19 11/19 20/19w 3 32/19 7/19 1 0 0 -110/19 -58/19 12/19所以線性互補可行解 T T (20/19,21/19,0,(0,0,12/19z w =即經(jīng)過三次迭代過程，得到K-T點12(,(20/19,21/19x x =。解法

17、二:利用改進(jìn)的算法表4-5改進(jìn)的Lemke算法的初始表Tab.4-5 The initial table of improved Lemke algorithm基向量 w 1 w 2 w 3 z 1 z 2 z 3 qw 1 1 0 0 -2 1-3 -1w 2 0 1 0 1-10* -2 -10 w 3 0 0 1 3 2 0 6 因為(0(0(01min 0i i q q q =,取2z為進(jìn)基變量則2w為出基變量，以(022d為主元，經(jīng)主元消去法得到表4-6改進(jìn)的Lemke算法的迭代表1Tab.4-6 The first iterated table of improved Lemke

18、algorithm基向量 w 1 w 2 w 3 z 1 z 2 z 3 qw 1 1 1/10 0 -19/10* 0 -6/5 -2z 2 0 -1/10 0 -1/10 1 1/5 1w 3 0 -2 1 16/5 0 -2/5 4顯然基向量為123(w ,(-2,1,4z w =，只有1w分量為負(fù)數(shù)，則1w的互補變量進(jìn)基，即1z進(jìn)基，則w 1出基，取(111d為主元，進(jìn)行主元消去得到Tab.4-7The sec ond iterated table of improved Lemke algorithm基 向量 w 1 w 2 w 3 z 1 z 2 z 3 q z 1 -10/19

19、-1/19 0 1 0 12/19 20/19 z 2 -1/19 -2/19 0 0 1 24/95 21/19 w 3 16/95 -174/95 1 0 0 -46/19 12/19得到基向量123(z ,(20/19,21/19,12/19z w =各分量均非負(fù)則停止計算。所以線性互補可行解T T(20/19,21/19,0,(0,0,12/19z w =所以僅經(jīng)過兩次迭代過程，得到K-T點12(,(20/19,21/19x x =例4.3求解如下凸二次規(guī)劃：221122121212min (24426.222f x x x x x x x st x x x x =-+-+解:有本題得

20、到如下數(shù)據(jù)2224H -?=?-?,26c -?=?-? ,1112A ?=?-? ,22b ?=?00110001211221224T A M A H -?- ? =? ?- ?-? 2226b q c ，? =? ?_?,y w v ?=?,u z x ?=?解法一:根據(jù)經(jīng)典的Lemke互補轉(zhuǎn)軸算法,在引入人工變量后，經(jīng)過4次迭代過程，得到互補基本可行解21446(0,0,0,(,0,5555T T w z =,因此得到K-T點1246(,(,55x x =。解法二:利用改進(jìn)的算法Tab.4-8 The initial table of improved Lemke algorithm基向

21、量 w 1 w 2 w 3 w 4 z 1 z 2 z 3 z 4 q w 1 1 0 0 0 0 0 1 1 2 w 2 0 1 0 0 0 0 -1 2 2 w 3 0 0 1 0 -1 1 -2 2 -2 w 4 0 0 0 1 -1 -2 2 -4* -6 因為(0(0(04min 0ii q q q =，選取4z為進(jìn)基變量，則4w為出基變量。以(044d為主元，經(jīng)主元消去 法得到表4-9改進(jìn)的Lemke算法的迭代表1Tab.4-9 The first iterated table of improved Lemke algorithm基向量 w 1 w 2 w 3 w 4 z 1 z

22、 2 z 3 z 4 q w 1 1 0 0 1/4 -1/4 -1/2 3/2 0 1/2 w 2 0 1 01/2 -1/2 -1 0 0 -1 w 3 0 0 1 1/2 -3/2 0 -1 0 -5 z 4 0 0 0 -1/4 1/4 1/2 -1/2 1 3/2顯然基向量為 12341(,w ,(,-1,-5,3/22w w z =,2w和3w分量為負(fù)數(shù),得3w的互補變量最大。根據(jù)最大互補規(guī)則，則3w的互補變量進(jìn)基,即3z進(jìn)基,3w出基。取(133d為主元，進(jìn)行主元消去得到表4-10改進(jìn)的Lemke算法的迭代表2Tab.4-10 The sec ond iterated table

23、 of improved Lemke algorithm基向量 w 1 w 2 w 3 w 4 z 1 z 2 z 3 z 4 q w 1 1 0 3/2 1 -5/2* -1/2 0 0 -7 w 2 0 1 01/2 -1/2 -1 0 0 -1 z 3 0 0 -1 -1/2 3/2 0 1 0 5 z 4 0 0 -1/2 -1/2 1 1/2 0 1 4顯然基向量為1234(,z ,(7,-1,5,4w w z =-,1w和2w分量為負(fù)數(shù)，則1w的互補變量最大，則1z進(jìn)基,1w出基。取(211d為主元，進(jìn)行主元消去得到表4-11改進(jìn)的Lemke算法的迭代表3Tab.4-11The f

24、irst iterated table of improved Lemke algorithm基向量 w1w2w3w4z1z2z3z4 qz1-2/50 -3/5 -2/5 1 1/5 0 0 14/5 w2 -1/51-3/103/10 0 -9/100 0 2/5 z33/50 -1/101/10 0 -3/101 0 4/5 z42/50 1/10 -1/100 3/10 0 1 6/5得到基向量123414246(z，,(,5555w z z=，各分量均非負(fù)則停止計代過程。即經(jīng)過三次迭代過程，得到互補基本可行解21446(ODaOC0,5555w z=,因此得到K-T點1246(,(,

25、55x x=。5結(jié)論本文通過對經(jīng)典的Lemke互補轉(zhuǎn)軸算法求解凸二次規(guī)劃問題的分析，找到了 Lemke算法的局限性。根據(jù)Lemke算法求解線性互補問題(LCP問題，對經(jīng)典的 Lemke算法的迭代過程進(jìn)行了修正，提出了一種改進(jìn)的Lemke算法。這種算法能有 效地克服了本身解的局限性，并能減少凸二次規(guī)劃問題的迭代過程。根據(jù)凸二次規(guī) 劃的Lemke算法及線性互補問題的描述，證明了改進(jìn)算法的可行性。通過利用改進(jìn) 的Lemke算法對凸二次規(guī)劃問題進(jìn)行求解，對改進(jìn)算法與經(jīng)典的Lemke算法進(jìn)行比 較和分析。數(shù)值結(jié)果表明：改進(jìn)算法能有效地克服了本身解的局限性，并能減少凸二 次規(guī)劃問題的迭代過程。本文給出了求

26、解凸二次規(guī)劃問題的一種 Lemke算法的改進(jìn)算法。該算法在迭 代時不需要引入人工變量，把特殊的凸二次規(guī)劃求解簡單化，這使得求解過程靈活、 方便。算例表明，所提算法在求解相應(yīng)問題時是簡便而有效的。參考文獻(xiàn)1Y.Y.Nie,S.0.Magu ndho.A QUASL-SIMPLEX METHOD FOR STRICTLYCONVEX QUADRATICPROGRAMMING.MINI-MICRO SYSTEM, 2001,22(12 張文武，華中生.一種改進(jìn)的求解含等式約束凸二次規(guī)劃問題的Lemke算法J.中國科學(xué)技術(shù)大學(xué)學(xué)報，2004.3 王浚嶺.一種新的可分凸二次規(guī)劃的不可行內(nèi)點算法J.應(yīng)用數(shù)學(xué)，2004, 17(1.4 張藝.線性約束凸二次規(guī)劃的一個原始對偶內(nèi)點算法J寧波大學(xué)學(xué)報(理工版,2004, 17(1.5 趙社峰，費浦生，李健.凸二次規(guī)劃的投影收縮算法J.武漢大學(xué)學(xué)報(理學(xué)版,2001,47(1.張勝等式約束二次規(guī)劃問題的迭代解法J.南京師范大學(xué)報(自然科學(xué)版,2000, 23(3.7徐君開，葉福玲.求解線性互補問題的Lemke算法的一種改進(jìn)J.福州大學(xué)學(xué) 報伯然科學(xué)版,1997, 25(6.The