第五章約束優(yōu)化方法

第五章約束優(yōu)化方法第1頁，共68頁，2023年，2月20日，星期三2概述約束優(yōu)化問題最優(yōu)解最優(yōu)值最優(yōu)點(diǎn)約束最優(yōu)解和無約束最優(yōu)解無論是在數(shù)學(xué)模型上還是幾何意義上均是不同的概念第2頁，共68頁，2023年，2月20日，星期三3等值線等值線族的中心無約束最優(yōu)解解：等值線的共同中心.數(shù)學(xué)模型:第3頁，共68頁，2023年，2月20日，星期三4數(shù)學(xué)模型:可行域約束最優(yōu)解

第4頁，共68頁，2023年，2月20日，星期三5無約束最優(yōu)點(diǎn)約束最優(yōu)點(diǎn)第5頁，共68頁，2023年，2月20日，星期三6約束優(yōu)化問題的類型

1.不等式約束優(yōu)化問題(IP型)2.等式約束優(yōu)化問題(EP型)3.一般約束優(yōu)化問題(GP型)第6頁，共68頁，2023年，2月20日，星期三7約束優(yōu)化方法分類約束優(yōu)化方法

約束坐標(biāo)輪換法直接法：約束隨機(jī)方向法

復(fù)合形法間接法：懲罰函數(shù)法

直接法：設(shè)法使每一次迭代產(chǎn)生的新迭代點(diǎn)限制在可行域內(nèi)，且一步一步的降低目標(biāo)函數(shù)值，直至最后獲得一個(gè)可行域內(nèi)的約束最優(yōu)解。間接法：將約束優(yōu)化問題通過一定形式的變換，轉(zhuǎn)化為無約束優(yōu)化問題，然后采用約束優(yōu)化方法進(jìn)行求解。第7頁，共68頁，2023年，2月20日，星期三85.3.1約束坐標(biāo)輪換法基本思想:與無約束坐標(biāo)輪換法類似,依此沿坐標(biāo)軸方向?qū)?yōu),逐步逼近最優(yōu)點(diǎn)。第8頁，共68頁，2023年，2月20日，星期三9任取一個(gè)初始點(diǎn)取初始步長α0沿e1方向檢查可行性:適用性:檢查......加速步長檢查可行性:適用性:第9頁，共68頁，2023年，2月20日，星期三10沿e2方向檢查可行性:適用性:檢查可行性:適用性:檢查可行性:適用性:檢查可行性:適用性:第10頁，共68頁，2023年，2月20日，星期三11沿e1方向檢查可行性:適用性:檢查可行性:適用性:沿e2方向檢查可行性:適用性:檢查......第11頁，共68頁，2023年，2月20日，星期三12沿坐標(biāo)軸方向找不到合適的點(diǎn):縮減初始步長

α0←0.5α0

繼續(xù)迭代終止準(zhǔn)則:

α0≤ε約束坐標(biāo)輪換法與無約束坐標(biāo)輪換法的區(qū)別：①步長

無約束:最優(yōu)步長

約束:加速步長②對(duì)每一個(gè)迭代點(diǎn)的檢查

無約束:檢查適用性

約束:檢查適用性和可行性③終止準(zhǔn)則

無約束:點(diǎn)距準(zhǔn)則

約束:步長準(zhǔn)則第12頁，共68頁，2023年，2月20日，星期三13特點(diǎn):約束坐標(biāo)輪換法具有算法明了、迭代簡單、便于設(shè)計(jì)者掌握運(yùn)用等優(yōu)點(diǎn)。但是，它的收斂速度較慢，對(duì)于維數(shù)較高的優(yōu)化問題(例如10維以上)很費(fèi)機(jī)時(shí)。另外，這種方法在某些情況下還會(huì)出現(xiàn)“死點(diǎn)”的病態(tài)，導(dǎo)致輸出偽最優(yōu)點(diǎn)。

避免輸出偽最優(yōu)點(diǎn)的辦法:1、輸入不同的初始點(diǎn)2、用不同的不長多次計(jì)算第13頁，共68頁，2023年，2月20日，星期三14基本原理：典型的“瞎子爬山”式的數(shù)值選代解法。在可行域內(nèi)，任選初始點(diǎn)x(0)，以給定的步長a=a0

，沿按某方法產(chǎn)生的隨機(jī)方向S(1)取探索點(diǎn)x=x(0)+aS(1），若該點(diǎn)同時(shí)符合下降性（F(x)<F(x(0)))和可行性（x∈D)則表示x點(diǎn)探索成功。并以它為新的起始點(diǎn)，繼續(xù)按上面的迭代公式在S(1）方向上獲取新的成功探索點(diǎn)……..

5.3.2約束隨機(jī)方向法第14頁，共68頁，2023年，2月20日，星期三155.3.2約束隨機(jī)方向法任取一個(gè)初始點(diǎn)取初始步長α0利用隨機(jī)函數(shù)構(gòu)成隨機(jī)方向S(1)

檢查可行性:適用性:檢查若m個(gè)方向都不行,則減小步長:α0←0.5α0終止準(zhǔn)則:

α0≤ε第15頁，共68頁，2023年，2月20日，星期三16說明當(dāng)在某個(gè)轉(zhuǎn)折點(diǎn)處沿m個(gè)(預(yù)先限定的次數(shù))隨機(jī)方向試探均失敗，則說明以此點(diǎn)為中心，α0為半徑的圓周上各點(diǎn)都不是適用、可行點(diǎn)。此時(shí)，可將初始步長α0縮半后繼續(xù)試探。直到α0≤ε，且沿m個(gè)隨機(jī)方向都試探失敗時(shí)，則最后一個(gè)成功點(diǎn)(如圖中的x(3))就是達(dá)到預(yù)定精度ε要求的約束最優(yōu)點(diǎn)，迭代即可結(jié)束。m是預(yù)先規(guī)定在某轉(zhuǎn)折點(diǎn)處產(chǎn)生隨機(jī)方向所允許的最大數(shù)目。一般可在50~500范圍內(nèi)選取。約束隨機(jī)方向法的搜索方向比坐標(biāo)輪換法要靈活得多。當(dāng)預(yù)定的隨機(jī)方向限定數(shù)m足夠大時(shí)，它不會(huì)像約束坐標(biāo)輪換法那樣出現(xiàn)“病態(tài)”而導(dǎo)致輸出偽最優(yōu)點(diǎn)。

第16頁，共68頁，2023年，2月20日，星期三17隨機(jī)搜索方向的產(chǎn)生在（a,b）之間的隨機(jī)數(shù)：yi=ai+

(bi–ai)

（-1,1）之間的隨機(jī)數(shù)：yi=2-1設(shè)是在區(qū)間(一l，1)上的兩個(gè)隨機(jī)數(shù)。將它們分別作為坐標(biāo)軸上的分量所構(gòu)成的向量即為相應(yīng)的二維隨機(jī)向量，其單位向量：同理，n維問題,隨機(jī)方向的單位向量：在算法語言所使用的函數(shù)庫中，有一種隨機(jī)函數(shù)RND(X)。利用這一隨機(jī)函數(shù)可在程序運(yùn)行過程中產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)。

(i＝l，2，…，n)第17頁，共68頁，2023年，2月20日，星期三18約束隨機(jī)方向搜索法的特點(diǎn)：對(duì)目標(biāo)函數(shù)的性態(tài)無特殊要求，程序設(shè)計(jì)簡單，使用方便。在維數(shù)較少的情況下是一種十分有效的方法，適用于小型問題。第18頁，共68頁，2023年，2月20日，星期三195.3.3復(fù)合形法基本思想：在可行域中選取K個(gè)點(diǎn)作為一復(fù)合形（多面體）的K個(gè)頂點(diǎn)。比較各點(diǎn)函數(shù)值的大小，去掉函數(shù)值最大所對(duì)應(yīng)的最壞點(diǎn)，而代之最壞點(diǎn)的映射點(diǎn)構(gòu)成新的復(fù)合形。不斷重復(fù)上述過程，使復(fù)合形不斷向最優(yōu)點(diǎn)移動(dòng)和收縮，直至滿足選代精度為止。

132X0X(R)n+l≤k≤2n第19頁，共68頁，2023年，2月20日，星期三20[引例]

設(shè)有一約束優(yōu)化問題的數(shù)學(xué)模型第20頁，共68頁，2023年，2月20日，星期三21一、復(fù)合形法的基本思想步驟：第一步：初始復(fù)合形的構(gòu)成

頂點(diǎn)X(1)、X(2)、X(3)第二步：對(duì)復(fù)合形進(jìn)行

調(diào)優(yōu)迭代計(jì)算頂點(diǎn)X(1)、X(2)、X(3)

F1>F2>F3

↓↓

X(H)

X(L)

壞點(diǎn)好點(diǎn)先求出除壞點(diǎn)外，其余各點(diǎn)構(gòu)成的圖形的形心點(diǎn)X0再求壞點(diǎn)X(H)相對(duì)于形心點(diǎn)X0的映射點(diǎn)

X(R)132X0X(R)第21頁，共68頁，2023年，2月20日，星期三22步驟：第一步：初始復(fù)合形的構(gòu)成

第二步：對(duì)復(fù)合形進(jìn)行調(diào)優(yōu)迭代計(jì)算

形心點(diǎn)X0映射點(diǎn)X(R)

α:反射系數(shù)，一般開始是取α=1.3132檢查可行性:適用性:新復(fù)合形4點(diǎn)的映射復(fù)合形的收縮第22頁，共68頁，2023年，2月20日，星期三23二、初始復(fù)合形的構(gòu)成

方法一:試湊法方法二:隨機(jī)產(chǎn)生(1)產(chǎn)生K個(gè)隨機(jī)點(diǎn)隨機(jī)數(shù)

(i＝l，2，…，n)(2)將非可行點(diǎn)調(diào)入可行域1234第23頁，共68頁，2023年，2月20日，星期三24終止條件:第24頁，共68頁，2023年，2月20日，星期三25例:用復(fù)合形法求解下例約束最優(yōu)化問題，迭代精度取

解：取復(fù)合形的頂點(diǎn)數(shù):(1)獲得初始復(fù)合形:本例采用人為給定四個(gè)點(diǎn)檢驗(yàn)各點(diǎn)是否可行：將各點(diǎn)的坐標(biāo)值代入以上三個(gè)約束方程，均滿足約束要求，這四個(gè)點(diǎn)為可行點(diǎn)，用作初始復(fù)合形的四個(gè)頂點(diǎn)第25頁，共68頁，2023年，2月20日，星期三26(2)迭代計(jì)算獲得新復(fù)合形計(jì)算復(fù)合形各頂點(diǎn)目標(biāo)函數(shù)值，

定出最壞點(diǎn)最好點(diǎn)計(jì)算除壞點(diǎn)外其余各頂點(diǎn)的中心

將代入諸約束條件均滿足，可知在可行城內(nèi)。

取，求壞點(diǎn)的映射點(diǎn)

在可行域內(nèi)

第26頁，共68頁，2023年，2月20日，星期三27計(jì)算并與比較：

用替換，亦即替換構(gòu)成新的復(fù)合形：

比較各點(diǎn)目標(biāo)函數(shù)值，定出最壞點(diǎn):最好點(diǎn):

（3）檢驗(yàn)迭代終止條件

第27頁，共68頁，2023年，2月20日，星期三28第28頁，共68頁，2023年，2月20日，星期三29復(fù)合形法的特點(diǎn):

對(duì)目標(biāo)函數(shù)及約束函數(shù)無特殊要求，適應(yīng)性強(qiáng)，計(jì)算量一般，收斂較快，適用中小型問題。是現(xiàn)有解不等式約束優(yōu)化問題的一種重要的直接法。第29頁，共68頁，2023年，2月20日，星期三305.3.5懲罰函數(shù)法將約束優(yōu)化問題通過一定形式的變換，轉(zhuǎn)化為無約束優(yōu)化問題，然后采用約束優(yōu)化方法進(jìn)行求解轉(zhuǎn)化必須滿足條件：1、不破壞原約束問題的約束條件，

2、最優(yōu)解必須歸結(jié)到原約束問題的最優(yōu)解上去。約束優(yōu)化問題的間接法有:消元法、拉格朗日乘子法、

懲罰函數(shù)法等.第30頁，共68頁，2023年，2月20日，星期三31minφ(x，r(k)，m(k)) (5.56)x∈Rn式中，φ(x，r(k)，m(k))為增廣函數(shù)，稱為懲罰函數(shù)，簡稱罰函數(shù)

將一般約束優(yōu)化問題數(shù)學(xué)模型minF(x)x∈Rn：gu(x)≥0，u＝l，2，…，phv(x)=0，v=1，2，…，q轉(zhuǎn)化成為一個(gè)如下的無約束優(yōu)化問題構(gòu)造的新目標(biāo)函數(shù)一般形式為懲罰函數(shù)法懲罰項(xiàng)第31頁，共68頁，2023年，2月20日，星期三32按照懲罰函數(shù)構(gòu)成的形式不同，懲罰函數(shù)法又分為三種：1、內(nèi)點(diǎn)懲罰函數(shù)法2、外點(diǎn)懲罰函數(shù)法3、混合懲罰函數(shù)法第32頁，共68頁，2023年，2月20日，星期三33一、內(nèi)點(diǎn)懲罰函數(shù)法基本思想：將新目標(biāo)函數(shù)定義于可行域內(nèi)，序列迭代點(diǎn)在可行域內(nèi)逐步逼近原目標(biāo)函數(shù)約束邊界上的最優(yōu)點(diǎn)。將約束優(yōu)化問題：

minF(x)x∈:gu(x)≥0(u=12……m)轉(zhuǎn)化為無約束優(yōu)化問題

其中：r(1)>r(2)>r(3)…>r(k)…>0是一個(gè)遞減的正值數(shù)列：

r(k)＝Cr(k-1)，

0＜C＜1

(k)=0

第33頁，共68頁，2023年，2月20日，星期三34內(nèi)點(diǎn)懲罰函數(shù)法的思路:當(dāng)X由可行域內(nèi)靠近任一約束邊界時(shí),懲罰項(xiàng)值趨于無窮大,所以它就像圍墻一樣阻止迭代點(diǎn)越出約束邊界.條件1：不破壞原約束問題的約束條件第34頁，共68頁，2023年，2月20日，星期三35minф(x,r(k))=min{F(x)+r(k)∑（1/gu(x)）}條件2：最優(yōu)解必須歸結(jié)到原約束問題的最優(yōu)解上去第35頁，共68頁，2023年，2月20日，星期三36解：若用內(nèi)點(diǎn)法求解此約束最優(yōu)化問題，由式知懲罰函數(shù)為將函數(shù)對(duì)求導(dǎo)，得:令:解得無約束極小值的點(diǎn)列為

:例:用內(nèi)點(diǎn)法求解

的約束最優(yōu)化問題。

無約束極小值點(diǎn)列相應(yīng)的懲罰函數(shù)值為

第36頁，共68頁，2023年，2月20日，星期三37第37頁，共68頁，2023年，2月20日，星期三38序列極小點(diǎn)都在可行域內(nèi)第38頁，共68頁，2023年，2月20日，星期三39初始點(diǎn)x(0)的確定

自定法:搜索法

先任取一個(gè)設(shè)計(jì)點(diǎn)x(k)；計(jì)算x(k)點(diǎn)的諸約束函數(shù)值gu(x(k))，u＝1，2，…，p若：構(gòu)造：按照該數(shù)學(xué)模型解出的最優(yōu)點(diǎn)x*，至少比原設(shè)計(jì)點(diǎn)x(k)多滿足一個(gè)約束條件

重復(fù)數(shù)次，直到所有的約束條件都得到滿足，最終可取得在可行域內(nèi)部的初始點(diǎn)x(0)。第39頁，共68頁，2023年，2月20日，星期三40

關(guān)于幾個(gè)參數(shù)的選擇(1)初始罰因子r(0)的選取一般可取初始罰因子r(0)＝1~50也有建議?。?2)遞減系數(shù)C的選擇

通常建議取C＝0.1~0.5第40頁，共68頁，2023年，2月20日，星期三41內(nèi)點(diǎn)懲罰函數(shù)法的特點(diǎn):在給定一個(gè)可行初始方案后，能求出一系列逐步得到改進(jìn)的可行的設(shè)計(jì)方案。但只適用于解不等式約束優(yōu)化問題，且初始點(diǎn)須在可行域內(nèi)。第41頁，共68頁，2023年，2月20日，星期三42=

已知約束優(yōu)化問題:試寫出內(nèi)點(diǎn)罰函數(shù),并選出初始迭代點(diǎn).內(nèi)點(diǎn)罰函數(shù):例：第42頁，共68頁，2023年，2月20日，星期三43例：桁架設(shè)計(jì)問題：minF(x)=1.57x1

x=[x1x2]T∈

第43頁，共68頁，2023年，2月20日，星期三44設(shè)有不等式約束優(yōu)化問題：構(gòu)造外點(diǎn)法懲罰函數(shù)的常見形式如下：懲罰因子r(k)規(guī)定取正。且在優(yōu)化過程中r(k)取為遞增數(shù)列

r(k)=Cr(k-1)，C＞1則將保證(k)=∞二、外點(diǎn)懲罰函數(shù)法基本思想：將新目標(biāo)函數(shù)定義于可行域外，序列迭代點(diǎn)在可行域外逐步逼近原目標(biāo)函數(shù)約束邊界上的最優(yōu)點(diǎn)。第44頁，共68頁，2023年，2月20日，星期三45式中:外點(diǎn)懲罰函數(shù)法的思路：可行域內(nèi)時(shí),新目標(biāo)函數(shù)就是原目標(biāo)函數(shù),當(dāng)X位于可行域外時(shí),懲罰項(xiàng)為正值,新目標(biāo)函數(shù)值增大,就構(gòu)成了對(duì)不滿足約束條件時(shí)的一種”懲罰”.且離可行域越遠(yuǎn),懲罰就越嚴(yán)厲.當(dāng)r(k）不夠大時(shí)，罰函數(shù)（新目標(biāo)函數(shù)）的極小值在可行域外，即懲罰不夠，可加大r(k），隨著r(k）的增大，使新目標(biāo)函數(shù)）的極小點(diǎn)越來越逼近原目標(biāo)函數(shù)極小點(diǎn)?？尚杏蛲饪尚杏騼?nèi)第45頁，共68頁，2023年，2月20日，星期三46對(duì)于解不等式約束優(yōu)化問題minF(x)＝xx∈R1

：g1(x)=x－1≥0用外點(diǎn)法構(gòu)造懲罰函數(shù)，具體構(gòu)造形式如下：寫成另一種形式例第46頁，共68頁，2023年，2月20日，星期三47令:解得無約束極小值的點(diǎn)列為

:無約束極小值點(diǎn)列相應(yīng)的懲罰函數(shù)值為

求懲罰函數(shù)極小點(diǎn):

第47頁，共68頁，2023年，2月20日，星期三48由此可見，當(dāng)懲罰因子為一遞增正值數(shù)列時(shí)，其極值點(diǎn)離約束最優(yōu)點(diǎn)愈來愈近，的差值與愈來愈小。當(dāng)時(shí)，，亦即逼近于真正的約束最優(yōu)解。無約束極值點(diǎn)列隨值遞增從可行域外向最優(yōu)點(diǎn)收斂。

第48頁，共68頁，2023年，2月20日，星期三49對(duì)幾個(gè)問題的討論初始點(diǎn)x(0)的選取:外點(diǎn)法的初始點(diǎn)x(0)可以任選，即在可行域與非可行域選取均可。(2)初始罰因子r(0)和遞增系數(shù)C的選取初始罰因子r(0)選得是否恰當(dāng)，對(duì)算法的成敗和計(jì)算速度仍有著顯著的影響。因此，選取時(shí)要謹(jǐn)慎。遞增系數(shù)C的取值，一般影響不太顯著，但也不宜取得過大。通常取C＝5~10。(3)約束容差帶用外點(diǎn)法求解時(shí)，由于罰函數(shù)的無約束最優(yōu)點(diǎn)列是從可行域外部向約束最優(yōu)點(diǎn)逼近的，所以最終取得的最優(yōu)點(diǎn)一定是在邊界的非可行域一側(cè)。嚴(yán)格地說，它是一個(gè)非可行點(diǎn)。這對(duì)某些工程問題可能是不允許的。為了解決這一問題。可在約束邊界的可行域一側(cè)加一條容差帶，如圖5.21。這就相當(dāng)于將約束條件改為gu(x)－δu≥0，u=1，2，…，p式中的δu是容差量，一般可取δu=10－3~10－4。

第49頁，共68頁，2023年，2月20日，星期三50約束容差帶。第50頁，共68頁，2023年，2月20日，星期三51外點(diǎn)法不但可以解不等式約束優(yōu)化問題，而且還可以解等式約束優(yōu)化問題

用外點(diǎn)法求解二維等式約束優(yōu)化問題：按外點(diǎn)法的基本思想，構(gòu)造懲罰函數(shù)第51頁，共68頁，2023年，2月20日，星期三52

外點(diǎn)法的特點(diǎn)外點(diǎn)法既可解不等式約束優(yōu)化問題，也能解等式約束優(yōu)化問題，且其初始點(diǎn)x(0)可任選，即在可行域中或非可行域中均可。其缺點(diǎn)是序列無約束最優(yōu)點(diǎn)是一系列的非可行點(diǎn)，對(duì)于工程設(shè)計(jì)一般是不可取的。為使最終的迭代點(diǎn)能落入可行域，必須設(shè)置約束容差帶。第52頁，共68頁，2023年，2月20日，星期三53例：已知約束優(yōu)化問題:試寫出外點(diǎn)罰函數(shù),并選出初始迭代點(diǎn).外點(diǎn)罰函數(shù):第53頁，共68頁，2023年，2月20日，星期三54三、混合法

用罰函數(shù)法解決有等式約束和不等式約束的一般約束（GP型）優(yōu)化問題的方法，把它稱為混合懲罰函數(shù)法，簡稱混合法。

一般約束優(yōu)化問題的數(shù)學(xué)模型

minf(x)x∈DD:gu(x)≥0(u=12……p)hv(x)=0(v=12……q,q<n)第54頁，共68頁，2023年，2月20日，星期三55內(nèi)點(diǎn)形式的混合型懲罰函數(shù)法r(k)---遞減m(k)---遞增初始點(diǎn)必須是嚴(yán)格的內(nèi)點(diǎn)為了統(tǒng)一用一個(gè)內(nèi)點(diǎn)法懲罰因子,上式也可寫成:不等式約束部分按內(nèi)點(diǎn)法形式處理r(k)---遞減第55頁，共68頁，2023年，2月20日，星期三56r(k)---遞增外點(diǎn)形式的混合型懲罰函數(shù)法不等式約束部分按外點(diǎn)法形式處理第56頁，共68頁，2023年，2月20日，星期三57如何判斷優(yōu)化結(jié)果的正確性:1、約束優(yōu)化問題，最優(yōu)點(diǎn)大多位于邊界上。2、輸入不同的初始點(diǎn)多次計(jì)算。3、用不同的方法解。作業(yè)：1、了解各種方法的基本思想和特點(diǎn)2、P130題237第57頁，共68頁，2023年，2月20日，星期三58機(jī)械優(yōu)化舉例：已知給定軌跡曲線，其上１２個(gè)主要點(diǎn)的坐標(biāo)見下表，并給定

（該機(jī)構(gòu)主要傳遞運(yùn)動(dòng)，對(duì)動(dòng)力特性要求不高）。試設(shè)計(jì)一曲柄搖桿機(jī)構(gòu)，使其連桿上點(diǎn)Ｍ的連桿曲線最佳逼近已知曲線.第58頁，共68頁，2023年，2月20日，星期三5912