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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、。,43,理想點法： 構造如下單目標最優(yōu)化問題：,可以證明，該問題的最優(yōu)解是一個最接近完全最優(yōu)解的有效解，因此叫做理想點法。,該問題的最優(yōu)解即考慮了各個分目標的重要性，又接近與完全最優(yōu)解。,引入權因子，改寫成：,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為目標函數(shù)，x0為初始值，options為設置參數(shù)。 A和b為線性不等式約束，AXb；Aeq和beq為線性等式約束，Aeq=beq； lb和ub分別為變量x的下限和上限；nonlcon為非線性約束,45,例6.1 用MATLAB求解：,建立目標函數(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ù)與運行程序 x0=1,1; opt=optimset(Display,iter); x,fval,exitflag,output=fmincon(optimfun,x0,0,nonlconfun,opt);,46,例6.5 用MATLAB求解：初始點(s,t)=(1,2),建立目標函數(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ù)與運行程序 A=2 3; -1 1; b=2; 5; %線性不等式約束 x0=1,2;%初始值 opt=optimset(Display,iter); %參數(shù)設定 x,fval,exitflag,output=fmincon(optimfun,x0,A,b,nonlconfun,opt),6.6 約束最優(yōu)化問題應用實例,47,最大體積問題： 最大體積問題指的是在給定表面積一定的前提下，確定容積的最大值，隨著實際問題的不同，不一定是給定