非線性等式約束優(yōu)化問題的一類既約Hessian算法研究_圖文

1、首都師范大學(xué)碩士學(xué)位論文非線性等式約束優(yōu)化問題的一類既約Hessian算法研究姓名：王瑋申請學(xué)位級別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：陳蘭平20070406摘要對于解決非線性約束最優(yōu)化問題，罰函數(shù)法、可行方向法、逐步二次規(guī)觸法（）和既約法是目前應(yīng)用比較廣泛的幾種方法其中，逐步二次規(guī)劃法已經(jīng)成為求解中小規(guī)模非線性約束最優(yōu)化問題的一類最重要的方法，而既約法以每次迭代計算量小且算法所需內(nèi)存也小等優(yōu)點更是得到了許多研究者的青睞既約法一般可分為雙邊既約法和單邊既約法年。和首先提出雙邊既約的思想，后來一些學(xué)者對此進行了研究并提出一些算法這些算法一般都具有局部步卜超線性收斂速度年，和，提出單邊既約法，并且證明了

2、此方法具有局部步超線性收斂速度本文結(jié)合單邊既約法較快的收斂速度和雙邊既約法保持正定又較小的存儲的優(yōu)點。提出一種分別對單邊既約的近似陣和雙邊既約的近似陣校正的既約算法，在一定條件下證明了算法具有局部步卜超線性收斂速度；進一步地，在新算法的基礎(chǔ)上又提出一種具有全局收斂性的既約逐步二次規(guī)劃法數(shù)值實驗表明。本文提出的兩種新算法是有效的整篇論文內(nèi)容安排如下在第一章中，首先簡要的介紹了最優(yōu)化問題的提出以及判斷最優(yōu)解常用的最優(yōu)性條件，回顧了非線性最優(yōu)化問題常用的幾類方法在第二章中，就非線性等式約束問題，提出一種既約校正算法，此算法分別對函數(shù)的單邊既約的近似陣和雙邊既約的近似陣進行校正證明了若每次迭代至少有一

3、者被校正時，算法具有步一超線性收斂速度，并給出數(shù)值結(jié)果在第三章中，以第二章提出的算法為基礎(chǔ)，構(gòu)建一種解決非線性等式約束問題的既約方法為避免效應(yīng)，此方法采用的光滑精確罰函數(shù)的逼近形式作為價值函數(shù)，在一定條件下證明了算法的全局收斂性并且給出數(shù)值結(jié)果關(guān)鍵詞：約束最優(yōu)化，既約，擬牛頓方法，逐步二次規(guī)劃，局部超線性收斂，全局收斂性，（出，髓，：，首都師范大學(xué)學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨立進行研究工作所取得的成果除文中已經(jīng)注明引用的內(nèi)容外，本論文不含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品成果對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標(biāo)明本人完

4、全意識到本聲明的法律結(jié)果由本人承擔(dān)學(xué)位論文作者簽名衛(wèi)弗日期，御年月日首都師范大學(xué)學(xué)位論文授權(quán)使用聲明本人完全了解首都師范大學(xué)有關(guān)保留，使用學(xué)位論文的規(guī)定，學(xué)校有權(quán)保留學(xué)位論文并向國家主管部門或其指定機構(gòu)送交論文的電子版和紙質(zhì)版有權(quán)將學(xué)位論文用于菲贏利目的的少量復(fù)制并允許論文進入學(xué)校圖書館被查閱，有權(quán)將學(xué)位論文的內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索有權(quán)將學(xué)位論文的標(biāo)題和摘要匯編出版保密的學(xué)位論文在解密后適用本規(guī)定學(xué)位論文作者簽名。豆移日期；唧年，月日非線性優(yōu)化問題簡介這一章里，將簡要介紹非線性最優(yōu)化問題的發(fā)展現(xiàn)狀第一節(jié)。簡要地闡述最優(yōu)化問題的提出以及判斷最優(yōu)解常用的最優(yōu)性條件；第二節(jié)。總結(jié)了非線性最優(yōu)化問

5、題幾類常用的方法，重點是約束優(yōu)化的幾類方法；在最后一節(jié)，明確提出構(gòu)建薪算法的動機和技術(shù)手段最優(yōu)化問題的提出及最優(yōu)性條件最優(yōu)化理論與方法是一門應(yīng)用性很強的年輕學(xué)科雖然最優(yōu)化可以追溯到十分古老的極值問題，但直到年提出一般線性規(guī)劃問題的單純形法之后。它才成為獨立的學(xué)科，隨著現(xiàn)代科技的發(fā)展和計算機的廣泛應(yīng)用，進一步推動了最優(yōu)化理論和算法的研究今天，最優(yōu)化理論與方法在經(jīng)濟規(guī)劃，政府決策，生產(chǎn)管理、交通運輸和軍事國防等方面都得到了廣泛的應(yīng)用，已經(jīng)成為一門十分活躍的學(xué)科一般來說，最優(yōu)化問題可歸結(jié)為求解如下的極小值問題卿）其中，。是決策變量，（）為目標(biāo)函數(shù)。彤為可行域根據(jù)變量的類型，最優(yōu)化問題可分為連續(xù)型最優(yōu)

6、化和離散型最優(yōu)化（也稱組合優(yōu)化）連續(xù)型最優(yōu)化問題又可分為目標(biāo)函數(shù)和約束函數(shù)均為線性時的線性規(guī)劃問題，以及目標(biāo)函數(shù)和約束函數(shù)中至少有個為非線性時的非線性優(yōu)化問題本論文研究方向是非線性優(yōu)化問題非線性優(yōu)化問題通常有如下形式：砌。）（）（），一，。；（）（）（），。，；冗）及（），）都是定義在形上的函數(shù)，其中至少一個為非線性函數(shù)滿足（）一（）的點稱為可行點。所有可行點所組成的集合被稱為可行域，記為，顯然（），。；：功，）（）當(dāng)時，問題（）一（）是無約束優(yōu)化問題，否則，是約束優(yōu)化問題在約束優(yōu)化問題中。如果只有等式約束，即。，則稱為等式約束問題另一種特殊情形是所有的約束函數(shù)都是線性函數(shù)，這時我們稱問題（，

7、）一（）是個線性約束優(yōu)化問題下面我們給出非線性優(yōu)化問題的全局最優(yōu)解和局部最優(yōu)解的定義定義設(shè)礦，如果，（），（），成立，則稱礦是問題（）一（）的全局極小點，如果對一切且礦有，（）（）成立，則稱礦是全局嚴(yán)格極小點定義設(shè)礦，如果對某一有，（），（），（，）（）成立，則稱礦是問題（）一（）的局部極小點，其中（，）是以礦為中心以為半徑的廣義球（。，）霉一）如果對一切（礦，）且礦不等式（）成立，則稱礦是局部嚴(yán)格極小點若記（）（）表示，（）的梯度，（￥），（）表示，（）的矩陣對于無約束問題，有以下最優(yōu)化條件定理【（無約束優(yōu)化必要條件）若礦為問題（）的一個局部極小點，（）在礦處可微，則必有（礦）如果，（）在礦

8、處二次可微，則必有（，），（礦）（）（）滿足（）的點稱為函數(shù)，（）的穩(wěn)定點從上述可知，只要目標(biāo)函數(shù)可微，局部極小點必是穩(wěn)定點定理】（無約束優(yōu)化充分條件）假設(shè)，（功在礦處二次連續(xù)可微，如果礦是（）的穩(wěn)定點且對任何非零向量妒有（），則礦是無約束問題（）的局部嚴(yán)格極小點現(xiàn)在我們考慮約束優(yōu)化問題顯然，可行域上的一個點是否為局部極小點取決于目標(biāo)函數(shù)在這一點以及該點附近的可行點的值所以我們有必要給出可行方向的定義（）定義引入記號，。），），（）糾臼（），），對礦艫，我們稱集合（），（）是在點的積極集合（或有效集合），（）（）是在點的積極約束（或有效約束），（）“簪（）是在點的非積極約束（或非有效約束）定義

9、設(shè)礦，艫，如果存在使得，【，司，則稱是在礦處的可行方向（，）（）在礦處的所有可行方向的集合記為定義設(shè)礦，艫，如果（），（），（礦），（）（）則稱是在礦處的線性化可行方向在礦處的所有線性化可行方向的集合記為（，）定義設(shè)，肝，如果存在序列血，）和以（，）使礙礦以，（）且有如一和如一，則稱是在礦處的序列可行方向在礦處的所有序列可行方向的集合記為（，）引理如果所有的約束函數(shù)都在礦處可微，則有（，）（，）（。，）定理設(shè)礦是（）一（）的一個局部極小點，如果（，）（，）則存在越，）使得（）（礦），塒均，：島（），定義如果礦且存在”（姆，螺）滿足（）一（），則稱礦是問題（）（）的點（簡稱點），稱”是在處的乘子

10、假定我們已知問題（）（）在解處的積極約束（）我們只需求解如下的等式約束優(yōu)化問題砌，）（），（）由（）可得，（）的函數(shù)，即（）（）（，）一（）他）一地（）（）其中（，。）妒，以及（）（），南（）定義設(shè)礦是（）一（）的點。”是一相應(yīng)的乘子如果是在礦處的線性化可行方向且有智礦（礦），（礦），則稱是在礦處的線性化零約束方向在礦處的所有線性化零約束方向的集合記為（礦，”）如果在礦處的乘子是唯一的，我們用（。）來表示（礦，”）定義設(shè)礦是（）一（）的點，是一相應(yīng)的乘子如果存在序列以，）和缸（，）使得礦以，（）（）：（以），且有以一和以一，則稱是在礦處的序列零約束方向在礦處的所有序列零約束方向的集合記為（礦，

11、”）下面給出約束問題的優(yōu)化條件定理【】（約束優(yōu)化一階必要條件）設(shè)礦是問題（）。（）的一個局部極小點，如果（）“，（礦）線性無關(guān)，則必存在智“，）使得（）一（）成立定理【】（約束優(yōu)化一階充分條件）設(shè)礦如果，（功和島（），）都在礦處可微且礦，（礦），（，），（）則礦是聞題（，）一（）的局部嚴(yán)格極小點定理【】（約束優(yōu)化二階必要條件）設(shè)礦是問題（）（）的個局部極小點，是相應(yīng)的乘子，則必有吃（，），（，），（）其中（，）是由（）定義的函數(shù)定理【】（約束優(yōu)化二階充分條件）設(shè)礦是（）一（）的個點，”是相應(yīng)的乘子如果乞（，），（，），（）則礦是局部嚴(yán)格極小點非線性優(yōu)化問題的常用方法本文主要研究約束優(yōu)化問題，由

12、于約束優(yōu)化問題的解法很多基本思想來自無約束優(yōu)化問題的解法，且約束優(yōu)化問題往往可以轉(zhuǎn)化為無約束優(yōu)化問題的求解，所以有必要先介紹一些常見的無約束問題的解法和理論根據(jù)無約束優(yōu)化問題的算法大致分為兩類：其中之一，在計算過程中要用到目標(biāo)函數(shù)的解析性質(zhì)（包括一階導(dǎo)數(shù)和二階導(dǎo)數(shù)），一般稱這些方法為解析法；另一類只用到目標(biāo)函數(shù)值，不涉及目標(biāo)函數(shù)導(dǎo)數(shù)的計算，通常成為直接方法首先我們簡要介紹一下解析法它是求解無約束優(yōu)化問題；。（）（）常用的一類算法，它的基本思想是對于當(dāng)前的迭代點瓤，首先確定個搜索方向靠，使得目標(biāo)函數(shù)（）的值沿該方向是下降的，然后確定沿靠方向行進的步長并得到下一個迭代點?！办栐谶@里，我們要確定的搜

13、索方向應(yīng)滿足，（。）以使（）在點沿血方向下降為了行文的方便，在介紹線搜索和解析法幾類算法之前，約定記號如下，（），女（），（如），一女，女確定的過程就是線搜索，也稱一維搜索精確線搜索就是在也方向上尋求。最優(yōu)。的行進距離，使得（）乎（）（）（）精確線搜索往往計算量很大，特別是當(dāng)?shù)c遠(yuǎn)離最優(yōu)解時，效率很低而且，很多最優(yōu)化算法的收斂速度并不依賴于精確線搜索的過程，所以在實際應(yīng)用中，一般不采用精確線搜索非精確線搜索不要求（）成立。而僅要求找到的能使目標(biāo)函數(shù)在某種意義上達到令人滿意的下降，可以大大節(jié)省計算量常用的非精確線搜索如線搜索和線搜索兩種搜索的條件如下：線性搜索條件：觸舨堿槭璉陬魏扛咖帆十槲如口

14、（，百），盧（盯，）（）線性搜索條件：線性搜索主要是找一個兒，使，（，），且滿足如下不等式（）（）口姆（鯫）改口（，）（）下面我們介紹幾種常用的解析法最速下降法人們在處理（）這類問題時，總希望從某一點出發(fā)，選擇個目標(biāo)函數(shù)值下降最快的方向，以利于盡快達到極小點正是基于這樣的一種愿望，早在年法國著名數(shù)學(xué)家最早提出了最速下降法后來，等人作了進一步的研究該方法取也一（以），即每步都以負(fù)梯度方向作為搜索方向因為負(fù)梯度方向是目標(biāo)函數(shù)值下降最快的方向，所以該方法稱為最速下降法這種方法每次迭代的運算量不大。并且初始點不用很接近最優(yōu)點礦，但最速下降方向反映了目標(biāo)函數(shù)的一種局部性質(zhì)從局部看，最速下降方向是函數(shù)值下

15、降最俠的方向。選擇這樣的方向進行搜索是有利的但從全局看，由于鋸齒現(xiàn)象的影響，即使向著極小點移近不太大的距離，也要經(jīng)歷不小的彎路，因此使收斂速率大為減慢因此，總的來說，最速下降法并不是收斂最快的方法，它的收斂是比較慢的牛頓法牛頓法的基本思想是在每次迭代時，用適當(dāng)?shù)亩魏瘮?shù)去近似目標(biāo)函數(shù)，并用迭代點指向近似二次函數(shù)極小點的方向來構(gòu)造搜索方向，然后精確地求出近似二次函數(shù)的極小點，以該極小點作為，的極小點的近似值最直接而自然的二次模型，顯然就是，的展開式中直到二次項的部分?。ǎǎ?，其中（），（），因為方向比源于牛頓方程（）（），故稱為牛頓方向當(dāng)初始點充分靠近最優(yōu)點。時，該方法二階收斂并且對二次凸函數(shù)

16、具有二次終止性，但是當(dāng)初始點卻遠(yuǎn)離礦時，牛頓法可能不收斂。甚至連下降性也保證不了其原因是，迭代點不一定是目標(biāo)函數(shù)廠在牛頓方向以上的極小點為克服上述缺陷，往往要引進阻尼因子即步長，可以證明其在一定條件下是全局收斂的牛頓法需要計算目標(biāo)函數(shù)的及其逆矩陣，存儲量、計算量都很大，并且在迭代過程中，（）可能出現(xiàn)奇異，使迭代被迫中止共軛梯度法共軛梯度法最初由和于年為求解線性方程組而提出的后來，人們把這種方法用于求解無約束最優(yōu)化問題，使之成為一種重要的最優(yōu)化算法共扼梯度法取初始搜索方向一（。），以下各方向由第次迭代負(fù)梯度一（）與已得到的共軛方向一的線性組合來確定即以“，呶，。一。，主；其中風(fēng)為標(biāo)量，著名的公式

17、有釅?；I器高餌刪一卜蹦，），茚器（鈀枷覷¨），瞥（，），矽：些（戚一蝴，）等對正定二次函數(shù)來說，以上公式是等價的。但對于目標(biāo)函數(shù)是二次函數(shù)的無約束優(yōu)化問題，它們產(chǎn)生的搜索方向是不同的一般說來方法收斂性；較好，方法和方法具有好的數(shù)值表現(xiàn)，方法的收斂性和數(shù)值表現(xiàn)都比較理想由于共軛梯度法至少具有線性收斂速度，而且迭代公式比較簡單，只用到目標(biāo)函數(shù)及其梯度值，避免了二階導(dǎo)數(shù)的計算。從而減少了計算量和存儲量。因此它是一種比較有效的方法擬牛頓法擬牛頓法是近年發(fā)展起來的一種求解無約束優(yōu)化問題的最有效的方法特別是對高維問題有著明顯的優(yōu)越性擬牛頓算法的基本思想是：用不包含二階導(dǎo)數(shù)的矩陣近似牛頓法中的矩陣

18、的逆矩陣，由于構(gòu)造近似矩陣的方法不同，因而出現(xiàn)不同的擬牛頓法但近似×階對稱正定矩陣（）必須滿足擬牛頓方程：挑（）擬牛頓法的搜索方向為一（）（），在著名的族擬牛頓法中，的校正迭代公式為風(fēng)一等警絲州概咖碡（）饑一畿纛饑一面試?yán)诠膛f】其中口【，】，當(dāng)分別為，時，即為著名的公式和公式校正公式。圾一等警蓑校正公式。娜礬一警蓑（咖（）方法具有二次終止性，方法除了具有二次終止性之外。還具有超線性收斂性對于方法，由于線搜索的不精確和計算誤差的積累可能導(dǎo)致某一次迭代中的風(fēng)奇異；而方法對線搜索的精度要求不高，并且由它產(chǎn)生的風(fēng)不易變?yōu)槠娈惥仃囈虼?，方法比方法有更好的?shù)值穩(wěn)定性，使它更具有實用性擬牛頓法有許

19、多優(yōu)點，比如，迭代中僅需一階導(dǎo)數(shù)不必計算矩陣，當(dāng)正定時，算法產(chǎn)生的方向均為下降方向，并且這類算法具有二次終止性擬牛頓算法的缺點是所需存儲量較大，對于大型問題，可能遇到存儲方面的困難在有些無約束優(yōu)化問題中，目標(biāo)函數(shù)的解析式比較復(fù)雜或者難以用明顯的解析式表示出來，因而其導(dǎo)數(shù)很難求出或者無法求出，這就要求我們給出一些只涉及目標(biāo)函數(shù)值的計算而不涉及目標(biāo)函數(shù)的導(dǎo)數(shù)的求解方法這類方法也就是直接法，接下來我們就介紹幾種比較著名的直接方法交替方向法最早的也是最簡單的直接方法是交替方向法比較著名的算法有模式搜索法和方法摸式搜索法是由和于年提出的因此也稱為方法這種方法的基本思想從幾何意義上講。是尋找具有較小函數(shù)值

20、的。山谷”。力圖使迭代產(chǎn)生的序列沿。山谷”走向逼近極小點算法從初始基點開始。包括兩種類型的移動，這就是探測移動和模式移動探測移動依次沿個坐標(biāo)軸進行，用以確定新的基點和有利于函數(shù)值下降的方向模式移動浩相鄰兩個基點連線方向進行，試圖順著。山谷”使函數(shù)值更快減小模式移動的方向可以看作最速下降方向的近似，因此模式搜索法也可以看作最速下降法的一種近似由此可見，這種方法的收斂速度是比較慢的但是由于編程比較簡單，對變量不多的問題可以使用，而且的確是一種可靠的方法方法又稱為轉(zhuǎn)輔法。這種算法的每次迭代包括探測階段和構(gòu)造搜索方向兩部分內(nèi)容探測階段中，從一點出發(fā)，依次沿，個單位正交方向進行探測移動，一輪探測之后。再

21、從第一個方向開始繼續(xù)探測經(jīng)過若干輪探測移動，完成個探測階段然后構(gòu)造一組新的單位正交方向，稱之為轉(zhuǎn)軸，在下一次迭代中，將沿這些方向進行探測方法最早在年由提出后來、和對此方法進行了改進和分別討論了如何比較經(jīng)濟地詩算每次迭代中需要的個正交方向單純形法這里要介紹的單純形法是一種無約束最優(yōu)化的直接方法，并不是線性規(guī)劃的單純形法此方法最早由、和于年提出，后來由和改進單純形是指胛中的個點為頂點的凸包單純形法的基本思想是：在每次迭代時利用已有的單純形去尋我個函數(shù)值更小的點如果得到這樣個更好的點。則用這個新點作為一個頂點構(gòu)造新的單純形否則。將已有單純形縮小重復(fù)迭代方法方法的本質(zhì)上是共軛方向法，它是在年提出的方法

22、把整個計算過程分為若干個階段，每一個階段（一輪迭代）由次一維搜索組成在算法的每一階段中，先依次沿著已知的個方向搜索，得一個最好點，然后沿本階段的初點與該最好點連線方向進行搜索，求得這一階段的最好點再用最后的搜索方向取代前個方向之一，開始下一階段的迭代后來，注意到他的方法可能選取到接近線性相關(guān)的搜索方向，特別是變量很多時更是如此，為此他提出一種改進的方法，解決了這一問題雖然改進的方法不再具有二次終止性，但是，它的計算效果仍然令人滿意下面我們重點介紹幾種約束優(yōu)化問題的常用方法可行方向法可行方向法可看作無約束下降算法的自然推廣，其典型策略是從可行點出發(fā)，沿著下降的可行方向進行搜索，求出使目標(biāo)函數(shù)值下

23、降的新的可行點算法的主要步驟是選擇搜索方向和確定沿此方向的步長。搜索方向的選擇方式不同就形成了不同的可行方向法下面我們就來介紹一些可行方向法可行方向法通過線性規(guī)劃來確定下降可行方向，收斂速度比較慢方法是年和提出的一種求解線性約束問題的算法，其基本思想是將目標(biāo)函數(shù)作線性近似，通過求解線性規(guī)劃求得可行下降方向，并沿該方向在可行域內(nèi)作一維搜索這種方法又稱為近似線性化法，但是在實際應(yīng)用中。此方法常常不收斂于年提出一種投影梯度法，后來，和又將此法進行了改進的投影梯度法的基本思想是當(dāng)?shù)c在可行域內(nèi)部時，取該點處的負(fù)梯度方向作為可行下降方向，當(dāng)?shù)c在可行域邊界上時，取該點處負(fù)梯度方向在可行域邊界上的投影

24、產(chǎn)生一個可行下降方向約梯度法年，將線性規(guī)劃的單純形法推廣到具有非線性目標(biāo)函數(shù)的問題，提出既和于年成功地把既約梯度法推廣于求解帶菲線性等式約束的情形，提出了著名的方法（，廣義既約梯度法）數(shù)值實例表明，方法是目前求解約束非線性最優(yōu)化問題的最有效的方法之一由于可行方向法是先沿一線性化可行方向找到個較好的點，然后將該點利用方法?？尚谢钡玫揭粋€較好的可行點，每次迭代都要經(jīng)過若干次迭代，因此，可行方向法所需計算量還是相當(dāng)大的罰函數(shù)法罰函數(shù)法的基本思想是，借助罰函數(shù)把約束問題轉(zhuǎn)化為無約束問題，進而用無約束最優(yōu)化方法來求解早期求解非線性規(guī)劃問題（）一（）的方法都是罰函數(shù)法由于這些早期方法均是需要求解一串罰函

25、數(shù)極小的方法，故它們也被稱為序列無約束極小（）方法，簡稱罰函數(shù)可分為外點罰函數(shù)法內(nèi)點罰函數(shù)法和混合罰函數(shù)法如果罰函數(shù)的極小點和原問題（）一（）的解吻合時。我們稱該罰函數(shù)為精確罰函數(shù)罰函數(shù)法簡單實用，它直接利用無約束優(yōu)化的算法來求解約束優(yōu)化問題但是罰函數(shù)法一般要求罰因子趨于無窮或者需要求解非光滑優(yōu)化。所以利用一般無約束優(yōu)化算法時常有困難，另外罰函數(shù)法的收斂速度通常也是很慢的由于（）提出的一個求解線性規(guī)劃的內(nèi)點法實質(zhì)上等價于一個罰函數(shù)法，人們開始重新重視罰函數(shù)法解約束規(guī)劃的其他方法在判別迭代點好壞時都用到某一罰函數(shù)。所以對罰函數(shù)的研究對于求解約束規(guī)劃問題有著重要的作用最早的罰函數(shù)由（）提出，它只是

26、對等式約束問題提出的利用罰函數(shù)求解約束優(yōu)化問題往往需要很大的罰因子。從而使求解罰函數(shù)極小時可能出現(xiàn)數(shù)值困難如果利用精確罰函數(shù)或。精確罰函數(shù)，則一般經(jīng)過有限次迭代后得到原問題的精確解，但美中不足的是。三精確罰函數(shù)或厶。精確罰函數(shù)的極小是一個非光滑優(yōu)化問題內(nèi)點罰函數(shù)僅適合于不等式約束問題，即的情形兩個常見的內(nèi)點罰函數(shù)是倒數(shù)罰函數(shù)和對數(shù)罰函數(shù)因為內(nèi)點罰函數(shù)在可行域的邊界上無界，如果給定初始點在可行域內(nèi)部，則利用求罰函數(shù)極小所產(chǎn)生的點列全都是內(nèi)點從幾何上看，內(nèi)點罰函數(shù)在可行域的邊界形成一堵無窮高的。障礙墻。所以內(nèi)點罰函數(shù)也常稱為障礙罰函數(shù)早期罰函數(shù)法的缺點是需要罰因子趨于無窮大，才可使求罰函數(shù)極小和求

27、解原問題等價乘子罰函數(shù)利用近似乘子，從而不需要無窮大的罰因子著名的乘子罰函數(shù)法有增廣函數(shù)罰函數(shù)法和光滑罰函數(shù)法增廣函數(shù)罰函數(shù)法的一個美中不足是增廣函數(shù)是一個一次連續(xù)可微的函數(shù)，所以在求解過程中可能有數(shù)值困難光滑罰函數(shù)在一定意義下等價描述了原約束優(yōu)化問題，它在很多約束優(yōu)化的計算方法中有著直接的應(yīng)用一個很重要的例子是。它可以作為效益函數(shù)來判別算法給出的試探點是否可被接受逐步二次規(guī)劃法逐步二次規(guī)劃法（）是解決非線性優(yōu)化問題的最有效的方法之一，對于方法的研究已經(jīng)成為近十年來非線性最優(yōu)化領(lǐng)域的一個熱點這類方法是通過解一系列的二次規(guī)劃子問題來近似（）一（，）的的解，每一個二次規(guī)劃問題都得到一個搜索方向呶，

28、算法一般通過價值函數(shù)確定搜索步長，使瓢十毗在某種意望匕近似極小值點文考慮般非線性約束問題（）一（），由法得到（）一（）的二次規(guī)劃子問題為；，（），（）（）（，）“，其中（）（），。（）（），（），（），仉），仉，島艫”是函數(shù)的的近似記（）一（）的解為靠逐步二次規(guī)劃法用以作為搜索方向也是許多罰函數(shù)的下降方向，在一定條件下方法具有快速的局部收斂速度在約束優(yōu)化中，線搜索中用到的函數(shù)是來判斷試探點好壞的。所以這個函數(shù)被稱為價值函數(shù)為了得到全局收斂性，算法經(jīng)常使用罰函數(shù)作為價值函數(shù)，比如工精確罰函數(shù)，光滑精確罰函數(shù)但是罰函數(shù)有可能會破壞超線性收斂。這種現(xiàn)象通常被稱為效應(yīng)一般說來，利用光滑罰函數(shù)作為價值函

29、數(shù)可避免效應(yīng)目前型算法存在兩個重要問題：一是每步需要求解至個二次規(guī)劃子問題以得到迭代方向，計算工作量較大，難以應(yīng)用于大規(guī)模優(yōu)化問題，也難以利用有些問題的稀疏、對稱等良好特性；二是這些子問題可能無解，盡管此時可用其它措施重新定義迭代方向，但必然增加算法的復(fù)雜性，增大計算量，導(dǎo)致理論證明不完善文獻提出序列方程組法在一定程度上解決了上述問題因為方法采用擬牛頓法構(gòu)造，所以具備了擬牛頓法的優(yōu)點，【、均、，【等基于此提出一些算法圳證明了這類方法都具有局部超線性收斂速度這些方法一般在反正定的情況下直接對取校正。在風(fēng)不一定正定的情況下則對增廣函數(shù)的進行校正由于增廣項在靠近解的時候會導(dǎo)致矩陣病態(tài)，為解決這一問題

30、，【】使用一修正的校正公式來保證矩陣的正定性，但是遺憾的是此方法不能達到局部超線性收斂速度。而且會產(chǎn)生病態(tài)的逼近既約法既約法（簡稱既約法）是從法發(fā)展出來的方法它的基本思想是只利用既約或者是近似既約構(gòu)造的求解約束優(yōu)化的算法。這類方法的優(yōu)勢在于；在迭代過程中，由于只利用了函數(shù)的部分信息。所以矩陣的維數(shù)相對較小。每次迭代計算量較小。算法所需內(nèi)存也小而且由于函數(shù)的既約在解處是正定的，所以用擬牛頓公式校正不需要引入增廣項。從而避免了病態(tài)現(xiàn)象既約法一般可分為雙邊既約法和單邊既約法和【踟首先提出雙邊既約法的思想?！尽?，【】、嗍、】分別對等式約束問題提出了一些算法并且對收斂性進行和了分析嗍，和【】提出了解決不

31、等式約束問題（）提出單邊既約法，并且證明了此方法具有局部步的算法，這些算法一般都具有局部步卜超線性收斂速度超線性收斂速度的研究和在文獻【】中給出了個利用厶價值函數(shù)的全局收斂的既約算法在第二章我們會對既約法作更詳細(xì)本文的創(chuàng)新點近年來，許多學(xué)者對雙邊既約方法進行了研究，但是由于雙邊既約法忽略了一項的計算。使得收斂速度出現(xiàn)一步快步慢的現(xiàn)象，只能得到步卜超線性收斂速度本文提出一種分別對單邊既約和雙邊既約校正的新算法，在一定條件下證明了新算法具有局部步卜超線性收斂速度我們還將分析新算法使用光滑罰函數(shù)作為價值函數(shù)時的全局收斂性在第二章中，就非線性等式約束問題，提出一種既約校正算法，此算法分別對函數(shù)的單邊既

32、約的近似陣和雙邊既約的近似陣進行校正我們證明了若每次迭代至少有一者被校正時，算法具有步卜超線性收斂速度在第三章中，以第二章提出的算法為基礎(chǔ)，提出一種解決非線性等式約束同題的既約方法為避免效應(yīng)，此方法采用的光滑精確罰函數(shù)的逼近形式作為效益函數(shù)，在一定條件下證明了算法的全局收斂性在第二章和第三章中，我們都做了適量的數(shù)值實驗，其中的測試函數(shù)均出自文獻】一種非線性等式約束問題的既約算法在這一章中，就非線性等式約束問題，提出一種既約算法。此算法分別對函數(shù)的單邊既約的近似陣和雙邊既約的近似陣進行校正我們證明了若每次迭代至少有一者被校正時，算法具有步（卜超線性收斂速度引言考慮等式約束問題（）其中，：礦一，：

33、，仇都是二次連續(xù)可微的記（）；島（）（），（）（）。（）】，（）【（）。（）】假設(shè)，的矩陣在點是連續(xù)的矩陣函數(shù)，（）列滿秩，且設(shè)（）的分解有如下形式：，（習(xí)（）。（）元（）【扛）（）】孑，的零空間孔是（）的局部極小點的一階必要條件是（）（。），（。），（）其中（）是×階列正交矩陣，（）是×一）階列正交矩陣，（）是×階上三角陣；（）的列張成（）的值空間，（）的列張成（）（）（）為乘子而（）表明。是函數(shù)（，）一）的穩(wěn)定點設(shè)（，）是（，）二階導(dǎo)數(shù)。即則軋是的（）局部極小點的二階必要條件是（）（茹。，九歸（￥。）半正定，二階充分條件是（。）（，）（正。）正定證明見文獻【】

34、既約方法是通過約束函數(shù)切空間上函數(shù)的二階導(dǎo)數(shù)的近似信息來求問題（）的局部極小點它是由法發(fā)展起來的方法由于只利用了函數(shù)陣的部分信息，所以算法在每次迭代計算量小且算法所需內(nèi)存也小記法試探步為（也，（民）則滿足【毪第“。如卜【，（一），（【一（）簡化即得【（）一【一（，）羥一川蛩釅【凳一。囝國一釅其中瓢兒（民），設(shè)國？則上式可以寫為由（）得磙況昭巧一帆霹孫洲二茲篆糾【船（）蟊女一甜，若考慮（）的后兩行（分塊意義下）則可得（）蟹嚳耀磊船【一磺翟鯫【仇（）即有曜一，耀一況弧一刃在求解過程中需要求，般采用最小二乘法即（）（）從而可解出呶當(dāng)列滿秩，且刃矸名旅正定時，（）一（）的解唯一唼“一珊解得巧（）既約方法一般有兩種，即單邊既約法和雙邊既約法兩種方法一般都采用擬牛頓公式對函數(shù)的既約的近似陣進行校正常用的擬牛頓公式有公式。公式，公式，即風(fēng)魚生二里生生亟磊；巡一（礤靠）。，（。）單邊既約法一般用）“代替刃，由（）可得（礦），城船蚍；（刪玩慧一訾：卜一磐【蠔（¨）用（）校正得和在文獻】中證明了單邊既約法是局部超線性收斂的。但是沒有保證仇磊的正定性雙邊既約法一般用（”“，?？垡弧?，代替巧反，用零矩陣代替蠶圪，則由（）可得一詈陋】一磐用保持正定性的校正公式如（）或（）校正玩得最如文獻【】【】【中的方法，這些方法都只得到了步超線性收斂速度文獻】提出在一定