最優(yōu)化理論與方法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)內(nèi)點(diǎn)法基本原理摘要：內(nèi)點(diǎn)法是求解含不等式約束最優(yōu)化問題的一種十分有效的算法。內(nèi)點(diǎn)法通過構(gòu)造障礙函數(shù)，求解一系列只含等式約束最優(yōu)化問題，逐步得到原問題的最優(yōu)解，具有找初始點(diǎn)容易、線性收斂、迭代次數(shù)少等特點(diǎn)。本文主要介紹了內(nèi)點(diǎn)法的基本原理，障礙方法的一般步驟并分析了該方法的優(yōu)缺點(diǎn)，進(jìn)行了算例實(shí)踐。關(guān)鍵詞：內(nèi)點(diǎn)法；障礙方法；Newton法The Theory of Interior Point MethodAbstract: Interior point method is

2、a very effective algorithm for solving optimization problems with inequality constrained. Interior point method is constructed to solve a series of optimization problems with equality constraints, and the optimal solution of the original problem is obtained, which has the characteristics of finding

3、the initial point easier, linear convergence, less iteration number and so on. This paper mainly introduces the theory of interior point method, the general steps of barrier method and analyzing the advantages and disadvantages of the method. Key words: interior point method; barrier method;Newton m

4、ethod1 引言內(nèi)點(diǎn)法是由John von Neumann利用戈?duì)柕さ木€性齊次系統(tǒng)提出的，后被Narendra Karmarkar于1984年推廣應(yīng)用到線性規(guī)劃，即Karmarkar算法。內(nèi)點(diǎn)法是凸優(yōu)化算法遞階結(jié)構(gòu)中新層次的方法，其思想是對(duì)于線性等式和不等式約束的優(yōu)化問題，通過將其簡(jiǎn)化成一系列線性等式約束問題求解1。主要是通過構(gòu)造對(duì)數(shù)障礙函數(shù)將不等式約束與原目標(biāo)函數(shù)結(jié)合，將原問題轉(zhuǎn)化為新的等式約束下的優(yōu)化問題，之后再運(yùn)用Newton方法進(jìn)行求解2。而罰函數(shù)法是將不等式約束與等式約束全部進(jìn)行加權(quán)處理后與原目標(biāo)函數(shù)結(jié)合，將原問題轉(zhuǎn)化為新的無約束優(yōu)化問題，通過求解該新的無約束優(yōu)化問題，間接得到原約

5、束優(yōu)化問題的最優(yōu)解6。兩者在算法思想上有本質(zhì)的不同，但是當(dāng)原問題中只有不等式約束時(shí)，兩者求解是相同的。下面主要介紹內(nèi)點(diǎn)法的基本原理及算法思想，并對(duì)障礙法與原對(duì)偶內(nèi)點(diǎn)法的優(yōu)缺點(diǎn)進(jìn)行了探究與分析，并給出了一個(gè)實(shí)際算例來加以說明。2 內(nèi)點(diǎn)法原理2.1 對(duì)數(shù)障礙函數(shù)和中心路徑含有不等式約束的凸優(yōu)化問題的標(biāo)準(zhǔn)形式如下：（1）其中是二次可微的凸函數(shù)，。并且設(shè)最優(yōu)的點(diǎn)，最優(yōu)值為。滿足如下KKT條件：（2）通過定義對(duì)數(shù)障礙函數(shù)及加入正參數(shù)t：將原問題（1）近似轉(zhuǎn)化為（3）隨著參數(shù)t的不斷增加問題（3）的近似精度也會(huì)不斷改進(jìn)。而后我們可以通過讓參數(shù)t逐漸增加，運(yùn)用Newton方法來求解一系列形如（3）的優(yōu)化問題

6、，從而得到原問題（1）的最優(yōu)解。為了簡(jiǎn)化符號(hào)，考慮（3）的等價(jià)問題：（4）兩則的最優(yōu)解集相同，最優(yōu)值差一個(gè)常參數(shù)t。從開始假定問題（4）能夠用Newton方法求解，并特別假定對(duì)任何t0都存在唯一解。我們稱為中心點(diǎn)，而這些點(diǎn)的集合定義為問題（1）的中心路徑。并且所有中心路勁上的點(diǎn)都由以下充要條件所界定：是嚴(yán)格可行，即滿足：并且存在使成立。再定義我們可以將中心路徑的條件解釋為KKT最優(yōu)性條件（2）的連續(xù)變形。即等于的充要條件是存在滿足：（5）中心路徑條件（5）與KKT條件（2）的唯一不同在于互補(bǔ)松弛條件被條件所替換。特別是，對(duì)于很大的t，和對(duì)應(yīng)的對(duì)偶解“幾乎”滿足問題（1）的KKT最優(yōu)性條件。并且

7、在實(shí)際計(jì)算過程中求解是相當(dāng)有難度的，而通過將其轉(zhuǎn)化為就相對(duì)容易求解。2.2 障礙方法障礙方法是對(duì)無約束極小化方法進(jìn)行簡(jiǎn)單的擴(kuò)充，通過順序求解一系列無約束（或線性約束）對(duì)的極小化問題，每次用所獲得的最新的點(diǎn)作為求解下一個(gè)問題的初始點(diǎn)，也就是說，通過逐漸增加t的值得到相應(yīng)的，直到滿足所需要的精度。障礙算法的步驟如下：給定嚴(yán)格可行點(diǎn)誤差閾值。重復(fù)進(jìn)行：中心點(diǎn)步驟。從x開始，在的約束下極小化，最終確定。改進(jìn)。停止準(zhǔn)則。如果對(duì)偶間隙小于。增加t。每步迭代中我們都從上次獲得的中心點(diǎn)開始計(jì)算當(dāng)前中心點(diǎn)，然后通過乘比因子增加t。在中心點(diǎn)步驟中我們主要采用Newton方法來求解。我們將中心點(diǎn)步驟中的Newton

8、迭代或步驟稱為內(nèi)部迭代。每次內(nèi)部迭代我們都可以得到原問題可行解；但是僅在外部迭代結(jié)束時(shí)我們才有對(duì)偶可行解。2.3 障礙方法優(yōu)缺點(diǎn)分析（1）對(duì)初始點(diǎn)選擇要求不高對(duì)于初始點(diǎn)的選擇可以通過求解下面優(yōu)化問題得到，（6）并且根據(jù)上述優(yōu)化問題的最優(yōu)值的符號(hào)可以區(qū)分三種情況。當(dāng)則原不等式約束有嚴(yán)格可行解；當(dāng)則原不等式約束不可行；當(dāng)則原不等式約束可行，但是沒有嚴(yán)格可行解。并且只需要選擇的初始點(diǎn)嚴(yán)格滿足不等式約束，在接下去的迭代中只要中心步驟的某個(gè)迭代點(diǎn)選取了完整的Newton步徑，那么之后的所有迭代點(diǎn)都是原問題可行點(diǎn)。中心點(diǎn)的精度不需要十分精確在求解過程中不需要對(duì)進(jìn)行精確計(jì)算，因?yàn)橹行穆窂降淖饔脙H是隨著將中心

9、點(diǎn)引向原點(diǎn)的最優(yōu)解，無其他意義；不精確的中心點(diǎn)計(jì)算方法同樣能夠產(chǎn)生收斂于最優(yōu)點(diǎn)的點(diǎn)列。并且另一個(gè)方面，計(jì)算的十分精確的極小解只會(huì)增加少量的Newton迭代，因此也可以假定在計(jì)算中心點(diǎn)步驟中產(chǎn)生的都是精確的中心點(diǎn)。值的選擇不敏感參數(shù)的選擇需要同時(shí)兼顧所需要的內(nèi)部迭代和外部迭代的次數(shù)。當(dāng)值較小時(shí)可以期望每次外部迭代所需要進(jìn)行較少次數(shù)的Newton迭代，但是由于每次外部迭代只減少了較小的間隙，所需要的外部迭代次數(shù)會(huì)比較多。當(dāng)較大時(shí)，相反的情況也會(huì)發(fā)生。但是經(jīng)過實(shí)踐表明，的選擇對(duì)總的計(jì)算量并非特別敏感，取值從10到20或附近都能取得較好的效果，這位算法選擇提供了極大的便利。隨著問題維數(shù)的增加所需要的N

10、ewton迭代次數(shù)的增量非常小在具體算例中，可以發(fā)現(xiàn)應(yīng)用障礙方法當(dāng)問題的維數(shù)增加時(shí)，所需要的Newton迭代次數(shù)非常緩慢地增加，幾乎總是圍繞數(shù)十次的數(shù)量變動(dòng)。不過，進(jìn)行每次Newton迭代的計(jì)算量會(huì)隨著問題規(guī)模的增加而同步增加。對(duì)偶間隙呈現(xiàn)近似線性收斂對(duì)于大于10或者附近數(shù)值的值，障礙方法能夠很好地在大約經(jīng)過30次左右的Newton迭代就可以把對(duì)偶間隙從減少到。每次Newton迭代問題的對(duì)偶間隙近似縮小為原來的。但是通過實(shí)踐，我們也發(fā)現(xiàn)當(dāng)大于10或附近的數(shù)值時(shí)，的選擇幾乎不影響所需要的總的Newton迭代次數(shù)。為了改進(jìn)障礙方法的線性收斂速度，又提出了原對(duì)偶內(nèi)點(diǎn)法，該方法具有超線性收斂性質(zhì)，并且

11、能夠有效處理可行但不嚴(yán)格可行的問題5。3 算法實(shí)踐為了編程的方便，令，則。給定精度等參數(shù)后按照上述算法可以得到如下程序框圖：圖1：內(nèi)點(diǎn)法程序框圖以下面簡(jiǎn)單的優(yōu)化問題為例對(duì)內(nèi)點(diǎn)進(jìn)行進(jìn)一步的說明。（7）首先通過構(gòu)造內(nèi)點(diǎn)障礙函數(shù)用極值條件進(jìn)行求解可得，聯(lián)立上式求得，由于約束條件的限制，可得無約束極值點(diǎn)為，當(dāng)取時(shí)，可得最優(yōu)解為，。利用matlab也得到了相同的結(jié)果，如附錄程序所示7。而從如下圖像中也可以直觀看出當(dāng)時(shí)求出的最優(yōu)解約近似于原問題的最優(yōu)解。圖2：當(dāng)r分別取4、1、0.1、0.01時(shí)障礙函數(shù)圖像參考文獻(xiàn)：1Stephen Boyd, Lieven Vandenberghe.Convex Opt

12、imizationM.New York: Cambridge University Press, 2004,561-615. 2劉紅英, 夏勇, 周水生.數(shù)學(xué)規(guī)劃基礎(chǔ)M.北京:北京航空航天大學(xué)出版社,2012,205-239.3劉明波, 王曉村. 內(nèi)點(diǎn)法在求解電力系統(tǒng)優(yōu)化問題中的應(yīng)用綜述J. 電網(wǎng)技術(shù), 1999, 23(8):61-64.4汪超群, 韋化, 吳思緣,等. 七種最優(yōu)潮流分解協(xié)調(diào)算法的性能比較J. 電力系統(tǒng)自動(dòng)化, 2016, 40(6).5劉志鵬. 基于原對(duì)偶內(nèi)點(diǎn)法的最優(yōu)潮流研究D. 山東科技大學(xué), 2009.6張菊亮, 章祥蓀. 不等式約束最優(yōu)化的非光滑精確罰函數(shù)的一個(gè)光滑近

13、似J. 系統(tǒng)科學(xué)與數(shù)學(xué), 2000, 20(4):499-505.7 薛定宇,陳陽泉.高等應(yīng)用數(shù)學(xué)問題的Matlab求解M.北京:清華大學(xué)出版社,2004,37-42.附錄1.障礙函數(shù)function f=fun(x,r)f=x(1,1)2+x(2,1)2-r*log(x(1,1)-1);2.步長(zhǎng)的函數(shù)function f=fh(x0,h,s,r)%h為步長(zhǎng)%s為方向%r為1/tx1=x0+h*s;f=fun(x1,r);3. 步長(zhǎng)尋優(yōu)函數(shù)function h=fsearchh(x0,r,s)%利用進(jìn)退法確定高低高區(qū)間，利用黃金分割法進(jìn)行求解h1=0;%步長(zhǎng)的初始點(diǎn)st=0.001; %步長(zhǎng)的

14、步長(zhǎng)h2=h1+st;f1=fh(x0,h1,s,r);f2=fh(x0,h2,s,r);if f1f2 h3=h2+st; f3=fh(x0,h3,s,r); while f2f3 h1=h2; h2=h3; h3=h3+st; f2=f3; f3=fh(x0,h3,s,r); endelse st=-st; v=h1; h1=h2; h2=v; v=f1; f1=f2; f2=v; h3=h2+st; f3=fh(x0,h3,s,r); while f2f3 h1=h2; h2=h3; h3=h3+st; f2=f3; f3=fh(x0,h3,s,r); endend%得到高低高的區(qū)間a=

15、min(h1,h3);b=max(h1,h3);%利用黃金分割點(diǎn)法進(jìn)行求解h1=1+0.382*(b-a);h2=1+0.618*(b-a);f1=fh(x0,h1,s,r);f2=fh(x0,h2,s,r);while abs(a-b)0.0001 if f1f2 a=h1; h1=h2; f1=f2; h2=a+0.618*(b-a); f2=fh(x0,h2,s,r); else b=h2; h2=h1; f2=f1; h1=a+0.382*(b-a); f1=fh(x0,h1,s,r); endendh=0.5*(a+b);4. 迭代點(diǎn)的尋優(yōu)函數(shù)function f=fsearchx(x0,r,epson)x00=x0;m=length(x0);s=zeros(m,1);for i=1:m s(i)=1; h=fsearchh(x0,r,s); x1=x0+h*s; s(i)=0; x0=x1;endwhile norm(x1-x00)epson x00=x1; for i=1:m s(i)=1; h=fsearchh(x0,r,s); x1=x0+h*s; s(i)=0; x0=x1; endendf=x1;5. 主程序clearclcx0=2;2; %給定初始點(diǎn)