非線性約束最優(yōu)化算法課件

本文框架最優(yōu)化算法分類(lèi)不等式約束組合變量消除優(yōu)化函數(shù)和濾波馬洛托斯現(xiàn)象二次校正和非單調(diào)方法本文框架最優(yōu)化算法分類(lèi)115.1最優(yōu)化算法分類(lèi)非線性最優(yōu)化算法沒(méi)有分類(lèi)標(biāo)準(zhǔn)；對(duì)后面章節(jié)各種逼近做了分組，如下

所述：第16章，討論二次線性規(guī)劃（quadraticprogramming）求解問(wèn)題的算法，它具有獨(dú)特的性能。對(duì)有效集(activeset)，內(nèi)點(diǎn)法(interior-point)和梯度投影法(gradientprojectionmethods)進(jìn)行討論。第17章,討論罰函數(shù)(penalty)和增廣拉格朗日(augmentedLagrangianmethods)方法，把目標(biāo)函數(shù)和條件都結(jié)合歸到罰函數(shù)里邊，這樣可以通過(guò)求解一系列非約束條件處理15.1問(wèn)題。15.1最優(yōu)化算法分類(lèi)非線性最優(yōu)化算法沒(méi)有分類(lèi)標(biāo)準(zhǔn)；對(duì)后面215.11罰函數(shù)和增廣朗格朗日方法假如(15.1)中只有等式約束條件存在，那么二次罰函數(shù)定義：等式約束問(wèn)題，定義：結(jié)合拉格朗日函數(shù)性質(zhì)和二次罰函數(shù)（15.2）函數(shù)增廣拉格朗日函數(shù):15.11罰函數(shù)和增廣朗格朗日方法假如(15.1)中只有等315.12連續(xù)二次規(guī)劃方法第18章，討論序列二次規(guī)劃方法（sequentialquadraticprogramming）簡(jiǎn)稱(chēng)SQP.基本的SQP方法中定義Pk在(xk，λk)迭代的方向，從而得到解約束條件：15.12連續(xù)二次規(guī)劃方法第18章，討論序列二次規(guī)劃方法（415.13非線性規(guī)劃內(nèi)點(diǎn)法第19章，討論非線性規(guī)劃內(nèi)點(diǎn)法（interior-point）相對(duì)在14章討論的線性規(guī)劃來(lái)說(shuō)，這種方法可以看做是原始對(duì)偶內(nèi)點(diǎn)法（primal-dualinterior-point）的拓展，也可以看做是障礙法。約束條件：15.13非線性規(guī)劃內(nèi)點(diǎn)法第19章，討論非線性規(guī)劃內(nèi)點(diǎn)法515.2不等式約束組合求解非線性規(guī)劃最主要的難題是處理不等式約束，特別是在解中確定哪些約束條件是有效的。估測(cè)一個(gè)最優(yōu)有效集A*，這是一組約束條件，在解處滿足等式。這估測(cè)值叫做作用集，用w表示。在作用域約束條件強(qiáng)制為等式，約束條件在w處忽略，然后求解。最后驗(yàn)證是否有一個(gè)拉格朗日乘數(shù)，得到近似解X*，且W滿足KKT條件（12.34）。這樣把這X*看做（15.1）的局部解。例子：即使小數(shù)量的不等式約束，確定最優(yōu)化有效集不是一個(gè)簡(jiǎn)單的任務(wù)。問(wèn)題：約束條件：15.2不等式約束組合求解非線性規(guī)劃最主要的難題是處理不等615.21W的八種可能選擇用在下面的描述的作用作用域：按指數(shù)1到3有序標(biāo)記，圖15.1闡述了目標(biāo)函數(shù)的形態(tài)，可行域是兩軸和曲線包圍的區(qū)域?？梢钥闯鲈诮庵兄挥械谝粋€(gè)約束條件有效，（x*，y*）=(1.953，0.089)τ即使對(duì)這個(gè)小的例子，考慮所有w可能的值很麻煩，圖15.1表明，可以利用定義這個(gè)問(wèn)題和他們的派生的函數(shù)知識(shí)消除，事實(shí)上在16章描述的有效集方法利用這種信息來(lái)進(jìn)行一系列有根據(jù)的猜測(cè)作用域，避免w選擇的明顯偏離15.1的解。既內(nèi)點(diǎn)法（障礙法）之后，一種不同的方法在19章考慮，這種方法生成的迭代遠(yuǎn)離通過(guò)不等式約束條件定義的可行定義域的邊界，作為非線性規(guī)劃的解釋近似的阻礙作用被消弱，允許精度增加解的估計(jì)，在這種方法中避免了非線性規(guī)劃組合的難題。15.21W的八種可能選擇用在下面的描述的作用作用域：即使7第一種可能：求解方案中任何約束條件無(wú)效，也就是說(shuō)w=Φ，由于▽f=(x-2，y-1/2)T，可以看到無(wú)約束f最小值在可行域外邊，所以最優(yōu)化有效集不能為空。有7種另外可能，其中三個(gè)約束條件是有效的，w={1，2，3}，圖（15.1）對(duì)這個(gè)問(wèn)題這樣的情況沒(méi)有發(fā)生，三個(gè)約束條件不共享一個(gè)相同的交叉點(diǎn)。通過(guò)單一的有效約束條件，得到三個(gè)更進(jìn)一步的可能，那就是是{w=1}，{w=2}，{w=3}{W=2}，只有x=0的約束條件有效，如果在這種條件下使f執(zhí)行最小化，得到（0，1、2）T這個(gè)點(diǎn)，檢查（12.34）KKT條件，表明無(wú)論選擇什么拉格朗日乘數(shù)，都不能滿足在0，1、2）T的條件。（因?yàn)楸仨氁?=λ3=0滿足（13.34e）），通過(guò)這表明，設(shè)λ2=-2滿足（12.34a），但是λ2的值不滿足(12.34d)。{W=1，3}，得到單一的可行點(diǎn)（3，0）T，由于約束條件2在這個(gè)點(diǎn)無(wú)效，令λ2=0，解決（12.34a）用其他朗格朗日乘數(shù)，得到λ1=-16，λ3=16.5。，這些值是負(fù)數(shù)，不滿足（12.34）所以（3，0）T不是（15.1）的解。{W=1}，求解等式約束條件問(wèn)題，這問(wèn)題中第一個(gè)約束條件是有效的，得到點(diǎn)（x，y）T=(1.953，0.089)T和拉格朗日乘數(shù)λ1=0.411。通過(guò)設(shè)定λ2=λ3=0，很容易得到，（12.34）的KKT其他條件是滿足。于是得結(jié)論這個(gè)點(diǎn)是KKT點(diǎn)，由于拉格朗日的Hessian正定，很容易得到二階充分條件滿足。第一種可能：求解方案中任何約束條件無(wú)效，也就是說(shuō)w=Φ，由于815.3變量消除

處理約束最優(yōu)化問(wèn)題，用邊界條件消除問(wèn)題中的變量是正常的，用更少的自由度得到一個(gè)簡(jiǎn)單問(wèn)題。然而由于消除法可能改變問(wèn)題或者引入病態(tài)條件必須小心使用目標(biāo)函數(shù)：約束條件：得到兩個(gè)變量的函數(shù)：15.3變量消除

處理約束最優(yōu)化問(wèn)題，用邊界條件消除問(wèn)題915.31非線性消除的缺點(diǎn)問(wèn)題思考：約束條件：通過(guò)消除y求解，得到下面等式：很明顯，隨著x趨近負(fù)無(wú)窮時(shí)，h(x)趨近負(fù)無(wú)窮。盲目應(yīng)用這個(gè)轉(zhuǎn)換，得到這個(gè)問(wèn)題無(wú)線，但是這個(gè)問(wèn)題不能忽略約束條件（x-1）3=y2，這個(gè)含蓄的表明x≧1界值，這個(gè)解是有效的。因此，如果希望消除y，必須加入x≧1這個(gè)界值。這個(gè)問(wèn)題說(shuō)明了用非線性消去變量，可能導(dǎo)致很難追蹤錯(cuò)誤的結(jié)果?；谶@個(gè)原因，大多數(shù)最優(yōu)化算法中不用非線性消去法。相反，許多約束條件的線性的算法會(huì)用到消去法去解一些簡(jiǎn)單問(wèn)題。現(xiàn)在就系統(tǒng)的概述下用線性約束去得到變量消除的目的。15.31非線性消除的缺點(diǎn)問(wèn)題思考：約束條件：通過(guò)消除y1015.32用線性約束簡(jiǎn)單消去思考線性函數(shù)的約束條件的最小化問(wèn)題，約束條件是線性等式約束：約束條件：A是一個(gè)m×n的矩陣，m≦n。簡(jiǎn)單起見(jiàn)假設(shè)A是滿秩（假如情況不是這種情況，得到這個(gè)問(wèn)題要么矛盾，要么約束條件多余的，能刪除而不影響問(wèn)題的解)在這種假定下，我們可以找到線性獨(dú)立矩陣Ａ的m列的一個(gè)子集。如果將這些列向量組合到一個(gè)的B矩陣，定義一個(gè)的P置換矩陣。Ｐ矩陣是將這些列與Ａ的第一個(gè)列進(jìn)行交換的矩陣，表達(dá)式:N表示Ａ矩陣n-m剩余列。(這里的注釋和第13章一致，討論線性規(guī)劃背景的相似概念)15.32用線性約束簡(jiǎn)單消去思考線性函數(shù)的約束條件的最小11定義下面形式下的子向量

：(15.8)xB為基變量，B為基矩陣。注意PPT=I可以將約束條件Ax=b改寫(xiě)如下：重排這個(gè)式子，通過(guò)下面的表達(dá)式可以減少所給的基變量：(15.9)從而，通過(guò)選擇任意xN值，計(jì)算約束條件Ax=b的可行點(diǎn)，然后可以通過(guò)(15.9)設(shè)置xB。因此，(15.4)問(wèn)題和非約束問(wèn)題等價(jià)。(15.10)上述討論說(shuō)明了線性等式的約束條件的非線性最優(yōu)化問(wèn)題是從數(shù)學(xué)觀點(diǎn)來(lái)的，非約束問(wèn)題同樣，下面就討論非約束問(wèn)題定義下面形式下的子向量：上述討論說(shuō)明了線性等式的約束條件的1215.34線性等式的非約束問(wèn)題的非線性最優(yōu)化思考：（15.11a）約束條件：(15.10)定義轉(zhuǎn)置矩陣P得

的組成從新排列，xT=(x3，x6，x1，x2，x4，x5)T，得到AP矩陣的系數(shù):基矩陣B是對(duì)角陣，因此，很容易求取轉(zhuǎn)置(15.12)15.34線性等式的非約束問(wèn)題的非線性最優(yōu)化思考：13替換(15.11a)中的x3，x6，問(wèn)題變成如下：

(15.13)從Ａ系數(shù)矩陣(不含有X3和X6兩個(gè)變量)中選擇其它兩列作(15.11b)系統(tǒng)中消除的基礎(chǔ)。然而，這些選擇，B-1N將會(huì)變得更復(fù)雜。用高斯消元法選擇一組m非獨(dú)立列，在線性代數(shù)中的用語(yǔ)，能計(jì)算出這個(gè)矩陣的行階梯型，選擇中心軸列做為基矩陣的列。理想情況下，希望B矩陣很好分解和適定性。為了這個(gè)目的，用稀疏高斯消去算法去，保持稀疏、控制舍入誤差。替換(15.11a)中的x3，x6，問(wèn)題變成如下：(15.14從(15.8)和(15.9)中可以看出在線性約束條件(15.6)中任意可行點(diǎn)可以被寫(xiě)成：(15.14)(15.15)注意z有n-m線性非獨(dú)立列(由于在低維中存在單位矩陣的存在)滿足AZ=0因此，Z是空矩陣A的基礎(chǔ)矩陣。加上Y和Z的列組成是一個(gè)線性非獨(dú)立集。我們也可以看到是線性約束條件一個(gè)特解.從(15.8)和(15.9)中可以看出在線性約束條件(15.15換句話說(shuō)，這個(gè)簡(jiǎn)單消去法說(shuō)明了可行點(diǎn)可以作為Ax=b(15.14的第一項(xiàng))的特解加上沿著約束條件(15.14的第二項(xiàng))的空集(或者相切)總的概括。這(15.13)，(15.14)的關(guān)系表明特解Yb是從控制x的n-m個(gè)在０點(diǎn)的組成，別的部分是松弛的，直到它們滿足約束條件；Yb的特解有時(shí)稱(chēng)作坐標(biāo)松弛步長(zhǎng)。見(jiàn)圖15.3坐標(biāo)松弛步長(zhǎng)Yb通過(guò)選擇不基矩陣B去成為A矩陣的第一列，若果選擇B作為A的第二列，那么坐標(biāo)松弛步長(zhǎng)將沿著X2軸。簡(jiǎn)單消去法不費(fèi)時(shí)，但是數(shù)值不穩(wěn)定會(huì)產(chǎn)生。如果圖15.3中這個(gè)可行集是由幾乎平行與X1軸的一條線組成的話，沿著這個(gè)坐標(biāo)軸的坐標(biāo)松弛是一個(gè)比較大的數(shù)量級(jí)。計(jì)算x作為不同的大矢量，給出數(shù)值取消。在這種情況下選擇沿著x2軸的特解會(huì)比較好，也就是說(shuō)選擇不同的基。因此，一般情況下，選擇最好的基底并不是一個(gè)簡(jiǎn)單的任務(wù)。當(dāng)這個(gè)基矩陣約束條件很少時(shí)，在定義過(guò)程中會(huì)引起數(shù)值錯(cuò)誤。為了克服過(guò)分協(xié)調(diào)松弛步長(zhǎng)的危險(xiǎn)。我們可以定義這個(gè)特解Yb作為約束條件的最小基準(zhǔn)步長(zhǎng)。這種方法是現(xiàn)在所描述的縱多消去法中的特殊情況。換句話說(shuō)，這個(gè)簡(jiǎn)單消去法說(shuō)明了可行點(diǎn)可以作為Ax=b(15.1615.35線性約束條件的一般消減法對(duì)(15.14)和（15.15）歸類(lèi)，選擇矩陣Y∈Rn×m和Z∈Rn×(n-m)，具有以下性質(zhì)：(15.16)這些屬性表明，正如（15.15）Z的列是空矩陣A的基底。因?yàn)锳有滿秩，所以A[YIZ]=[AYI0]，所以AY矩陣也是非奇異矩陣，現(xiàn)在表示線性約束Ax=b任何形式的解，如下：(15.17)對(duì)向量XY∈Rm和xZ∈Rn-m，通過(guò)15.17的取代到約束條件Ax=b得到：因此通過(guò)非奇異矩陣，可以直接被寫(xiě)成下式：(15.18)通過(guò)代替表達(dá)式(15.17)，得到任意一個(gè)向量的形式:(15.19)15.35線性約束條件的一般消減法對(duì)(15.14)和（117xz∈Rn-m的任意選擇滿足約束條件Ax=b。因此，這個(gè)問(wèn)題(15-6)可以被重新當(dāng)做如下的非約束問(wèn)題：(15.20)理想的，選擇Y使AY盡可能的滿足Ax=b條件，因?yàn)樗枰獙?duì)這個(gè)因式分解給出特解Y（AY）-1b。用一個(gè)AT的QR因式分解來(lái)計(jì)算Y和Z，AT有如下形式為：(15.21)[Q1Q2]是正交矩陣。子矩陣Q1和Q2有正交列，它們分別為n×m和n×(n-m)，而R是n×m的上三角矩陣和非奇異矩陣，是一個(gè)m×m矩陣。（在附錄(A.54)詳細(xì)的討論。）做如下定義：(15.22)因此，Y和Z的形式是Rn的一個(gè)正交基矩陣。假如我們將(15.20)展開(kāi)并做一部分從排列，我們可以得到:xz∈Rn-m的任意選擇滿足約束條件Ax=b。因此，這個(gè)問(wèn)題18因而，Y和Z有期望性質(zhì)，這樣AY的條件數(shù)和R一樣，A也是一樣的。從(15.19)中可以看出Ax=b的任何解能被表示成:對(duì)xz向量，計(jì)算這R-T∏-Tb并不是很費(fèi)時(shí)，用單一的三角代換就得到了簡(jiǎn)單的估算表明這個(gè)特征值Q1R-T∏-Tb能被寫(xiě)成(15.22)因此，這個(gè)約束條件Ax=b的最小范數(shù)解是下式的解：(15.23)因而，Y和Z有期望性質(zhì)，這樣AY的條件數(shù)和R一樣，A也是一樣19這是最小值范數(shù)解，圖(15.5)給出了這步的圖解。從數(shù)值穩(wěn)定性的觀點(diǎn)來(lái)看，消去法通過(guò)正交基矩陣(15.22)是比較理想的。主要耗時(shí)的是在(12.21)QR因子因式分解中與下降方法有關(guān)計(jì)算。不好的是，在這個(gè)問(wèn)題中矩陣大和稀疏，在簡(jiǎn)單消去法中，計(jì)算稀疏QR因子因式分解過(guò)程比稀疏高斯消去法更耗時(shí)。因此，別的一些消去分類(lèi)在這兩種方法中尋求平衡而得到了發(fā)展；可以看練習(xí)15.7.這是最小值范數(shù)解，圖(15.5)給出了這步的圖解。從數(shù)值穩(wěn)定2015.36不等式約束的作用如果不等式約束呈現(xiàn)出等式約束時(shí)變量消去法并不總是有效地。例如，問(wèn)題(15.10)，(15.11)有附加約束條件x≧0，消去變量x3和x6后，就能只剩下在(15.13)中的最小化函數(shù)問(wèn)題，約束條件是：因此，消去等式約束(15.11)的作用是使得不等式約束要比簡(jiǎn)單邊界x≧0復(fù)雜。對(duì)許多算法來(lái)說(shuō)，這個(gè)轉(zhuǎn)換并不是沒(méi)有一點(diǎn)益處。然而，假如問(wèn)題(15.11)包含一般不等式約束條件3x1+2x3≧1，這個(gè)(15.12)消去法，轉(zhuǎn)換問(wèn)題將會(huì)變成(15.12)中的函數(shù)最小化問(wèn)題在，不等式約束條件：（15.23）在等式約束消去之后，這個(gè)不等式約束并不能變的很復(fù)雜，因此，消去法是值得去做的。15.36不等式約束的作用如果不等式約束呈現(xiàn)出等式約束時(shí)2115.4優(yōu)化函數(shù)和濾波對(duì)于非線性規(guī)劃問(wèn)題(15.1)，的優(yōu)化函數(shù)是受歡迎的選擇是這個(gè)l1罰函數(shù)函數(shù)被下式定義為罰函數(shù)函數(shù)被下式定義為：（15.24）注釋[z]-=max{0，-x}。正標(biāo)量μ罰參數(shù)，這決定了分配滿足相對(duì)目標(biāo)函數(shù)的最小的約束條件的權(quán)重。由于一些列球型參數(shù)μ能確定優(yōu)化函數(shù)，這個(gè)非線性規(guī)劃問(wèn)題(15.1)的解是φ(x，μ)的一個(gè)小域。注意這個(gè)l1優(yōu)化方程φ1不可微的，因?yàn)檫@個(gè)絕對(duì)值和[]-函數(shù)是存在的，但是它有重要精確性質(zhì)。15.4優(yōu)化函數(shù)和濾波對(duì)于非線性規(guī)劃問(wèn)題(15.1)，的2215.43準(zhǔn)確的優(yōu)化函數(shù)假如對(duì)任意μ>μ*中有一個(gè)正的標(biāo)量μ*，這個(gè)優(yōu)化函數(shù)φ（x，μ）就能確定，任何一個(gè)非線性規(guī)劃問(wèn)題(15.1)的局部解是φ（x，μ）的局部最小值。在定理17.3展示的那樣，在一定的假設(shè)，l1優(yōu)化方程φ（x，μ）確定，μ*的極限值是被給λi*表示和最優(yōu)解x*有關(guān)的拉格朗日多項(xiàng)式。因?yàn)樽罴牙窭嗜粘藬?shù)是建立在包含調(diào)整罰函數(shù)參數(shù)的規(guī)則的l1優(yōu)化方程的算法，然后事先不知道，有理由相信這不是足夠大的（或者不是極大）。這些規(guī)則建立在最優(yōu)化算子的選擇，將在下一章討論。15.43準(zhǔn)確的優(yōu)化函數(shù)假如對(duì)任意μ>μ*中有一個(gè)正的標(biāo)2315.44精準(zhǔn)l2函數(shù)的增廣拉格朗日對(duì)于等式約束的情況，優(yōu)化函數(shù)用如下形式：這個(gè)函數(shù)不可微分，因?yàn)?-規(guī)范不是平方值，其衍生類(lèi)在x=0沒(méi)有定義。一些優(yōu)化函數(shù)不僅平滑而且精確。確保屬性持有，必須在優(yōu)化函數(shù)中加附加條件。對(duì)等式約束條件問(wèn)題，弗萊徹的增廣拉格朗日，通過(guò)下面的給定：15.44精準(zhǔn)l2函數(shù)的增廣拉格朗日對(duì)于等式約束的情況，24μ＞0是罰參數(shù)A（x）表示c(x)的雅克比行列式，盡管這個(gè)優(yōu)化函數(shù)有一些有趣的理論屬性，它有實(shí)際的限制，包括在（15.27）λ（x）求解代價(jià)。與眾不同的優(yōu)化函數(shù)是在x，λ的增廣拉格朗日，對(duì)等式約束問(wèn)題有如下形式：μ＞0是罰參數(shù)25通過(guò)比較LA（x+，λ+，μ）和當(dāng)前迭代（x，λ）的值來(lái)評(píng)估測(cè)試點(diǎn)的合格性，嚴(yán)格的講，感覺(jué)上LA不是優(yōu)化方程，一般來(lái)講非線性規(guī)劃問(wèn)題的解（x*，λ*）不是LA（x+，λ+，μ）的最小值，僅僅是一個(gè)駐點(diǎn)。盡管一些連續(xù)的二階規(guī)劃方法用LA通過(guò)修改模型λ和μ參數(shù)成功的作為優(yōu)化方程，但還是不考慮這做一個(gè)優(yōu)化方程，相反，把焦點(diǎn)主要放在非光滑精確罰函數(shù)Φ1Φ2。通過(guò)比較LA（x+，λ+，μ）和當(dāng)前迭代（x，λ）的值來(lái)評(píng)估26通過(guò)線性搜索算法產(chǎn)生的實(shí)驗(yàn)步長(zhǎng)x+=x+αp，如果這在優(yōu)化方程Φ（x，μ）產(chǎn)生足夠減小，那么這算法是可接受的。方法一：定義這個(gè)概念類(lèi)似于在非約束最優(yōu)化（3.4）條件，然而在這一步這個(gè)數(shù)量不能相對(duì)太小以致不能預(yù)測(cè)函數(shù)的變化。L1和l2優(yōu)化函數(shù)不可微，但有方向?qū)?shù)。（看（A.51）背景的方向?qū)?shù)）直接寫(xiě)Φ（x，μ）在p方向的方向?qū)?shù)：D（Φ（x，μ），p）用線性搜索法，足夠減少的條件要求是迭代步長(zhǎng)參數(shù)α>0，足夠小以致如下不等式對(duì)于η∈（0，1）滿足：通過(guò)線性搜索算法產(chǎn)生的實(shí)驗(yàn)步長(zhǎng)x+=x+αp，如果這在優(yōu)化方27經(jīng)過(guò)p步長(zhǎng)后，信賴域方法常用二階模型q(p)來(lái)評(píng)估優(yōu)化函數(shù)Φ，如18.5部分。足夠的減少條件能用這個(gè)模型減少的形式規(guī)定，如下：非線性約束最優(yōu)化算法ppt課件2815.45濾波濾波技術(shù)是一步接受原理建立在多目標(biāo)最優(yōu)化問(wèn)題的基礎(chǔ)上。從觀測(cè)非線性規(guī)劃推導(dǎo)有兩個(gè)目的：目標(biāo)函數(shù)的最小化函數(shù)和滿足約束條件。定義不可行域估量：把這兩個(gè)目標(biāo)寫(xiě)成：不同于優(yōu)化函數(shù)，這結(jié)合所有問(wèn)題到單一的最小化問(wèn)題，濾波方法在（15.32）分開(kāi)保持這兩個(gè)目標(biāo)。如果

不受控前一個(gè)通過(guò)算法產(chǎn)生的

，濾波方法接受測(cè)試步長(zhǎng)x+做一個(gè)新的迭代，這些概念被定義如下：15.45濾波濾波技術(shù)是一步接受原理建立在多目標(biāo)最優(yōu)化問(wèn)題29定義15.2fk≦fl和hk≦hl則，（fk，hk）是被（fl，hl）控制，濾波是對(duì)（fl，hl）的列表，如此沒(méi)有任何一對(duì)占主導(dǎo)地位，迭代xk是對(duì)濾波可接受的。當(dāng)?shù)鷛k是對(duì)濾波可接受，我們一般加（fk，hk）到濾波，移除被（fk，hk）支配的任何對(duì)，圖示15.6展示了濾波中每一對(duì)（fl，hl）用黑點(diǎn)表示。每一個(gè)濾波形成一個(gè)矩形區(qū)域，這個(gè)結(jié)合定義一個(gè)組隊(duì)對(duì)濾波不可接受。更特殊的，如果（f+，h+）在實(shí)線的下面或者左邊（圖15.6），測(cè)試點(diǎn)x+是可接受的。比較濾波和優(yōu)化函數(shù)方法，在圖15.7繪制了組對(duì)（f，h）的輪廓線，這樣f+uh=fk+uhk，xk是當(dāng)前迭代，該區(qū)域線的左邊和雙集一致，減少優(yōu)化函數(shù)φ（x，μ=f(x)+μh(x)，很明顯，這個(gè)集完全不同與接受點(diǎn)。如果通過(guò)線搜索方法所產(chǎn)生一個(gè)試驗(yàn)步長(zhǎng)x+=xk+αkpk給出給一對(duì)(f+，h+)，這是可接受的濾波波，設(shè)置xk+1=x+，否則，執(zhí)行回溯線性搜索。在信賴域方法中，如果濾波這步驟不可行，信賴區(qū)域減少，計(jì)算新步驟。定義15.230當(dāng)?shù)鷛k是對(duì)濾波可接受，我們一般加（fk，hk）到濾波，移除被（fk，hk）支配的任何對(duì)，圖示15.6展示了濾波中每一對(duì)（fl，hl）用黑點(diǎn)表示。每一個(gè)濾波形成一個(gè)矩形區(qū)域，這個(gè)結(jié)合定義一個(gè)組隊(duì)對(duì)濾波不可接受。更特殊的，如果（f+，h+）在實(shí)線的下面或者左邊（圖15.6），測(cè)試點(diǎn)x+是可接受的。當(dāng)?shù)鷛k是對(duì)濾波可接受，我們一般加（fk，hk）到濾波，移31如果通過(guò)線搜索方法所產(chǎn)生一個(gè)試驗(yàn)步長(zhǎng)x+=xk+αkpk給出給一對(duì)(f+，h+)，這是可接受的濾波波，設(shè)置xk+1=x+，否則，執(zhí)行回溯線性搜索。在信賴域方法中，如果濾波這步驟不可行，信賴區(qū)域減少，計(jì)算新步驟。這個(gè)濾波技術(shù)需要作一些改進(jìn)，從而獲得全局收斂性和良好的實(shí)用性能。首先，我們需要確保我們不接受一點(diǎn)(f、h)對(duì)是非常接近當(dāng)前的一對(duì)(fk，hk)或在濾波中的其他對(duì)。通過(guò)修改可行準(zhǔn)則和實(shí)現(xiàn)充分下降條件。濾波是接受測(cè)試迭代x+，如果濾波中所有(hf，hj)，有如下條件：如果通過(guò)線搜索方法所產(chǎn)生一個(gè)試驗(yàn)步長(zhǎng)x+=xk+αkpk給出32β∈(0，1)。雖然這條件在實(shí)踐使用中有效，說(shuō)β=10?5，分析的目的，通過(guò)下面的式子，它可能有利于取代第一個(gè)不平等的。通過(guò)線性搜索方法生成的搜索方向的可能需要足夠小步長(zhǎng)αk，這樣濾波才可行。這種現(xiàn)象可以導(dǎo)致算法陷入停滯和失敗。為了防止這種情況，如果回溯線搜索生成一個(gè)步長(zhǎng)比極值αmin小，該算法切換到可行性恢復(fù)階段。非線性約束最優(yōu)化算法ppt課件33可行性恢復(fù)階段主要目的是減少相反的約束條件，也就是說(shuō)，找到一個(gè)近似的解決問(wèn)題的辦法。現(xiàn)在列舉濾波步驟，假設(shè)由信賴域方法生成迭代的，參見(jiàn)18.5節(jié)信賴域方法約束優(yōu)化討論。算法15.1(一般濾波方法)選擇起點(diǎn)x0，初始信賴域半徑Δ0設(shè)置k←0，重復(fù)，直到滿足收斂測(cè)試可行性恢復(fù)階段主要目的是減少相反的約束條件，也就是說(shuō)，找到一34If步驟生成子問(wèn)題不可行用可行性恢復(fù)階段計(jì)算xk+1else計(jì)算試驗(yàn)迭代x+=xk+pkIf(f+，h+)濾波可以接受設(shè)置xk+1=x+并添加(fk+1，hk+1)濾波選擇Δk+1，Δk+1≥Δk從濾波中刪除所有主導(dǎo)對(duì)由(fk+1，hk+1)Else丟棄這一步驟中，If步驟生成子問(wèn)題不可行35設(shè)置xk+1=xk選擇Δk+1<ΔkEndifEndifk←k+1，endrepeat這個(gè)簡(jiǎn)單的濾波步驟的其他改進(jìn)用于實(shí)踐，建立在算法的選擇上，將在后續(xù)的章節(jié)中討論。設(shè)置xk+1=xk3615.5

馬洛托斯現(xiàn)象一些算法基于優(yōu)化函數(shù)或?yàn)V波可能在迅速收斂失敗，因?yàn)閬G棄朝著解的方向進(jìn)的步驟。這種不良現(xiàn)象通常被稱(chēng)為馬洛托斯效應(yīng)，因?yàn)樗潜获R洛托斯[199]首次發(fā)現(xiàn)。通過(guò)下面的例子說(shuō)明，在哪些步驟pk，如果接受這將產(chǎn)生二階收斂，導(dǎo)致目標(biāo)函數(shù)值和違反約束條件的增加15.5馬洛托斯現(xiàn)象一些算法基于優(yōu)化函數(shù)或?yàn)V波可能在迅速37考慮問(wèn)題可以驗(yàn)證(見(jiàn)圖15.8)最佳解是x?=(1，0)T，對(duì)應(yīng)的拉格朗日乘子λ*=3/2，讓我們考慮xk=(cosθ，sinθ)形式的迭代xk，這對(duì)于任何θ值可行。假設(shè)算法的計(jì)算步驟如下:測(cè)試點(diǎn)考慮問(wèn)題38通過(guò)使用基本三角轉(zhuǎn)換，有因此因此，這一步的方法的解與Q二階收斂速度一致。然后，有因此，在圖15.8中可以看到，這一步目標(biāo)函數(shù)值和約束違反增加。這種行為發(fā)生在任何θ非零值，即使任意初始點(diǎn)接近解。通過(guò)使用基本三角轉(zhuǎn)換，有39在上面的示例中，任何算法，需要優(yōu)化函數(shù)減少的形式：h(?)是一個(gè)非負(fù)函數(shù)，滿足h(0)=0，將丟棄(15.35)好步驟。(這樣的優(yōu)化函數(shù)的例子包括φ1和φ2罰函數(shù))。(15.35)步驟也將被上述的濾波原理丟棄，因?yàn)?f(xk+pk)，h(xk+pk))是由(fk，hk)控制。因此，所有這些方法有馬洛托斯現(xiàn)象。在上面的示例中，任何算法，需要優(yōu)化函數(shù)減少的形式：40如果沒(méi)有采取補(bǔ)救措施，馬洛托斯現(xiàn)象可能從解中通過(guò)干擾好步驟或防止超線性收斂，減緩優(yōu)化方法。避免馬洛托斯現(xiàn)象的策略包括如下：用不受馬洛托斯現(xiàn)象的優(yōu)化函數(shù)，。例子是弗萊徹的增廣拉格朗日函數(shù)(15.26)。用二階校正，pk增加步p’k，在c(xk+pk)計(jì)算，減少了約束違反。允許優(yōu)化函數(shù)φ增加某些迭代，也就是說(shuō)，可以使用非單調(diào)。在下一節(jié)中將討論最后的兩種方法。如果沒(méi)有采取補(bǔ)救措施，馬洛托斯現(xiàn)象可能從解中通過(guò)干擾好步驟或4115.6二階校正和非單調(diào)技術(shù)通過(guò)添加修正項(xiàng)，減少了約束違反，各種算法能夠克服馬洛托斯現(xiàn)象有關(guān)難題。用等式約束條件問(wèn)題描述這方法，約束條件是c（x）=0，Rn趨近RIεI給定步長(zhǎng)pk，p’k的二階校正步長(zhǎng)定義：Ak=A(xk)是c在xk雅可比。注意p’k的屬性，在xk+pk點(diǎn)它滿足了線性化的約束c，也就是說(shuō)：事實(shí)上，p’k是這個(gè)等式的最小范數(shù)解。15.6二階校正和非單調(diào)技術(shù)通過(guò)添加修正項(xiàng)，減少了約束違42校正步長(zhǎng)p’k的效果是對(duì)Ixk?x?I3的規(guī)則減少I(mǎi)c(x)I量，，主要步驟pk滿足Akpk+pk+c(xk)=0。這個(gè)估計(jì)表明，從xk到xk+pk+p’k將減少優(yōu)化函數(shù)，至少靠近解。此增強(qiáng)功能包括約束函數(shù)c在xk+pk額外的評(píng)估和從(15.36)所需的線性代數(shù)來(lái)預(yù)訂步長(zhǎng)p’k?，F(xiàn)在描述用線性搜索和二階修正步長(zhǎng)的優(yōu)化函數(shù)算法。假設(shè)pk和搜索方向計(jì)算的罰參數(shù)μk，pk是優(yōu)化函數(shù)下降方向，也就是說(shuō)，D(φ(xk，μ)，pk)<0。在18和19章，將討論如何完成這些目標(biāo)。算法的主要特征是，如果完整的步驟αk=1，在優(yōu)化函數(shù)不會(huì)產(chǎn)生滿意的下降，在回溯沿著pk原來(lái)的方向之前嘗試二階校正步驟。校正步長(zhǎng)p’k的效果是對(duì)Ixk?x?I3的規(guī)則減少I(mǎi)c(x)43算法15.2(用二階校正的通用算法)。選擇參數(shù)η∈(0，-0.5)和τ1τ2與0<τ1<τ2<1，選擇初始點(diǎn)x0設(shè)置k←0，重復(fù)，直到滿足收斂測(cè)試:計(jì)算一個(gè)搜索方向pk，設(shè)置αk←1，新點(diǎn)←假，while新點(diǎn)=falseifφ(xk+αkpk，μ)≤φ(xk，μ)+ηαkD(φ(xk，μ)，pk)設(shè)置xk+1←xk+αkpk設(shè)置新點(diǎn)t←正確，Elseifαk=1從(15.36)計(jì)算p’k，Ifφ(xk+pk+p’k，μ)≤φ(xk，μ)+ηD(φ(xk，μ)，pk)設(shè)置xk+1←xk+pk+p’k，算法15.2(用二階校正的通用算法)。44設(shè)置新點(diǎn)←正確，Else選擇新αk[τ1αkτ2αk]，ENDELSE選擇新αk在[τ1αk，τ2αk]，EndEndwhileEndrepeat在該算法中，如果在優(yōu)化函數(shù)作用沒(méi)有減少完整的二階校正步長(zhǎng)p’k丟棄。放棄pk+p,k方向追蹤，因?yàn)樗荒鼙ＷC是優(yōu)化函數(shù)的下降方向。該算法的變化應(yīng)適用于二階修正步長(zhǎng)，只有(15.29)條件充分下降，在規(guī)范約束條件下增長(zhǎng)的結(jié)果是違反的。二階校正策略在實(shí)踐中是有效的。執(zhí)行額外的約束函數(shù)評(píng)估的和在（15.36）額外的回執(zhí)代價(jià)勝過(guò)增加健壯性和效率。設(shè)置新點(diǎn)←正確，45非單調(diào)性的策略馬洛托斯現(xiàn)象造成的低效也可以避免，偶爾的接受增加優(yōu)化函數(shù)步驟，這些措施被稱(chēng)為松弛步驟。耐性有限制，然而如果優(yōu)化函數(shù)足夠的減少?zèng)]有獲得一定數(shù)量的松弛步長(zhǎng)的迭數(shù)(t’迭代)返回迭代，在松弛步長(zhǎng)前返回迭代步長(zhǎng)，執(zhí)行正常的迭代，在優(yōu)化函數(shù)中用線性搜索或其他方法強(qiáng)制減少。與二階修正相比，唯一目的是提高約束條件的滿意度，這種非單調(diào)策略總是常規(guī)算法的步長(zhǎng)pk，目的都是提高可