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

內(nèi)點法基本原理 摘要：內(nèi)點法是求解含不等式約束最優(yōu)化問題的一種十分有效的算法。內(nèi)點法通過構(gòu)造障礙函數(shù)，求解一系列只含等式約束最優(yōu)化問題，逐步得到原問題的最優(yōu)解，具有找初始點容易、線性收斂、迭代次數(shù)少等特點。本文主要介紹了內(nèi)點法的基本原理，障礙方法的一般步驟并分析了該方法的優(yōu)缺點，進行了算例實踐。關(guān)鍵詞：內(nèi)點法；障礙方法；Newton法The Theory of Interior Point MethodAbstract: Interior point method is 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 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 method1 引言內(nèi)點法是由John von Neumann利用戈爾丹的線性齊次系統(tǒng)提出的，后被Narendra Karmarkar于1984年推廣應(yīng)用到線性規(guī)劃，即Karmarkar算法。內(nèi)點法是凸優(yōu)化算法遞階結(jié)構(gòu)中新層次的方法，其思想是對于線性等式和不等式約束的優(yōu)化問題，通過將其簡化成一系列線性等式約束問題求解1。主要是通過構(gòu)造對數(shù)障礙函數(shù)將不等式約束與原目標(biāo)函數(shù)結(jié)合，將原問題轉(zhuǎn)化為新的等式約束下的優(yōu)化問題，之后再運用Newton方法進行求解2。而罰函數(shù)法是將不等式約束與等式約束全部進行加權(quán)處理后與原目標(biāo)函數(shù)結(jié)合，將原問題轉(zhuǎn)化為新的無約束優(yōu)化問題，通過求解該新的無約束優(yōu)化問題，間接得到原約束優(yōu)化問題的最優(yōu)解6。兩者在算法思想上有本質(zhì)的不同，但是當(dāng)原問題中只有不等式約束時，兩者求解是相同的。下面主要介紹內(nèi)點法的基本原理及算法思想，并對障礙法與原對偶內(nèi)點法的優(yōu)缺點進行了探究與分析，并給出了一個實際算例來加以說明。2 內(nèi)點法原理2.1 對數(shù)障礙函數(shù)和中心路徑含有不等式約束的凸優(yōu)化問題的標(biāo)準(zhǔn)形式如下：（1）其中是二次可微的凸函數(shù)，。并且設(shè)最優(yōu)的點，最優(yōu)值為。滿足如下KKT條件：（2）通過定義對數(shù)障礙函數(shù)及加入正參數(shù)t：將原問題（1）近似轉(zhuǎn)化為（3）隨著參數(shù)t的不斷增加問題（3）的近似精度也會不斷改進。而后我們可以通過讓參數(shù)t逐漸增加，運用Newton方法來求解一系列形如（3）的優(yōu)化問題，從而得到原問題（1）的最優(yōu)解。為了簡化符號，考慮（3）的等價問題：（4）兩則的最優(yōu)解集相同，最優(yōu)值差一個常參數(shù)t。從開始假定問題（4）能夠用Newton方法求解，并特別假定對任何t0都存在唯一解。我們稱為中心點，而這些點的集合定義為問題（1）的中心路徑。并且所有中心路勁上的點都由以下充要條件所界定：是嚴(yán)格可行，即滿足：并且存在使成立。再定義我們可以將中心路徑的條件解釋為KKT最優(yōu)性條件（2）的連續(xù)變形。即等于的充要條件是存在滿足：（5）中心路徑條件（5）與KKT條件（2）的唯一不同在于互補松弛條件被條件所替換。特別是，對于很大的t，和對應(yīng)的對偶解“幾乎”滿足問題（1）的KKT最優(yōu)性條件。并且在實際計算過程中求解是相當(dāng)有難度的，而通過將其轉(zhuǎn)化為就相對容易求解。2.2 障礙方法障礙方法是對無約束極小化方法進行簡單的擴充，通過順序求解一系列無約束（或線性約束）對的極小化問題，每次用所獲得的最新的點作為求解下一個問題的初始點，也就是說，通過逐漸增加t的值得到相應(yīng)的，直到滿足所需要的精度。障礙算法的步驟如下：給定嚴(yán)格可行點誤差閾值。重復(fù)進行：1. 中心點步驟。從x開始，在的約束下極小化，最終確定。2. 改進。3. 停止準(zhǔn)則。如果對偶間隙小于。4. 增加t。每步迭代中我們都從上次獲得的中心點開始計算當(dāng)前中心點，然后通過乘比因子增加t。在中心點步驟中我們主要采用Newton方法來求解。我們將中心點步驟中的Newton迭代或步驟稱為內(nèi)部迭代。每次內(nèi)部迭代我們都可以得到原問題可行解；但是僅在外部迭代結(jié)束時我們才有對偶可行解。2.3 障礙方法優(yōu)缺點分析（1）對初始點選擇要求不高對于初始點的選擇可以通過求解下面優(yōu)化問題得到，（6）并且根據(jù)上述優(yōu)化問題的最優(yōu)值的符號可以區(qū)分三種情況。當(dāng)則原不等式約束有嚴(yán)格可行解；當(dāng)則原不等式約束不可行；當(dāng)則原不等式約束可行，但是沒有嚴(yán)格可行解。并且只需要選擇的初始點嚴(yán)格滿足不等式約束，在接下去的迭代中只要中心步驟的某個迭代點選取了完整的Newton步徑，那么之后的所有迭代點都是原問題可行點。（2） 中心點的精度不需要十分精確在求解過程中不需要對進行精確計算，因為中心路徑的作用僅是隨著將中心點引向原點的最優(yōu)解，無其他意義；不精確的中心點計算方法同樣能夠產(chǎn)生收斂于最優(yōu)點的點列。并且另一個方面，計算的十分精確的極小解只會增加少量的Newton迭代，因此也可以假定在計算中心點步驟中產(chǎn)生的都是精確的中心點。（3） 值的選擇不敏感參數(shù)的選擇需要同時兼顧所需要的內(nèi)部迭代和外部迭代的次數(shù)。當(dāng)值較小時可以期望每次外部迭代所需要進行較少次數(shù)的Newton迭代，但是由于每次外部迭代只減少了較小的間隙，所需要的外部迭代次數(shù)會比較多。當(dāng)較大時，相反的情況也會發(fā)生。但是經(jīng)過實踐表明，的選擇對總的計算量并非特別敏感，取值從10到20或附近都能取得較好的效果，這位算法選擇提供了極大的便利。（4） 隨著問題維數(shù)的增加所需要的Newton迭代次數(shù)的增量非常小在具體算例中，可以發(fā)現(xiàn)應(yīng)用障礙方法當(dāng)問題的維數(shù)增加時，所需要的Newton迭代次數(shù)非常緩慢地增加，幾乎總是圍繞數(shù)十次的數(shù)量變動。不過，進行每次Newton迭代的計算量會隨著問題規(guī)模的增加而同步增加。（5） 對偶間隙呈現(xiàn)近似線性收斂對于大于10或者附近數(shù)值的值，障礙方法能夠很好地在大約經(jīng)過30次左右的Newton迭代就可以把對偶間隙從減少到。每次Newton迭代問題的對偶間隙近似縮小為原來的。但是通過實踐，我們也發(fā)現(xiàn)當(dāng)大于10或附近的數(shù)值時，的選擇幾乎不影響所需要的總的Newton迭代次數(shù)。為了改進障礙方法的線性收斂速度，又提出了原對偶內(nèi)點法，該方法具有超線性收斂性質(zhì)，并且能夠有效處理可行但不嚴(yán)格可行的問題5。3 算法實踐為了編程的方便，令，則。給定精度等參數(shù)后按照上述算法可以得到如下程序框圖：圖1：內(nèi)點法程序框圖以下面簡單的優(yōu)化問題為例對內(nèi)點進行進一步的說明。（7）首先通過構(gòu)造內(nèi)點障礙函數(shù)用極值條件進行求解可得，聯(lián)立上式求得，由于約束條件的限制，可得無約束極值點為，當(dāng)取時，可得最優(yōu)解為，。利用matlab也得到了相同的結(jié)果，如附錄程序所示7。而從如下圖像中也可以直觀看出當(dāng)時求出的最優(yōu)解約近似于原問題的最優(yōu)解。圖2：當(dāng)r分別取4、1、0.1、0.01時障礙函數(shù)圖像參考文獻：1Stephen Boyd, Lieven Vandenberghe.Convex OptimizationM.New York: Cambridge University Press, 2004,561-615. 2劉紅英, 夏勇, 周水生.數(shù)學(xué)規(guī)劃基礎(chǔ)M.北京:北京航空航天大學(xué)出版社,2012,205-239.3劉明波, 王曉村. 內(nèi)點法在求解電力系統(tǒng)優(yōu)化問題中的應(yīng)用綜述J. 電網(wǎng)技術(shù), 1999, 23(8):61-64.4汪超群, 韋化, 吳思緣,等. 七種最優(yōu)潮流分解協(xié)調(diào)算法的性能比較J. 電力系統(tǒng)自動化, 2016, 40(6).5劉志鵬. 基于原對偶內(nèi)點法的最優(yōu)潮流研究D. 山東科技大學(xué), 2009.6張菊亮, 章祥蓀. 不等式約束最優(yōu)化的非光滑精確罰函數(shù)的一個光滑近似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.步長的函數(shù)function f=fh(x0,h,s,r)%h為步長%s為方向%r為1/tx1=x0+h*s;f=fun(x1,r);3. 步長尋優(yōu)函數(shù)function h=fsearchh(x0,r,s)%利用進退法確定高低高區(qū)間，利用黃金分割法進行求解h1=0;%步長的初始點st=0.001; %步長的步長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=min(h1,h3);b=max(h1,h3);%利用黃金分割點法進行求解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. 迭代點的尋優(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; %給定初始點r=1;c