線性互補(bǔ)問題及其算法畢業(yè)論文

1、線性互補(bǔ)問題及其算法摘要互補(bǔ)問題與數(shù)學(xué)規(guī)劃、經(jīng)濟(jì)學(xué)、對(duì)策論、力學(xué)、變分學(xué)、隨機(jī)最優(yōu)制等學(xué)科關(guān)系密切，在科學(xué)研究和工程技術(shù)各領(lǐng)域有著廣泛的應(yīng)用。從二十世紀(jì)60年代以后，互補(bǔ)問題的理論和算法研究一直是應(yīng)用數(shù)學(xué)和計(jì)算數(shù)學(xué)領(lǐng)域中的一個(gè)熱點(diǎn)課題，有關(guān)互補(bǔ)問題的算法不斷涌現(xiàn)。互補(bǔ)問題可以分為線性互補(bǔ)問題和非線性互補(bǔ)問題。對(duì)互補(bǔ)問題的研究又可以分為理論和算法。前者主要研究問題解的存在性、唯一性、穩(wěn)定性以及靈敏度分析等性質(zhì)。后者集中研究如何構(gòu)造有效算法及其理論分析。本文旨在有效算法方面的研究。本篇文章主要介紹線性互補(bǔ)問題基本概念、算法；二次規(guī)劃問題基本概念、理論。重點(diǎn)探討二次規(guī)劃問題與線性互補(bǔ)問題的關(guān)系，以及

2、如何利用二次規(guī)劃的方法求解線性互補(bǔ)問題。關(guān)鍵詞：線性互補(bǔ)問題，二次規(guī)劃，算法，互補(bǔ)問題和二次規(guī)劃的關(guān)系 abstractthe theory and algorithm of the linear complementary problem (lcp) is widely used in mathematics programming and. as lcp is related to nonlinear scientific knowledge and many practical problems, the theory and algorithm of the lcp was a hot

3、 task since 20th 60, and many algorithms about lcp were generated.the research of the lcp included theory and algorithm. the former include existence, uniqueness and stabilize of the problem. the later was concentrate on how to construct efficient algorithm and the analysis about the theory. in this

4、 paper we were mainly talking about the algorithm of lcp.in this paper, we were mainly introduced the basic conception and algorithm of lcp, and the basic conception and algorithm of quadratic programming problems.key words: linear complementary problem, quadratic programming problem, algorithm, the

5、ory, the relationship of lcp and qpp目錄摘要1目錄3引言4第一章：互補(bǔ)問題51.1 互補(bǔ)問題介紹51.2 互補(bǔ)問題的算法介紹8第二章：二次規(guī)劃142.1 庫(kù)恩塔克條件：142.2 二次規(guī)劃14第三章：線性互補(bǔ)問題與二次規(guī)劃問題173.1 用線性互補(bǔ)問題解決二次規(guī)劃問題173.2 解線性互補(bǔ)問題的lemke方法183.3 用二次規(guī)劃解決線性互補(bǔ)問題233.4 解二次規(guī)劃問題的起作用集方法23第四章：應(yīng)用舉例論文總結(jié)27參考文獻(xiàn)28致謝30引言互補(bǔ)問題是運(yùn)籌學(xué)與計(jì)算數(shù)學(xué)的一個(gè)交叉研究領(lǐng)域。作為一類新的數(shù)學(xué)模型，互補(bǔ)問題首先是由著名運(yùn)籌學(xué)家、數(shù)學(xué)規(guī)劃的創(chuàng)始人g.b

6、.dantzig和他的學(xué)生r.w.cottle于1963年提出，并很快引起了當(dāng)時(shí)運(yùn)籌學(xué)界和應(yīng)用數(shù)學(xué)界的廣泛關(guān)注和濃厚興趣，許多人參與了這類問題的研究。由于與最優(yōu)化、變分不等式、平衡問題、對(duì)策論、不動(dòng)點(diǎn)理論等分支的緊密聯(lián)系，以及在力學(xué)、工程、經(jīng)濟(jì)、交通等許多實(shí)際部門的廣泛應(yīng)用，互補(bǔ)問題越來越顯示其重要性，這激勵(lì)了人們對(duì)其理論與算法的進(jìn)一步研究，出現(xiàn)了20世紀(jì)90年代以來的研究高潮。 互補(bǔ)問題的求解方法根據(jù)模型為線性和非線性分為兩大類：(i)對(duì)線性互補(bǔ)問題，有直接方法(如lemke法，cottle-dentzig法)和迭代法(如mangsarian法)；(ii)對(duì)非線性互補(bǔ)問題，有不動(dòng)點(diǎn)法，同倫法

7、，投影法，newton法。在本文中，第一章，我們簡(jiǎn)要介紹互補(bǔ)問題和幾個(gè)互補(bǔ)問題的經(jīng)典算法；第二章我們介紹了二次規(guī)劃問題的基本概念和kkt條件；第三章，旨在探究線性互補(bǔ)問題與二次規(guī)劃的問題的關(guān)系,并在此基礎(chǔ)上，討論如何利用線性互補(bǔ)問題的方法求解二次規(guī)劃問題、以及利用二次規(guī)劃問題的方法求解線性互補(bǔ)問題。這也是本文的重點(diǎn)內(nèi)容。第一章 互補(bǔ)問題1.1 互補(bǔ)問題介紹互補(bǔ)問題是運(yùn)籌學(xué)與計(jì)算數(shù)學(xué)的一個(gè)交叉研究領(lǐng)域，與數(shù)學(xué)規(guī)劃、經(jīng)濟(jì)學(xué)、對(duì)策論、力學(xué)、變分學(xué)、隨機(jī)最優(yōu)制等學(xué)科關(guān)系密切，在科學(xué)研究和工程技術(shù)各領(lǐng)域有著廣泛的應(yīng)用?；パa(bǔ)問題自20世紀(jì)60年代開始發(fā)展到現(xiàn)在，無論在理論還是在算法研究上都取得了豐碩的成果

8、。 互補(bǔ)問題的研究又可以分為理論和算法。前者主要研究問題解的存在性、唯一性、穩(wěn)定性以及靈敏度分析等性質(zhì)。后者集中研究如何構(gòu)造有效算法及其理論分析。本文旨在有效算法方面的研究。 我們首先給出互補(bǔ)問題的定義：定義1.1（線性互補(bǔ)問題）：給定一個(gè)的矩陣，q是一個(gè)維向量，找到一個(gè)向量w和z使得： （1.1）； （1.2）； （1.3）在這里，表示一對(duì)互補(bǔ)向量。線性系統(tǒng)的一個(gè)解叫做互補(bǔ)問題可行解。另外，如果對(duì)變量都適合，是（1.1）和（1.2）的基可行解，則這個(gè)解也叫做互補(bǔ)問題可行基解。定義1.1（非線性互補(bǔ)問題）： 求一個(gè)p維向量x，使得：， （1.4）； （1.5） （1.6）其中，是：連續(xù)可微。互

9、補(bǔ)問題與最優(yōu)化問題關(guān)系密切，最優(yōu)化中的許多問題都可以轉(zhuǎn)化為互補(bǔ)問題求解，下面分別給出說明。（1）線性規(guī)劃考慮原始線性規(guī)劃問題： （1.7）其中：。它的對(duì)偶問題為： （1.8）設(shè)，分別是和的可行解，則，同為最優(yōu)解的充要條件是：；設(shè)：，則：；在，同為最優(yōu)解的條件下，可以構(gòu)造如下的互補(bǔ)問題：求，使得，且。是的解當(dāng)且僅當(dāng)，是和的最優(yōu)解。（2）二次規(guī)劃考慮二次規(guī)劃問題：其中，。引入松弛變量，使得。則由條件，存在向量乘子，使得：將上面的條件改寫成如下形式：若令，則條件等價(jià)地可以寫為：求，使得，且，而這正是線性互補(bǔ)問題的形式。（3）非線性規(guī)劃考慮非線性規(guī)劃其中連續(xù)可微，。令則由約束最優(yōu)化的條件：將上面的式子

10、展開寫成：若令，則條件等價(jià)于：求，使得，且；這也是互補(bǔ)問題。1.2 互補(bǔ)問題的算法介紹我們簡(jiǎn)要介紹幾個(gè)互補(bǔ)問題的經(jīng)典算法和近幾年的解互補(bǔ)問題的發(fā)展情況，對(duì)我們以后分析和解決互補(bǔ)問題有很大的幫助。主要有光滑方程法、可微的無約束優(yōu)化法、glp投影法、內(nèi)點(diǎn)法。1.光滑方程法：這類方法就是把互補(bǔ)問題轉(zhuǎn)化為一個(gè)與之等價(jià)的光滑方程組，然后用newton類型法求解。mangasarian于1976年首先提出這種方程族（3）（4）這里是指的第個(gè)分量，是一個(gè)嚴(yán)格遞增的函數(shù)，滿足，稱為函數(shù)或者勢(shì)函數(shù)，mangasarian證明了兩個(gè)重要結(jié)論：定理1： 假設(shè)由（4）定義，則；進(jìn)一步，解。定理1： 假設(shè)解且在連續(xù)可微

11、，如果下列條件成立（a）是非退化的，即；（b）在點(diǎn)的jacobian矩陣非奇異；（c）連續(xù)可微、嚴(yán)格遞增，且當(dāng)時(shí)，；那么，在點(diǎn)的jacobian矩陣非奇異。顯然，滿足定理2（c）的函數(shù)很多，例如光滑方程法：，此時(shí)的函數(shù)。于是我們可再生出許多光滑方程，并能用newton程序解之。當(dāng)然，滿足定理2條件的解點(diǎn)附近，算法有超線性收斂性。為了保證大范圍收斂性，waston建立了一個(gè)同倫算法（取）。subbramanian則提出一個(gè)帶阻尼因子的gauss-newton法（取），迭代格式為：；（5）這里為步長(zhǎng)，由精確armijo搜索求得；，；表示適當(dāng)維數(shù)的單位矩陣；。ferris和lucidi用非單調(diào)線性搜

12、索技術(shù)改進(jìn)程序(5)，得到好的數(shù)值結(jié)果最近本文第一作者和subramanian合作證明：在連續(xù)可微時(shí)，算法(5)是大范圍收斂的；在定理2的條件下，其點(diǎn)列局部超線性收斂?；诤瘮?shù)(4)，kanzow考慮下面2n階光滑方程組（6）他給出了jacobian矩陣在的非解點(diǎn)處存在逆的幾個(gè)充分條件。顯然，算法的大范圍收斂性與水平集（7）的有界性有密切聯(lián)系。對(duì)此，文64也做了研究。tseng則把（6）變成方程；（8）進(jìn)而研究和的增長(zhǎng)行為。雖然這類方法有一定的優(yōu)越性。但缺點(diǎn)是， 即使一個(gè)線性互補(bǔ)問題，轉(zhuǎn)化后的方程往往是非線性的，且非線性程度較高這就導(dǎo)致理論與計(jì)算的復(fù)雜化。下面的一類方法恰能彌補(bǔ)這一不足。2可微

13、的無約束優(yōu)化法這是把互補(bǔ)問題轉(zhuǎn)化為一個(gè)與之等價(jià)的可微無約束優(yōu)化問題，然后用某種大范圍或newton類型法求解由于無約束優(yōu)化法較為成熟，因此，對(duì)這類方法的研究重心在于如何轉(zhuǎn)化上。mangasarian和solodov又先于他人，給出一個(gè)可微的勢(shì)函數(shù)這里表示2-范數(shù)。 稱為隱lagrange函數(shù)。他們證明了定理6 對(duì)，且解實(shí)際上， 可由可微的函數(shù)；并取向量1-范數(shù)生成，即文7研究了穩(wěn)定點(diǎn)與極小點(diǎn)之間的關(guān)系，得到定理7 假設(shè)f是可微的，且正定，則是(17)的穩(wěn)定點(diǎn)是的一個(gè)解。文8的9做了統(tǒng)一處理。基于fukushimp的結(jié)果，中國(guó)科學(xué)院計(jì)算數(shù)學(xué)所青年學(xué)者彭積明10給出了變分問題的可微無約束優(yōu)化再生。

14、有趣的是，它恰是隱lagrange函數(shù)在變分問題中的推廣。 自此至今的三年間， 出現(xiàn)了構(gòu)造函數(shù)熱。關(guān)于這個(gè)方向的綜述，可見fukushima的文章11最近，對(duì)可微無約束優(yōu)化再生的研究興趣轉(zhuǎn)向增加非負(fù)約束，因?yàn)閷?shí)際計(jì)算表明，僅用無約束優(yōu)化求出的的解并不理想。為此給出一個(gè)可行的信賴域方法；提出一降勢(shì)內(nèi)點(diǎn)法。這方面的文獻(xiàn)陸續(xù)增多，有12，13等3glp 投影法就是基于goldsteinlevitin-polyak求解凸規(guī)劃的梯度投影法思想，求解互補(bǔ)問題。基本迭代格式為這里 為步長(zhǎng)。然而它的收斂性需要是強(qiáng)單調(diào)的假設(shè)。為此， korpelevich(1976)提出外梯度法， 即它的收斂性僅要求單調(diào)且解集

15、。sun14,15應(yīng)用armijo搜索技術(shù)得到，在是偽單調(diào)且的假設(shè)下，迭代點(diǎn)列收斂到。雖然這類方法最多只有線性收斂速度，但它運(yùn)算量小，存儲(chǔ)量小，保稀疏性。因此近幾年又有新的發(fā)展。4內(nèi)點(diǎn)法這是把互補(bǔ)問題轉(zhuǎn)化為一個(gè)與之等價(jià)的非負(fù)約束方程組，然后用newton類型法求解。它的研究起源于karmarkar的求解線性與凸二次規(guī)劃的內(nèi)點(diǎn)法，也是這種方法的自然延伸。其研究高潮在1990年前后，至今取得極大成功。這方面的文獻(xiàn)很多很多，大都集中在雜志siam joptimization， mp， jota， math.operres上。 現(xiàn)在來考察內(nèi)點(diǎn)法的基本思想。令，則互補(bǔ)問題(1)可轉(zhuǎn)化為：這里。顯然， (

16、24)是一個(gè)帶有非負(fù)約束的2n階非線性方程組。當(dāng)時(shí)，僅第二個(gè)方程是非線性的，且有特殊形式的表達(dá)式。容易證明， 當(dāng)是函數(shù)時(shí)， jacobian矩陣是非奇異的。 因此，在迭代中可取newton方向傲為搜索方向。給定點(diǎn)，內(nèi)點(diǎn)法的一般迭代格式為： (25) (26)這里是由經(jīng)過一個(gè)微小擾動(dòng)而得，其目的是調(diào)節(jié)迭代的收斂速度；為步長(zhǎng)，它的取法使新點(diǎn)，且效益函數(shù)有一定量的下降。如果在迭代過程中能保證，則稱為可行內(nèi)點(diǎn)法； 否則稱為不可行內(nèi)點(diǎn)法。如果取的自然勢(shì)函數(shù)作為效益函數(shù)，則稱為路徑跟蹤法；如果取某種對(duì)數(shù)函數(shù)作為效益函數(shù)，則稱為降勢(shì)函數(shù)法。對(duì)于可行內(nèi)點(diǎn)法，它首先由kojima，mizuno和yoshise提

17、出,限于篇幅，不再一一舉例。內(nèi)點(diǎn)法的收斂結(jié)果大致有：(1)大范圍收斂性：若單調(diào)，可行集存在內(nèi)點(diǎn)，那么由內(nèi)點(diǎn)法產(chǎn)生的迭代點(diǎn)列滿足且q-線性(2)局部超線性收斂：假設(shè)單調(diào)且可行集存在內(nèi)點(diǎn)若是的一個(gè)極限點(diǎn)且有某種正則性，則或者超線性收斂于零或。(3)多項(xiàng)式復(fù)雜性若單調(diào)且可行集存在內(nèi)點(diǎn)，那么對(duì)可行內(nèi)點(diǎn)法，最好的復(fù)雜性界為；對(duì)不可行內(nèi)點(diǎn)法，最好的復(fù)雜性界為。總之，關(guān)于1994年以前內(nèi)點(diǎn)法的情況，請(qǐng)見新書16。這三年，關(guān)于內(nèi)點(diǎn)法的文章不多，在此僅向讀者推薦幾篇文獻(xiàn) bonnans和gonzaga17證明了求解內(nèi)點(diǎn)法的迭代點(diǎn)列收斂性。 sun和zhao18，19提出了一個(gè)求解的長(zhǎng)步內(nèi)點(diǎn)法，它僅用一次newt

18、on步可得到局部二次收斂性。 tseng20借用非內(nèi)點(diǎn)法的思想改進(jìn)中心路徑鄰域，并引進(jìn)積極約束集策略，使算法的局部超線性收斂性不需要嚴(yán)格互補(bǔ)條件。目前，人們正在發(fā)展用內(nèi)點(diǎn)法求解半定線性規(guī)劃。第二章 二次規(guī)劃2.1 庫(kù)恩塔克條件：在介紹二次規(guī)劃之前，我們先引入條件，因?yàn)閹?kù)恩塔克 條件是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是確定某點(diǎn)為最 優(yōu)點(diǎn)的必要條件。只要是最優(yōu)點(diǎn)，就必要滿足這個(gè)條件。但一般說，它并不是充分條件，因而滿足這個(gè)條件的點(diǎn)不一定是最優(yōu) 點(diǎn)（對(duì)于凸規(guī)劃，它既是最優(yōu)點(diǎn)存在的必要條件，同時(shí)也是充分條件）。庫(kù)恩塔克 條件的敘述如下：設(shè)是非線性規(guī)劃的極小值點(diǎn)，而且在點(diǎn)的各起作用約束的梯度線性無

19、關(guān)，則存在向量，使下列條件成立： （2.1）條件（2.1）稱為條件。滿足這個(gè)條件的點(diǎn)（它當(dāng)然也滿足非線性規(guī)劃的所有約束條件）稱為點(diǎn)。2.2 二次規(guī)劃若某些非線性規(guī)劃問題的目標(biāo)函數(shù)為自變量的二元函數(shù)，約束條件又全是線性的，就成這種規(guī)劃為二次規(guī)劃問題。二次規(guī)劃為是非線性規(guī)劃中比較簡(jiǎn)單的一類，比較容易求解。由于很多方面的問題都可以抽象為二次規(guī)劃的模型，而且它和線性規(guī)劃又有直接聯(lián)系，因而我們此處專門提出來說明一下。二次規(guī)劃的數(shù)學(xué)模型可表述如下：（2.1）式的右端的第二項(xiàng)為二次型。如果該二次型為正定（或者半正定），則目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)（或者凸函數(shù)）；此外，二次型的可行域?yàn)橥辜蚨?，上述?guī)劃屬于凸規(guī)劃

20、（在極大值問題中，如果上述二次型為負(fù)定或半負(fù)定，則也屬于凸規(guī)劃）。在文獻(xiàn)【運(yùn)籌學(xué)】中第六章已經(jīng)指出，凸規(guī)劃的局部極值即為其全局極值。對(duì)這種問題來說，條件不但是極值點(diǎn)存在的必要條件，而且是充分條件。將條件的第一個(gè)條件應(yīng)用于二次規(guī)劃（2.2）（2.4）中，并用y代替條件中的，即可得到在（2.3）式中引入松弛變量，（2.3）式即變?yōu)椋俣ǎ涸賹l件的第二個(gè)條件應(yīng)用于上述二次規(guī)劃，并考慮（2.6）式，這樣就得到：此外還有：聯(lián)立（2.5）式和（2.6）式，如果得到的解也滿足（2.7）式和（2.8）式，則這樣的解就是原二次規(guī)劃問題的解。但是，在（2.7）式，可能為正，也可能為負(fù)。為了方便于求解，先引入人

21、工變量（，其前面的符號(hào)可以取正或負(fù)，以便得出可行解）。這樣（2.5）式就變成了：其中是符號(hào)函數(shù)，當(dāng)時(shí)，；當(dāng)時(shí)，。這樣一來，可立即得到初始基本可行解如下：但是，只有當(dāng)時(shí)才能得到原來問題的解，故必須對(duì)上述問題進(jìn)行修正，從而得到如下線性規(guī)劃問題：該線性規(guī)劃尚應(yīng)滿足（2.7）式。這相當(dāng)于說，不能使和（對(duì)于每一個(gè)）同時(shí)為基變量。解線性規(guī)劃問題（2.10），若得到最優(yōu)解：則就是原問題的最優(yōu)解。第三章 二次規(guī)劃問題與線性互補(bǔ)問題3.1 利用線性互補(bǔ)問題求解二次規(guī)劃問題現(xiàn)在考慮二次規(guī)劃問題（3.1）其中h是n階對(duì)稱矩陣，c是n維列向量，a是矩陣，b是m維列向量。引入乘子y和u，定義lagrange函數(shù)（3.2

22、）再引入松弛變量，使得（3.3）這樣根據(jù)（3.2）式，可將問題（3.1）的條件寫成（3.4）記：， ，于是，（3.4）式可以寫成下列形式：（3.5）（3.6）其中w，z，q均為維列向量，m是維矩陣。（3.5）和（3.6）合稱為線性互補(bǔ)問題，它的每一個(gè)解都具有這樣的特征：解的個(gè)分量中，至少有個(gè)取零值，而且其中沒對(duì)變量中至少有一個(gè)為零，其余分量均是負(fù)數(shù)，下面研究怎樣求出線性互補(bǔ)問題的解。定義3.1 設(shè)是（3.5）式的一個(gè)基本可行解，而且每個(gè)互補(bǔ)變量對(duì)中有一個(gè)變量是基變量，則稱互補(bǔ)基本可行解。這樣，求二次規(guī)劃點(diǎn)的問題就轉(zhuǎn)化為求互補(bǔ)基本可行解。3.2 求解線性互補(bǔ)問題的lemke方法現(xiàn)在介紹求互補(bǔ)可行

23、解的lemke方法。我們分兩種情形討論：（1） 如果，則就是一個(gè)互補(bǔ)基本可行解。（2） 如果不滿足，則引入人工變量，令其中是分量全為1的維列向量。在求解（3.7）（3.9）式之前，先引入準(zhǔn)互補(bǔ)基本可行解的概念。定義3.2 設(shè)是（3.7）、（3.8）、（3.9）式的一個(gè)可行解，并且滿足下列條件，則稱是準(zhǔn)互補(bǔ)基本可行解。（1）是（3.7）和（3.8）的一個(gè)基本可行解；（2）對(duì)某個(gè)，和都不是基變量；（3）是基變量，每個(gè)互補(bǔ)變量對(duì)中恰好有一個(gè)變量是基變量。下面用主消去法求準(zhǔn)互補(bǔ)基可行解。首先，令；則是一個(gè)準(zhǔn)互補(bǔ)基本可行解，其中和式基變量，其余變量為非基變量。以這個(gè)解為起始解，用主元消去法求新的準(zhǔn)互補(bǔ)基

24、本可行解，力圖用這種方法迫使變?yōu)榉腔兞俊榱舜_?？尚行裕x擇主元時(shí)要遵守下面兩條規(guī)則：（1） 若（或者）離基，則（或者）進(jìn)基；（2） 按照單純形法中的最小比例規(guī)則確定立即變量。這樣就能實(shí)現(xiàn)從一個(gè)準(zhǔn)互補(bǔ)基本可行解到另一個(gè)互補(bǔ)基本可行解可行解的轉(zhuǎn)換，直至得到互補(bǔ)基本可行解，即變?yōu)榉腔兞浚蛘哂桑?.7）、（3.8）、（3.9）式所定義的可行域無界的結(jié)論。lemke方法的計(jì)算步驟：計(jì)算步驟如下：（1） 若，則停止計(jì)算，就是一個(gè)互補(bǔ)基本可行解；否則，用表格形式表示方程組（3.7），設(shè)取s行為主行，為對(duì)應(yīng)的主列，進(jìn)行主元消去，令。（2） 設(shè)現(xiàn)在行列表中變量下面的列為。若，則停止計(jì)算，得到（3.7）式

25、和（3.8）式的可行域的極方向；否則，按最小比例值規(guī)則確定指標(biāo)r，使：；（3） 設(shè)r行的基變量為或者（對(duì)于某個(gè)），變量進(jìn)基，以r行為主行，對(duì)應(yīng)的列為主列，進(jìn)行主元消去。如果離基變量是，則令；如果離基變量是，則令。轉(zhuǎn)到步驟（2）。（4） 變量進(jìn)基，離基。以r行為主行，對(duì)應(yīng)的列為主列，進(jìn)行主元消去，得到互補(bǔ)可行解，停止計(jì)算。3.3 利用二次規(guī)劃求解互補(bǔ)問題考慮互補(bǔ)問題：求一個(gè)p維向量x，使得：； （3.10）， （3.11） （3.12）其中，m是p階對(duì)稱矩陣，q是p維向量；是：連續(xù)可微。二次規(guī)劃問題（3.13）比較兩者可以明顯看出有以下結(jié)論：因?yàn)椋?.13）中約束條件保證二次規(guī)劃問題一定存在最

26、優(yōu)解，但是，當(dāng)最優(yōu)解f*0時(shí)，線性互補(bǔ)問題無解，當(dāng)f*=0，則線性互補(bǔ)問題一定有解。因此，對(duì)于線性互補(bǔ)問題就可以轉(zhuǎn)化為討論二次規(guī)劃的問題。然后，下面我們?cè)俳榻B一下二次規(guī)劃的簡(jiǎn)單的算法起作用集解法。3.4 解二次規(guī)劃問題的起作用集方法1. 起作用集方法的分析推導(dǎo)：考慮具有不等式約束的二次規(guī)劃問題：（3.14）其中是n階對(duì)稱正定矩陣，c是n維列向量，a是矩陣，秩為m， b是m維列向量，。由于不等式約束的出現(xiàn)，問題（3.14）不能直接使用消元法和lagrange方法求解。解決這個(gè)問題的策略之一，是起作用集方法將它轉(zhuǎn)化為求解等式的約束問題。設(shè)在地k次迭代中，已知可行點(diǎn)，在該點(diǎn)起作用約束集用表示。這時(shí)需

27、要求解等式約束問題（3.15）其中表示矩陣a的第i行。也是在處起作用約束函數(shù)的梯度。為方便起見，現(xiàn)將坐標(biāo)原點(diǎn)移至，令則：（3.16）于是問題（3.15）就變成求校正量的問題（3.17）解二次規(guī)劃問題（3.17），求出最優(yōu)解，然后區(qū)別不同情形，決定下面應(yīng)采取的步驟。如果是可行點(diǎn)，且，則在第次迭代中，已知點(diǎn)取作如果不是可行點(diǎn)，則列方向并沿搜索，令；現(xiàn)在分析怎樣確定沿方向的步長(zhǎng)。根據(jù)保持可行性的要求，的值應(yīng)使得對(duì)于每一個(gè)成立（3.18）由于是可行點(diǎn)，因此由上式可知，當(dāng)時(shí)，對(duì)于任意的非負(fù)數(shù)，（3.18）總成立；當(dāng)時(shí)，只要取正數(shù)對(duì)于每一個(gè)，（3.18）總成立。記由于是問題（3.17）的最優(yōu)解，為在第k次

28、迭代中得到較好的可行點(diǎn)，應(yīng)?。?.19）并令如果（3.20）則在點(diǎn)，有因此，在處，為起作用約束。這時(shí)，把指標(biāo)p加入，得到在的起作用約束指標(biāo)集。如果，則是問題（3.15）的最優(yōu)解。這時(shí)應(yīng)判斷是否為問題（3.14）的最優(yōu)解。為此，需用（3.20）式計(jì)算起作用約束乘子。如果這些，則是問題（3.14）的點(diǎn)。由于（3.14）是凸規(guī)劃，因此是問題（3.14）的最優(yōu)解。如果存在，使得，則不可能是最優(yōu)解?？梢则?yàn)證，當(dāng)時(shí)，在處存在可行下降方向。比如，是起作用約束系數(shù)矩陣，且滿秩，令方向是單位向量，對(duì)應(yīng)下標(biāo)q的分量為1，則有因此d是在處的下降方向。容易驗(yàn)證d也是可行方向。當(dāng)時(shí)，把下標(biāo)q從中刪除。如果有幾個(gè)乘子同時(shí)

29、為負(fù)，令將對(duì)應(yīng)的約束從起作用約束集中去掉，再解問題（3.17）2. 起作用約束集方法計(jì)算步驟計(jì)算步驟如下：（1） 給定初始可行點(diǎn)，相應(yīng)的起作用約束指標(biāo)集為，置（2） 求解問題（3.17），設(shè)其最優(yōu)解為。若，則進(jìn)入步驟（5）；否則，進(jìn)行步驟（3）（3） 令，由（3.19）式確定，令，計(jì)算式。（4） 若，則置，返回步驟（2）；若，記點(diǎn)處起作用約束指標(biāo)集為，置，進(jìn)行步驟（5）（5） 用（3.20）式計(jì)算對(duì)于起作用約束的lagrange乘子，設(shè)若，則停止計(jì)算，得到最優(yōu)解；否則，從中刪除q，返回步驟（2）。 第四章 應(yīng)用舉例例1.用lemke方法求解下面例題：解：有題意可得：，；線性互補(bǔ)問題為：引入人工

30、變量，建立下表：待添加的隱藏文字內(nèi)容2 1 0 0 0 0 0 1 1 -1 0 1 0 0 0 0 -1 2 -10 0 1 0 -1 1 -2 2 -10 0 0 1 -1 -2 2 -4 22-2-6因?yàn)椋?，主元，已?jīng)用方括號(hào)括起來，經(jīng)主元消去得到： 1 0 0 -1 1 2 -1 5 0 0 1 0 -1 1 2 -3 6 00 0 1 -1 0 3 -4 00 0 0 -1 1 2 -2 4 18846在這里， 進(jìn)基，離基，進(jìn)入下一迭代，得到下表： 1 0 1 0 0 0 1 -1 0 1 -1 1 0 00 0 0 1 00 0 1 0 0 12，根據(jù)最小比例規(guī)則，進(jìn)基，離基；

31、進(jìn)入下一迭代，得到下表： 0 1 1 1 0 1 0 這里，根據(jù)最小比例規(guī)則，進(jìn)基，離基，最終得到下表結(jié)果， 0 0 1 1 0 1 0 0 1 0 1 得到互補(bǔ)基本可行解：因此可以得到二次規(guī)劃問題的最優(yōu)解為。例2. 用起作用集方法方法求解下面例題：論文總結(jié)互補(bǔ)問題是運(yùn)籌學(xué)與計(jì)算數(shù)學(xué)的一個(gè)交叉研究領(lǐng)域。作為一類新的數(shù)學(xué)模型，互補(bǔ)問題首先是由著名運(yùn)籌學(xué)家、數(shù)學(xué)規(guī)劃的創(chuàng)始人g.b.dantzig和他的學(xué)生r.w.cottle于1963年提出，并很快引起了當(dāng)時(shí)運(yùn)籌學(xué)界和應(yīng)用數(shù)學(xué)界的廣泛關(guān)注和濃厚興趣，許多人參與了這類問題的研究。由于與最優(yōu)化、變分不等式、平衡問題、對(duì)策論、不動(dòng)點(diǎn)理論等分支的緊密聯(lián)系，

32、以及在力學(xué)、工程、經(jīng)濟(jì)、交通等許多實(shí)際部門的廣泛應(yīng)用，互補(bǔ)問題越來越顯示其重要性，這激勵(lì)了人們對(duì)其理論與算法的進(jìn)一步研究，出現(xiàn)了20世紀(jì)90年代以來的研究高潮。本篇文章主要介紹線性互補(bǔ)問題及其算法。首先，本文簡(jiǎn)要給出線性互補(bǔ)問題基本概念、若干個(gè)經(jīng)典算法；二次規(guī)劃問題基本概念和最優(yōu)性理論；重點(diǎn)探討二次規(guī)劃問題與線性互補(bǔ)問題的關(guān)系，以及如何利用二次規(guī)劃的方法求解線性互補(bǔ)問題。自己可以再加些內(nèi)容參考文獻(xiàn)1 運(yùn)籌學(xué)教材編寫組.運(yùn)籌學(xué)（修訂版）.北京：清華大學(xué)出版社，19902 陳寶林，最優(yōu)化理論與算法（第2版）.清華大學(xué)出版社.20053 rockafellar, r. t. c onvex anal

33、ys is. princeton univ. press,princeton, 19704 isac g. complementarity problems. lecture notes in matheanatics, springer-verlag, berlin, 1992.5 cottle r w, pang j s and stone r ethe linear complementary problem. academic press, boston. 1992.6 kangow c, yamehita n and fukushima m. new ncp-functions an

34、d their properties. jota, 1997, 94, 115-1357 yamashita nand fukushima mon stationary points of the implicit lngrangian for nonline complementaftty problems jota 1995，84：653-6638 kanzow cnonlinear complementaxity aunconstr2med optimization jota，1996，88(1)：139-1559 tseng yamashita n and fukushima m eq

35、uivalence of complementarity pro blems to diferentiable minimization：a unified approachsiam optimization,to appear10 pei1g j m equiw lece of variational inequality problem s to unconstrained optimization technical report，state key laboratory of scientific and engineering computing，academia sinicabei

36、jing，china，1995，to appearin math preforming11 fukushima merit function for wriational inequality and complementarity problems in diplilog and giannessl feds nonlinear clptimizntion and applications plenum press，new york，1996，155-17012 peng j m derivative-free methods for monotone variational inequal

37、ity and complementarity problems technical report1 state key laboratory of scientific and engineering computing academia sinica，bering china，199713 solodov m v-stationary points of bound constrained minimization reform ulations of complementaity problemsjota 199794：11513214 sun d-a new step skill fur solving a class of nonlinear projection eqttations jcoput math，1995，13(4)：357-36815 sun algorithms and convergence analysis for nonsmooth optimization and nonsmooth equ