約束最優(yōu)化.ppt

1、最優(yōu)化方法,濟(jì)南大學(xué)控制科學(xué)與工程學(xué)院,授課教師：李實(shí),cse_ 1教1007室,第六章 約束最優(yōu)化方法,6.1 懲罰函數(shù)法 6.2 乘子法 6.3 序列二次規(guī)劃法 6.4 多目標(biāo)最優(yōu)化方法 6.5 MATLAB求解約束最優(yōu)化問題 6.6 約束最優(yōu)化問題應(yīng)用實(shí)例,2,3,約束最優(yōu)化方法是用來求解如下非線性約束最優(yōu)化問題的數(shù)值迭代算法：,求解約束最優(yōu)化問題的關(guān)鍵在于如何處理各種約束條件。根據(jù)處理約束條件的不同方式，其求解方法分為直接法和間接法兩類： 直接法：在迭代過程中逐點(diǎn)考察約束，并使迭代點(diǎn)始終局限于可行域之內(nèi)的算法稱為直接法，如可行方向法。 間接法：將約束條件引入目標(biāo)函數(shù)，使約束最優(yōu)化問題轉(zhuǎn)

2、化為無約束最優(yōu)化問題求解，或者將非線性問題轉(zhuǎn)化為相對簡單的二次規(guī)劃問題或線性規(guī)劃問題求解，如懲罰函數(shù)法、乘子法、序列二次規(guī)劃法。,6.1 懲罰函數(shù)法,4,懲罰函數(shù)法是一種將約束最優(yōu)化問題轉(zhuǎn)化為無約束最優(yōu)化問題求解的算法。 對于約束最優(yōu)化問題：,構(gòu)造無約束問題：,為懲罰函數(shù),是由不等式約束函數(shù)構(gòu)成的復(fù)合函數(shù),是由等式約束函數(shù)構(gòu)成的復(fù)合函數(shù),當(dāng)X在約束可行域之外時(shí)，第二項(xiàng)與第三項(xiàng)的值很大，看做對目標(biāo)函數(shù)加以懲罰。或者當(dāng)X在約束邊界附近時(shí)，第二項(xiàng)和第三項(xiàng)的函數(shù)值趨于無窮大，使得函數(shù)在約束邊界筑起一道圍墻，迫使迭代點(diǎn)局限在可行域內(nèi)移動。,懲罰因子,6.1.1 外點(diǎn)法,5,構(gòu)造懲罰函數(shù)：,對于不等式約束

3、條件：,可以證明，當(dāng)懲罰因子按一個(gè)遞增的正數(shù)序列變化時(shí)：,懲罰因子rk取一正數(shù)，當(dāng)X點(diǎn)在可行域內(nèi)，gu(X)0，max(gu(X),0)=0，懲罰項(xiàng)為零，懲罰函數(shù)的極小問題變?yōu)槟繕?biāo)函數(shù)的無約束極小問題。當(dāng)X點(diǎn)在可行域外，gu(X)0, max(gu(X),0)=gu(X)，懲罰項(xiàng)為正數(shù)，對懲罰函數(shù)求極小。,取復(fù)合函數(shù)：,6,所得極小點(diǎn)序列：,對于等式約束問題，可按同樣思想構(gòu)造懲罰函數(shù)，即：,是逐步逼近不等式約束問題的最優(yōu)解的,依次求解每個(gè)rk對應(yīng)的懲罰函數(shù)極小值問題,一般情況下，該極小點(diǎn)序列是由可行域外部向可行域的邊界或內(nèi)部逼近的。 這種方法稱為外點(diǎn)罰函數(shù)法，簡稱外點(diǎn)法。,對于一般性約束問題，

4、將不等式約束與等式約束復(fù)合函數(shù)組合：,7,外點(diǎn)懲罰函數(shù)的形態(tài)和求解過程可以用下圖所示的一維問題加以說明，圖中的各種曲線分別代表目標(biāo)函數(shù)f(X)和幾個(gè)不同懲罰因子所對應(yīng)的懲罰函數(shù)的圖形：,由圖可以看出： 在可行域內(nèi)，懲罰函數(shù)與目標(biāo)函數(shù)重合，忽略約束條件。在可行域外，將約束條件與目標(biāo)函數(shù)構(gòu)成懲罰函數(shù)，懲罰函數(shù)的曲線被逐漸抬高，離約束邊界越近，曲線被抬高越多。 懲罰因子的值越大，懲罰函數(shù)被抬高越多，極小點(diǎn)越接近約束邊界。 懲罰因子趨于無窮大時(shí)，懲罰函數(shù)的極小點(diǎn)就是約束最優(yōu)化問題的最優(yōu)點(diǎn)。,8,外點(diǎn)法是針對落在可行域外的迭代點(diǎn)函數(shù)值加以懲罰，迫使迭代點(diǎn)向可行域的邊界或內(nèi)部逐步逼近的算法。因此，初始點(diǎn)可

5、以是內(nèi)點(diǎn)，也可以是外點(diǎn)。外點(diǎn)法可以處理不等式約束與等式約束問題，適應(yīng)性較好。,外點(diǎn)法的迭代步驟如下：,給定初始點(diǎn)X0，收斂精度，初始懲罰因子r0和懲罰因子遞增系數(shù)c，置k=0 構(gòu)造懲罰函數(shù)： 求解無約束最優(yōu)化問題： 終止判斷，滿足： 迭代終止，否則，k=k+1，轉(zhuǎn),9,例6.1 用外點(diǎn)法求解約束最優(yōu)化問題：,解： 構(gòu)造懲罰函數(shù)，轉(zhuǎn)化為無約束最優(yōu)化問題：, 求解無約束最優(yōu)化問題，因?yàn)閼土P函數(shù)構(gòu)造簡單，可以直接用極值條件求解，即令懲罰函數(shù)的一階導(dǎo)數(shù)等于零：,可行域內(nèi)： ，均不等于零，可知可行域內(nèi)無極值點(diǎn)。,10,聯(lián)立求解，得到：,取一組遞增的懲罰因子，得到懲罰函數(shù)的一組極小點(diǎn)，分別是：,可行域外：

6、,11,外點(diǎn)法的迭代路線如下圖所示，向約束問題的最優(yōu)點(diǎn)0, 0T逐步逼近。 虛線所示,6.1.2 內(nèi)點(diǎn)法,12,構(gòu)造懲罰函數(shù)：,內(nèi)點(diǎn)法是另一種懲罰函數(shù)法，其懲罰函數(shù)構(gòu)成形式與外點(diǎn)法類似，但要求迭代過程始終限制在可行域內(nèi)進(jìn)行。,對于不等式約束：,取復(fù)合函數(shù)：,倒數(shù)形式,對數(shù)形式,13,由上式可以看出，給定懲罰因子rk為正數(shù)，當(dāng)點(diǎn)在可行域內(nèi)，懲罰項(xiàng)的值大于零，當(dāng)點(diǎn)靠近約束邊界時(shí)，懲罰項(xiàng)迅速增大并趨于無窮。也就是說，當(dāng)初始點(diǎn)X0取在可行域內(nèi)，迭代點(diǎn)Xk不能超出可行域的邊界。,可以證明，當(dāng)懲罰因子按一個(gè)遞減的正數(shù)序列變化時(shí)：,并且初始點(diǎn)X0為內(nèi)點(diǎn)，得到的極小點(diǎn)序列是逐步向約束問題的最優(yōu)點(diǎn)逼近的：,從懲

7、罰函數(shù)的構(gòu)成可以看出，內(nèi)點(diǎn)法不適用于等式約束，并且要求初始點(diǎn)必須為內(nèi)點(diǎn)，這對于約束條件較多或約束函數(shù)較為復(fù)雜的問題不太方便。但是，內(nèi)點(diǎn)法在一次求解中除了得到最優(yōu)解之外，還可以提供一系列不斷變化的近似最優(yōu)解，供設(shè)計(jì)者進(jìn)一步分析選用。,14,內(nèi)點(diǎn)懲罰函數(shù)的形態(tài)和求解過程可以用下圖所示的一維問題加以說明，圖中的各種曲線分別代表目標(biāo)函數(shù)f(X)和幾個(gè)不同懲罰因子所對應(yīng)的懲罰函數(shù)的圖形：,由圖可以看出： 懲罰函數(shù)的有效區(qū)域是約束的可行域，目標(biāo)函數(shù)在可行域內(nèi)的所有點(diǎn)都受到懲罰，越靠近邊界懲罰越多。 不同的懲罰因子對應(yīng)不同的懲罰函數(shù)，懲罰因子越小，懲罰函數(shù)的極小點(diǎn)越接近與邊界處的最優(yōu)點(diǎn)。 當(dāng)懲罰因子趨近與零

8、時(shí)，懲罰函數(shù)的極小點(diǎn)就是原約束問題的最優(yōu)點(diǎn)。,15,內(nèi)點(diǎn)法的迭代步驟如下：,給定初始點(diǎn)X0，收斂精度，初始懲罰因子r0和懲罰因子遞減系數(shù)c，置k=0 構(gòu)造懲罰函數(shù)： 求解無約束最優(yōu)化問題： 終止判斷，滿足： 迭代終止，否則，k=k+1，轉(zhuǎn),16,例6.2 用內(nèi)點(diǎn)法求解約束最優(yōu)化問題：,解： 構(gòu)造懲罰函數(shù)，轉(zhuǎn)化為無約束最優(yōu)化問題：, 求解無約束最優(yōu)化問題，因?yàn)閼土P函數(shù)構(gòu)造簡單，可以直接用極值條件求解，即令懲罰函數(shù)的一階導(dǎo)數(shù)等于零：,17,聯(lián)立求解，得到：,取一組遞減的懲罰因子，得到懲罰函數(shù)的一組極小點(diǎn)，分別是：,18,外點(diǎn)法的迭代路線如下圖所示，向約束問題的最優(yōu)點(diǎn)0, 0T逐步逼近 虛線所示。,

9、6.1.3 混合法,19,混合法是綜合外點(diǎn)法和內(nèi)點(diǎn)法的優(yōu)點(diǎn)建立的一種算法，對不等式約束條件按內(nèi)點(diǎn)法建立懲罰項(xiàng)，對等式約束條件按外點(diǎn)法建立懲罰項(xiàng)，由此得到懲罰函數(shù)：,其中，懲罰因子rk1取正的遞減數(shù)列，rk2取正的遞增數(shù)列。,或?qū)蓚€(gè)懲罰因子合并，令rk=rk1=1/rk1，得到懲罰函數(shù)：,6.2 乘子法,20,懲罰函數(shù)法具有方法簡單、使用方便等優(yōu)點(diǎn)。但它存在固有的缺點(diǎn)：隨著懲罰因子趨向與極限值，帶來懲罰函數(shù)計(jì)算上的困難。為了克服這一困難，Hestenes和Powell與1969年各自提出了乘子法。,等式約束問題的乘子法,對于等式約束問題：,用外點(diǎn)法建立的極小化問題：,當(dāng)rk足夠大時(shí)，得到最優(yōu)解

10、Xk，由懲罰函數(shù)梯度等于零，可以得到：,21,要使Xk接近于極小點(diǎn)X*， 應(yīng)充分接近 。由于 ，上式右端也應(yīng)接近與零。但是對于約束最優(yōu)化問題， 一般并不等于零，因此只有無線增大rk的值來滿足極值條件。要解決這個(gè)問題，可以尋找一個(gè)在最優(yōu)點(diǎn)處梯度等于零的函數(shù)去取代f(X)。,考慮等于約束問題的拉格朗日函數(shù)：,根據(jù)極值條件，如果等式約束問題有解，必存在乘子向量使得：,22,對應(yīng)的無約束最優(yōu)化問題：,稱為增廣拉格朗日函數(shù)?？梢宰C明，如果知道最優(yōu)乘子向量*，那么只要取足夠大的懲罰因子rk，而不需要使其趨向無窮大，就能得到原等式約束問題的最優(yōu)解，這就是乘子法的基本思想。,該拉格朗日函數(shù)的梯度必等于零，可用

11、其代替原函數(shù)f(X)，因此得到新的等于約束最優(yōu)化問題：,23,增廣拉格朗日函數(shù)的梯度等于零：,由以上兩式，可得：,然而，最優(yōu)乘子向量*是不能預(yù)先得到的。一般的方法是，先給定足夠大的懲罰因子rk和初始向量0，然后在迭代過程中逐步修正k，使其趨向* 。,等式約束問題的k-t條件：,實(shí)際迭代過程中，將上式看作乘子向量的修正公式：,24,不等式約束問題的乘子法,對于不等式約束問題：,引入變量zu(u=1,2,p)，將不等式約束化為等式約束：,根據(jù)上節(jié)介紹的等式約束問題，建立增廣拉格朗日函數(shù)：,令 ，得到,25,可以得到，當(dāng)時(shí),當(dāng) 時(shí),26,綜合以上兩種情況，可將增廣拉格朗日函數(shù)寫為：,根據(jù)上節(jié)等式約束

12、推導(dǎo)最優(yōu)乘子向量，同理可得,終止準(zhǔn)則：,27,一般約束問題的乘子法,綜合以上兩個(gè)約束問題的乘子法，得到增廣目標(biāo)函數(shù)：,拉格朗日乘子迭代公式：,終止準(zhǔn)則：,28,乘子法的迭代步驟如下：,給定初始點(diǎn)X0，收斂精度，初始懲罰因子r0和懲罰因子遞減系數(shù)c，初始乘子向量0和0，置k=0 構(gòu)造增廣目標(biāo)函數(shù)： 求解無約束最優(yōu)化問題： 終止判斷，滿足終止準(zhǔn)則，迭代終止，否則，k=k+1，rk+1=c*rk， 轉(zhuǎn),29,例6.3 用乘子法求解約束最優(yōu)化問題：,解： 構(gòu)造增廣目標(biāo)函數(shù),直接用極值條件求解，得到極小值：,30,因?yàn)槌俗酉禂?shù)一般為正值，將x1=0點(diǎn)舍去，得到：,乘子的迭代公式為：,取rk=1, 0=0

13、，得到：,可以增大懲罰因子rk來提高逼近速度。,6.3序列二次規(guī)劃算法,31,序列二次規(guī)劃(Sequential Quadratic Programming, SQP)算法是將復(fù)雜的非線性約束最優(yōu)化問題轉(zhuǎn)化為比較簡單的二次規(guī)劃問題求解的算法。 將目標(biāo)函數(shù)簡化為二次函數(shù)，將約束函數(shù)簡化為線性函數(shù)。,將其簡化為二次規(guī)劃問題：,對于約束非線性最優(yōu)化問題：,32,將其寫成二次規(guī)劃問題的一般形式：,其中：,求解該二次規(guī)劃問題，并將其最優(yōu)解S*作為原問題的下一個(gè)搜索方向Sk，進(jìn)行搜索，得到原約束問題的下一個(gè)迭代點(diǎn)Xk+1，再代入二次規(guī)劃問題，得到新的最優(yōu)解，反復(fù)迭代，最后得到原問題的最優(yōu)解。,33,序列二

14、次規(guī)劃算法的迭代步驟如下：,給定初始點(diǎn)X0，收斂精度，令H0=I（單位矩陣），置k=0 在點(diǎn)Xk將原問題簡化為二次規(guī)劃問題： 求解該二次規(guī)劃問題，將得到的最優(yōu)解S*看作原問題的迭代方向Sk 在方向Sk上對原問題的目標(biāo)函數(shù)進(jìn)行一維搜索，得到最優(yōu)解X*，記做Xk+1 終止判斷，滿足終止準(zhǔn)則，迭代終止，否則，k=k+1，并用變尺度法修正二階導(dǎo)數(shù)矩陣Hk+1，轉(zhuǎn),34,二階導(dǎo)數(shù)矩陣H的修正：,采用變尺度法： DFP公式,BFGS公式,35,二次規(guī)劃問題的求解：,等式約束二次規(guī)劃問題：,其拉格朗日函數(shù)為：,由多元函數(shù)的極值條件，L的一階導(dǎo)數(shù)等于零，可得：,與等式約束聯(lián)立：,得到：,36,上式方程數(shù)與變量

15、數(shù)都為n+m，無解或有唯一解，如果有唯一解，根據(jù)k-t條件，只要不全為零，得到的Sk即為最優(yōu)解，可將其作為原約束問題的迭代方向Sk,一般性約束二次規(guī)劃問題：,由第二章最優(yōu)性條件討論可知，將起作用不等式約束條件變?yōu)榈仁郊s束條件，再構(gòu)造拉格朗日函數(shù)，根據(jù)極值條件，最后推導(dǎo)出具有極值的k-t條件：對于其作用不等式約束的拉格朗日向量必須為非負(fù)。 具體的推導(dǎo)過程，這里忽略。 求得的方向Sk作為原約束問題的迭代方向，繼續(xù)求解。,37,例6.4 求解二次規(guī)劃問題：,解： 變?yōu)槎我?guī)劃形式,初始點(diǎn)為0 0 0T.,38,建立拉格朗日函數(shù)：,由極值條件，取梯度等于零，與等式約束聯(lián)立，可得：,由k-t條件，不全為

16、零可知，S為極值點(diǎn)，因此S為二次規(guī)劃問題的最優(yōu)解。,6.4 多目標(biāo)最優(yōu)化方法,39,實(shí)際工程問題通常有多種評價(jià)設(shè)計(jì)質(zhì)量好壞的技術(shù)經(jīng)濟(jì)指標(biāo)。若將這多個(gè)技術(shù)經(jīng)濟(jì)指標(biāo)都寫作設(shè)計(jì)變量的函數(shù)，就構(gòu)成了多個(gè)目標(biāo)函數(shù)或設(shè)計(jì)目標(biāo)，分別記做f1(X), f2(X), , fq(X)。由此建立起來的數(shù)學(xué)模型,稱為多目標(biāo)優(yōu)化問題，簡稱多目標(biāo)問題。,40,多目標(biāo)問題一般不可能存在使每一個(gè)目標(biāo)都同時(shí)達(dá)到最優(yōu)的完全最優(yōu)解，只能對多個(gè)優(yōu)化目標(biāo)進(jìn)行折中，找到相對最優(yōu)解。 使每個(gè)目標(biāo)函數(shù)都取得極小點(diǎn)的解成為完全最優(yōu)解。 至少使一個(gè)目標(biāo)函數(shù)取得最小值的解稱為劣解。 除了完全最優(yōu)解與劣解，剩下的解均稱為有效解。 多目標(biāo)最優(yōu)化方法是

17、根據(jù)不同目標(biāo)的重要性對各個(gè)目標(biāo)進(jìn)行加權(quán)量化，求得一個(gè)相對最優(yōu)的有效解。 多目標(biāo)最優(yōu)化問題一般都是轉(zhuǎn)化為單目標(biāo)問題求解的，如主要目標(biāo)法、線性加權(quán)法、理想點(diǎn)法,41,主要目標(biāo)法： 在所有技術(shù)經(jīng)濟(jì)指標(biāo)中選出一個(gè)最重要的指標(biāo)作為設(shè)計(jì)的目標(biāo)函數(shù)，而將其他的指標(biāo)分別給定一個(gè)可以接受的范圍，轉(zhuǎn)變?yōu)橐唤M約束條件，從而構(gòu)成一個(gè)單目標(biāo)最優(yōu)化問題，這就是主要目標(biāo)法。,42,線性加權(quán)法： 由q個(gè)目標(biāo)函數(shù)構(gòu)成如下綜合評價(jià)函數(shù)：,得到單目標(biāo)約束最優(yōu)化問題：,式中wi是反應(yīng)各個(gè)分目標(biāo)重要性的一組系數(shù)，稱為權(quán)因子，權(quán)因子的選擇決定了最優(yōu)化問題的最優(yōu)解。一般可以按下式計(jì)算：,是以第i個(gè)分目標(biāo)為目標(biāo)函數(shù)所構(gòu)成的單目標(biāo)問題的最優(yōu)值

18、。,43,理想點(diǎn)法： 構(gòu)造如下單目標(biāo)最優(yōu)化問題：,可以證明，該問題的最優(yōu)解是一個(gè)最接近完全最優(yōu)解的有效解，因此叫做理想點(diǎn)法。,該問題的最優(yōu)解即考慮了各個(gè)分目標(biāo)的重要性，又接近與完全最優(yōu)解。,引入權(quán)因子，改寫成：,6.5 MATLAB求解約束最優(yōu)化,44,MATLAB中用于求解約束優(yōu)化問題的函數(shù)為 fmincon, 采用序列二次規(guī)劃法，其中每一次用二次規(guī)劃逼近，Hessian矩陣修正采用BFGS變尺度法,x,fval,exitflag,output=fminunc(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)：x為最優(yōu)解，fval為最優(yōu)值，exitflag輸

19、出1或0，為是否成功找到最優(yōu)值，output輸出迭代次數(shù)、迭代方法等。 fun為目標(biāo)函數(shù)，x0為初始值，options為設(shè)置參數(shù)。 A和b為線性不等式約束，AXb；Aeq和beq為線性等式約束，Aeq=beq； lb和ub分別為變量x的下限和上限；nonlcon為非線性約束,45,例6.1 用MATLAB求解：,建立目標(biāo)函數(shù)的*.m文件，命名為optimfun.m function y=optimfun(x) y=x(1)+x(2); g1為非線性不等式約束，g2可做變量的下限約束。 建立非線性不等式約束的 .m file, 命名為nonlconfun.m function c,ceq=non

20、lconfun(x) c=x(1)2-x(2); ceq=; 最后在MATLAB窗口輸入?yún)?shù)與運(yùn)行程序 x0=1,1; opt=optimset(Display,iter); x,fval,exitflag,output=fmincon(optimfun,x0,0,nonlconfun,opt);,46,例6.5 用MATLAB求解：初始點(diǎn)(s,t)=(1,2),建立目標(biāo)函數(shù)的*.m文件，命名為optimfun.m function y=optimfun(x) y=x(1)4-4*x(1)-8*x(2)+15; 建立非線性不等式約束的 .m file, 命名為nonlconfun.m function c,ceq=nonlconfun(x) c=9-x(1)2-x(2)2; ceq=; 最后在MATLAB窗口輸入?yún)?shù)與運(yùn)行程序 A=2 3; -1 1; b=2; 5; %線性不等式約束 x0=1,2;%初始值 opt=optimset(Display,iter); %參數(shù)設(shè)定 x,fval,exitflag,output=fmincon(optimfun,x0,A,b,nonlconfun,opt),6.6 約束最優(yōu)化問題應(yīng)用實(shí)例,47,最大體積問題： 最大體積問題指的是在給定表面積一定的前提下，確定容積的最大值，隨著實(shí)際問題的不同，不一定是給定