計(jì)算機(jī)視覺中數(shù)學(xué)方法-5迭代算法續(xù)

3.3

3．迭代算約束優(yōu)化問?minf?subjecttog(x)≤0,i=1,2,...,

h(x)=0,i= 的可行域?={x∈Rn|gi(x)≤0,hj(x)=0,i=1,2,...,p;j=假定約束優(yōu)化問題中1[懲罰法

3．迭代算懲罰法，又稱為序列無(wú)約束極小化方法。該方法是通過引入罰外懲罰法(罰函數(shù)法)內(nèi)懲罰法 函數(shù)法)外懲罰法基本思想：首先選擇一個(gè)充分大的數(shù)C，構(gòu)造一個(gè)罰?0,b(x)=C,x?

23．迭代算其中C稱為懲罰因子，表示對(duì)不可行點(diǎn)的懲罰。然后將原問題歸為無(wú)約束優(yōu)化問p(x)=f(x)+b(x)=f(x),x∈

??C,x??稱為(3.4.1)的增廣代價(jià)最優(yōu)然而罰函數(shù)(3.31)在可行域?的邊界具有非常大的跳躍，3優(yōu)化方法求解問題

3．迭代算為了使增廣代價(jià)函數(shù)p(x)在可行域邊界具有原代價(jià)函數(shù)的須使p(x)在可行域的邊 bc(x)=C∑[max(gi(x),0)]2 ∑(hi i= 2i=使得增廣代價(jià)函數(shù)pc(x)= f(x)+bc(x)在可行域邊界就具有連續(xù)性。因此，只要C充分大，原問題就可以歸結(jié)為無(wú)約束問題： (x) f(x)+ 懲罰因子C究竟選擇多才合改進(jìn)：選擇單調(diào)嚴(yán)格遞增趨于正無(wú)窮的懲罰因子序列：43．迭代算{Ck|k=1,2,...}此時(shí)隨著k的增 c(x)對(duì)不可行點(diǎn)的懲罰Ck也求解原約束優(yōu)化問題歸結(jié)為求解一系列無(wú)約束優(yōu)化問題 (x),k=k其中

pc(x)=f(x)+

p(x),bc(x)=Ck∑[max(gi(x),0)]2

i

2i對(duì)于(3.35)的最優(yōu)解{xk}，我們期望它能趨 問題的最優(yōu)解。（。5外懲罰法的計(jì)

選取初始x0，給定終止控制常數(shù)ε>0和懲罰因子序{Ck|k=1,2,...}；k:=1 以初始點(diǎn)xk?1，用無(wú)約束優(yōu)化方法求 (x)，得到它的k優(yōu)解xk。若xk已滿足終止條件，則輸出最優(yōu)解xk；否則k:=k+1，轉(zhuǎn)步2)

=σC(C>0,σ≥2)。終止條件：S(x) 1p(x)Ck+ CkS(x)≤ε；gk=max{gi(xk)},hk=max{hj(xk)}，max{gk,hk}≤6內(nèi)懲罰法基本

3．迭代算邊界設(shè)置一道 ”的是所謂 函數(shù)，然 為了陳述方便起?minf?subjecttog(x)≤0,i=1,2,...,

可行域的內(nèi)?o={x∈Rn|gi(x)<0,i=1,2,...,73．迭代算∈?值趨近于零，因此下 gb(x)= ，或b(x)=?∑log(?gigi= i=這個(gè)函數(shù)被稱 函數(shù)。構(gòu)造增廣代價(jià)函數(shù)如下p(x)=f(x)+， 函數(shù)b(x)的作，由于最終要尋求原約邊界上，所以在迭代過程中要逐漸減小b(x)的懲罰程度。為此，與83．迭代算懲罰法類似，首先選取一個(gè)單調(diào)減趨于零的正懲罰因子序列{Dk|k=1,2,...}，并對(duì)每一個(gè)k，構(gòu) 函數(shù) bDk(x)=?Dk∑g(x)，或bDk(x)=?Dk∑log(?gi i= i=然后構(gòu)造定義在?o上增廣代價(jià)函pD(x)=f(x)+bD D由 (x)構(gòu)造可知，當(dāng)一個(gè)點(diǎn)從可行域內(nèi)部趨向可行域邊界時(shí)DkD (x)將無(wú)限增DkD Dk的最優(yōu)解總是在可行域內(nèi)部。如果(3.39)93．迭代算 D(x)的影響逐漸k將近D (x),k= Dk內(nèi)懲罰>正懲罰因子序列{Dk|k=1,2；k:=1；構(gòu)造懲罰函數(shù)bD(x)和增廣代價(jià)函數(shù)pD D以初始點(diǎn)xk?1，用無(wú)約束優(yōu)化方法求 (x)，得到它的Dk3．迭代算優(yōu)解xk。若xk已滿足終止條件，則輸出最優(yōu)解xk；否則，k:=k+1，轉(zhuǎn)步2)在內(nèi)懲罰法中，初始{Dk|k=1,2,...}可按下述遞推方式產(chǎn)Dk+1=σ?1Dk(C1>0,σ≥終止條件bD(xk≤ε，或gk=max{|gi(xk)|}≤k懲罰法的優(yōu)點(diǎn)是方法結(jié)構(gòu)較簡(jiǎn)單，但存在下述缺點(diǎn)

3．迭代算收斂速度計(jì)算量方法自身造成了數(shù)值計(jì)算上 因?yàn)樵谇蠼膺^程中要求懲因子無(wú)限增大或無(wú)限數(shù)的矩陣的嚴(yán) ，直接影響了懲罰法的效率，甚至算法失敗[乘子法

3．迭代算Hestenes1969年，針對(duì)等式約束優(yōu)化問題提出了著名的乘子法，它借用了懲罰法中構(gòu)造增廣代價(jià)函數(shù)的思想，并利用Lagrange乘子法克服了懲罰法所固有的數(shù)值。后來，Buys，Bertsekas，RockafellarHestenes乘子法到一般約束優(yōu)化問題。先介紹Hestenes乘子法。乘考慮等式約束優(yōu)化問?minf?subjecttoh(x)=0,i=

3．迭代算假定所涉及的函數(shù)都pc(x)=f(x)pck

2

∑(hi(x))i=令 (x),k=1,2,...的最優(yōu)解為xk，則必kqck? (xk)=?f(xk)+Ck∑hi(xk)?hi(xk)=cki=qi1?f(xk)=?∑hi i=

(xk

(xk假定xk→x*k→∞，其中x*為最優(yōu)解于是在上式3．迭代算 limk→∞ ?f(xk)=?∑hi(x*)?hi(x*)= i=對(duì)于約束優(yōu)化問題，一般有?f(x*)≠0，所以Ck→∞。由此可見， 懲罰法的懲罰因子無(wú)限增大的本質(zhì)是f(x*)≠0。如果我們存在aane乘子*3.41的araneqL(x,μ)=f(x)+∑i=

3．迭代算?L(x*,μ*)

?xL(x*,?=??μL(x*,μ*)??(x*,μ*)不是函數(shù)L(x,μ)的極小點(diǎn)或極點(diǎn)即L(x*,μ)≤L(x*,μ*)≤L(x,綜上所述，問題(3.41)?minL(,?subjecttoh(x)=0,i=

3．迭代算 再將懲罰法應(yīng)用于上述問題，原問題(3.41)就轉(zhuǎn)化為求解增廣 pc(x,μ*)=L(x,μ*) ∑[hj 2j=的無(wú)約束極小問難點(diǎn)：在數(shù)值上如何確定μ*和C，特別是確定μ*。對(duì)此，Hestenes出了如下方C選取一個(gè)無(wú)限增大的正數(shù)序列{Ck3．迭代算使之隨迭代次數(shù)增加而增大；對(duì)乘子μ*，先給定一個(gè)初始值，然后在迭代過程中不斷更新它。下面給出Hestenes的乘子μ*更新公假定已有μk，并令xk=argminpC(xμk)，則kk?xk

(xk,μk)=?xL(xk,μk)+Ck∑hj(xk)?hj(xkj= =?f(xk)

∑μk?h(xk)+ j

∑hj(xk)?hj(xkj==?f(xk)

∑

+Ch(xk))?h(xk)=

k j= 3．迭代算?xL(x*,μ*)=?f(x*)

∑μ*?h j=≈?f(xk)

∑μk+1?h(xk

j=μk+1=μk+Ch(xk),j= k

>增趨于無(wú)窮大的正懲罰因子序列{Ck|k=1,2；k:=13．迭代算以初始點(diǎn)xk?1，用無(wú)約束優(yōu)化方法求 k C (x,μk)=f(x)Ck

∑μkh(x)jj=j

k∑[hj2j=若xk已滿足終止條件，則輸出最優(yōu)解xk；否則，轉(zhuǎn)步驟更新乘子：μk1=μk+Ch(xk),j=1,2,...,q，令k:=k+1 k轉(zhuǎn)步2)**Ck+1=σCk(C1∈[0.1,1],σ≥初始乘子常取零。終止條件：hk=max{|hj(xk)|}≤ε，或||xk1?xk||≤ε且||μk1?μk||≤ε，或|f(xk1?f(xk)|≤

3．迭代算Rockafellar將Hestenes乘子 到不等式約束優(yōu)化問題?minf ?subjecttog(x)≤0,i=1,2,...,

Rockafellar乘子法首先引入松馳變量y=(y1,y2,...,yp)T將不等式約束優(yōu)化(3.46)轉(zhuǎn)化為變量(x,y)的等式約束優(yōu)化：?minfi?subjecttogi(x)+y2=0,i=1,2,...,i

根據(jù)Hestenes乘子法，(3.47)的增廣Lagrange代價(jià)函數(shù)C (x,y,λ)=f(x)Ck

qi∑λi(gi(x)+y2)ii=

2

i∑(gi(x)+yii=

3．迭代算其中λ=(λ1,λ2,...,λp)T是乘子，{Ck}是一個(gè)單調(diào)增趨于無(wú)窮的正懲罰因子序列。近最優(yōu)解的迭代點(diǎn)列{(xkyk)}與乘子的迭代點(diǎn)列(xk,yk)=argminpC(x,y,λkkλk1=λk+Cg(xk+(yk)2),j=1,2p k 數(shù)pC(xy,λ關(guān)于變y極小kL(x,λ)=minypC(x,y,λ)k從下述方y(tǒng)1(λ1+Ck(g1(x)+y2))

3．迭代算 ?y2(λ2+Ck(g2(x)+y2))k?yk

(x,y,λ)??

?= ?2p得

+Ck(gp(x)+yp??1(λ+C(g

+C(g(x))<iky2=? ik?

,i=1,2,...,pi+Ck(gi(x))≥kλ(g(x)+y2)+Ck(g(x)+y2

3．迭代算??i，(λi+Ck(gi(x))<=

C?λigi(x)+k(gi(x))2，(λi+Ck(gi(x))≥

i[(max(0,λi+Ck(gi(x)))2?λ2],i=1,2,...,i因此L(x,λ)=minypC(x,y,λ)=f(x)k

pi1∑[(max(0,λi+Ckgi(x)))2?λi1ki=3．迭代算λk+1=λk+Cg(xk)+(yk)2)=max(0,λk+Cg(xk)),i=1,2,..., k k>增趨于無(wú)窮大的正懲罰因子序列{Ck|k=1,2；k:=1k C (x,λk)=f(x)Ck

[(max(0,λi+Ckgi(x)))?λi]ki=3．迭代算若xk已滿足終止條件，則輸出最優(yōu)解xk；否則，轉(zhuǎn)步驟更新乘子λk1=max(0,λk+Cg(xk)),i=1,2p kk:=k+1，轉(zhuǎn)步2)。一般約束優(yōu)化?minf?subjecttog(x)≤0,i=1,2,..., ? hj(x)=0,i=?的增廣代價(jià)函數(shù)序p1pLC(x,λk,μk)=f(x) ∑[(max(0,λ

3