2022/12/181第五章約束優(yōu)化方法一.約束坐標輪換法二.約束隨機方向法三.復合形法四.可行方向法五.罰函數(shù)法六.拉格朗日乘子法七.簡約梯度法及廣義簡約梯度法2022/12/182§5-1優(yōu)化方法的類型2）間接法1）直接法---將迭代點限制在可行域內(可行性),步步降低目標函數(shù)值(下降性),直至到達最優(yōu)點.

常用方法有:約束坐標輪換法,約束隨機方向法,復合形法,可行方向法,線性逼近法等.---通過變換,將約束優(yōu)化問題轉化為無約束優(yōu)化問題求解.

常用方法有:罰函數(shù)法,拉格朗日乘子法等.（可解IP型問題）（可解各類問題）(按對約束條件的處理方法分)2022/12/183§5-2約束坐標輪換法一.基本思路①可取定步長、加速步長和收縮步長,但不能取最優(yōu)步長;1.依次沿各坐標軸方向---e1,e2,…,en方向搜索;2.將迭代點限制在可行域內.②對每一迭代點均需進行可行性和下降性檢查.2022/12/184二.迭代步驟2022/12/185三.存在問題有時會出現(xiàn)死點,導致輸出“偽最優(yōu)點”.*為辨別真?zhèn)?要用K-T條件進行檢查.2022/12/186§5-3約束隨機方向法基本思路②若該方向適用、可行，則以定步長前進；坐標輪換法有時會輸出“偽最優(yōu)點”

,用隨機方向法可克服這一缺點.①

若該方向不適用、可行，則產生另一方向；③若在某處產生的方向足夠多，仍無一適用、可行，則采用收縮步長；④若步長小于預先給定的誤差限則終止迭代。搜索方向----采用隨機產生的方向2022/12/187二.隨機方向的構成1.用RND(X)產生n個隨機數(shù)2.將(0,1)中的隨機數(shù)

變換到(-1,1)中去;3.構成隨機方向變換得:于是例:對于三維問題:2022/12/188X0=X,F0=Fα=α0,F0=F(X0)F=F（X）j=1K=K+1三.隨機方向法的迭代步驟是K=0,j=0產生隨機方向α=0.5α否F<F0j=0K<mα≤ε結束X*=X0,F*=F0是否是否是否X∈D是否2022/12/189§5-4復合形法基本思路

在可行域內選取若干初始點并以之為頂點構成一個多面體(復合形),然后比較各頂點的函數(shù)值,去掉最壞點,代之以好的新點,并構成新的復合形,以逼近最優(yōu)點.有兩種基本運算:1)映射---在壞點的對側試探新點:先計算除最壞點外各頂點的幾何中心,然后再作映射計算.2)收縮---保證映射點的“可行”與“下降”X1為最壞點---映射系數(shù)常取

若發(fā)現(xiàn)映射點不適用、可行,則將減半后重新映射.2022/12/1810二.初始復合形的構成1.復合形頂點數(shù)K的選擇建議:

小取大值,大取小值2)為避免降維,K應取大些;但過大,計算量也大.*1)為保證迭代點能逼近極小點,應使2022/12/7112.初始復復合形形頂點點的確確定1)用試湊湊方法法產生生---適于低低維情情況;2)用隨機機方法法產生生①用隨機機方法法產生生K個頂點點

先用隨機函數(shù)產生

個隨機數(shù)

,然后變換到預定的區(qū)間

中去.這便得得到了了一個個頂點點,要連續(xù)續(xù)產生生K個頂點點.2022/12/712②將非可可行點點調入入可行行域內內ⅰ)檢查已已獲得得的各各頂點點的可可行性性,若無一一可行行,則重新新產生生隨機機點;若有q個可行行,則轉下下步.ⅱ)計算q個可行行點點點集的的幾何何中心心ⅲ)將非可可行點點逐一一調入入可行行域內內.若仍不不可行行,則重復復此步步驟,直至進進入可可行域域為止止.2022/12/713三.終止判判別條條件各頂點點與好好點函函數(shù)值值之差差的均均方根根應不不大于于誤差差限

不是十分可靠,可改變重作,看結果是否相同.2022/12/714比較復合形各頂點的函數(shù)值，找出好點XL，壞點XHXH=XRα=0.5α找出次壞點XSH

，XH=XSH滿足終止條件？X*=XL,F*=F(XL)結束四.復合形形法的的迭代步步驟是否給定K，δ，α，ε，ai,bi

i=1,2,…n產生初始復合形頂點Xj,j=1,2,…,K計算復合形各頂點的函數(shù)值F(Xj),j=1,2,…,K是是是否否否XR∈DFR<F(XH)2022/12/715§5-5可行方方向法法*其特點點是注注意到到約束束最優(yōu)優(yōu)點通通常在在約束束邊界界上：：為此此，可可先找找出一一個邊邊界點點，然然后沿沿邊界界搜索索;---是求解解大型型約束束優(yōu)化化問題題的主主要方方法.一.尋找邊邊界點點的方方法1.在D內取一一初始始點,然后沿沿負梯梯度方方向搜搜索,直至使使迭代代點超超越D或落在在邊界界上;2.若迭代點點在D外,則將它它調回回到邊界上上.2022/12/716二.產生適適用可可行方方向的的辦法法(一)適用可可行方方向的的數(shù)學學條件件1.適用(下降)性條件件在迭代代點處處,目標函函數(shù)沿沿該方方向的的方向向導數(shù)數(shù)應小小于0:與負梯度方向的夾角應小于900.2022/12/7172.可行性性條件件在邊界界迭代代點處處,實時約約束函數(shù)沿沿該方方向的的方向向導數(shù)數(shù)應不不小于于0:與實時約束函數(shù)梯度方向的夾角應不大于900.(1)可行方方向迭代公式:只要取適當?shù)?/p>

,能使

仍在D內,則

稱可行方向.(2)可行性性條件件2022/12/718*若迭代點

處于J個約束邊界的相交處,應同時成立:綜上所所述,適用可可行方方向的的數(shù)學學條件件為:幾何解解釋:2022/12/719(二)最有利利的適適用可可行方方向在滿足足上述述適用用可行行方向向的數(shù)數(shù)學條條件的的同時時，使使目標標函數(shù)數(shù)的方方向導導數(shù)為為負且且達到到最小?。ㄌ幚頌榫€線性規(guī)劃劃問題）：D:使求*1)---條件余度(>0,一般取為0.01—0.001);

2)---方向偏離系數(shù)(>=0,對線性約束取為0,其余取為1).--規(guī)格化條條件2022/12/720三.步長因子子的確定定1.最優(yōu)步長長因子(迭代點為為內點時時使用)下一迭代代點如仍仍為內點點,繼續(xù)進行行,直至迭代代點到邊邊界或域域外時止止.迭代公式式:2.試驗步長因子將

在

處作泰勒展開,僅取到線性項:(1)

定義目標函數(shù)相對下降量:(2)迭代公式

(3)(4)將(2)、(3)代入(1)后整理得:

迭代點在邊界附近偏域內一側時使用,采用最有利的適用可行方向.2)按此法,直至使迭迭代點進進入約束束容差帶帶或至域域外為止止.*1)為保證

是

的一個鄰近點,的值不能取得太大.通常2022/12/7212.調整步長長因子(將已出界界的迭代代點調回回到邊界界上)(1)約束邊界界容差帶帶

在實際計算中,應給約束邊界一個允許的誤差限:式中,通常取0.01-0.001;只要迭代點進入容差帶,即認為達到了邊界.(2)調整步長因子因

與

很接近,可認為

在這兩點間按線性變化:(1)為使新迭代點落在容差帶中部,取(2)于是有(3)*還需檢驗驗該點是是否在容容差帶內內.若不滿足足,則ⅰ)若

,則ⅱ)若

,則重復以上上步驟,直至滿足足時止.2022/12/722滿足K-T條件？

給定：內點X（0），β，θ，δ，ΔfK=0，M=0

沿負梯度方向一維搜索得極小點X（K+1）求最有利的適用可行方向求試驗步長因子αtM=0K=K+1X*=X(K),F*=F(X*)結束是是是否否否求求調整步長因子否四.終止迭代代準則采用K-T條件,對J個起作用用約束,求解線性性方程組組:M=1應為非負五.迭代步驟驟是2022/12/723§5-6懲罰函數(shù)數(shù)法一.概述1.基本思想想將約束問題

轉化成無約束問題

求解懲罰函數(shù)可調參數(shù)*構造懲罰函數(shù)

的基本要求:①懲罰項用用約束條條件構造造;②到達最優(yōu)優(yōu)點時,懲罰項的的值為0;③當約束不不滿足或或未到達達最優(yōu)點點時,懲罰項的值大于0.2.分類①內點法----將迭代點點限制在在可行域域內;②外點法----迭代點一一般在可可行域外外;③混合合法法----將外外點點法法和和內內點點法法結結合合起起來來解解GP型問問題題.2022/12/724二.SUMT內點點法法1.懲罰罰函函數(shù)數(shù)的的構構造造原問題:s.t.可取式中,1)*當X趨于于D的邊邊界界時時,B(X)趨于于無無窮窮大大,故又又稱稱為為障礙礙(圍墻墻)函數(shù)數(shù);2022/12/7252)

罰因子為使

與原問題同解,應使*對于一個

,求解一個無約束優(yōu)化問題.前一問題的結果為后一問題的初值,故為系列無約束極小化方法(SequentialUnconstrainedMinimizationTechnique).2022/12/726

輸出X*，F(xiàn)*=F（X*）結束是2.SUMT內點罰函數(shù)數(shù)法迭代步步驟用無約束方法求

的極小點X*輸入X0，r0,c,ε否k=k+1,Xk=X*，rk=crkK=0,Xk=X0,2022/12/727例:解:懲罰函數(shù)在D內

,對于固定的

,令得r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.94721/501.20.650.7…1/62501.01790.508955.90170.5179…010.50.52022/12/728r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.94721/501.20.650.7…1/62501.01790.508955.90170.5179…010.50.52022/12/7291)初始點X0的確定(必須為內點點)*用現(xiàn)有機器器參數(shù)作初初值;*用圖解法;*用隨機方法法;*用內點法求求內點.3.應用內點法法應注意的的問題---X0,r(0),c的確定2022/12/730k=0,X(k)=X0,r(k)=r0I2為空集計算指標集以X(K)為初始點,求解得X*。輸出是否任取X0,給定

r0,c,

2022/12/7312）罰因子的初初值*過大,會使

的最優(yōu)點比X0

離真正的最優(yōu)點更遠;過小,在域內的懲罰作用小,在接近邊界時則突然加大使性態(tài)變壞,且有可能使迭代點越出可行域.

Fox推薦3）遞減系數(shù)C本書推薦0.1—0.5.2022/12/732三.SUMT外點法1.懲罰函數(shù)的的構造考慮非線性性規(guī)劃問題題:s.t.懲罰函數(shù)可可取為2)罰因子*1)時,懲罰項為0,不懲罰;時,懲罰項大于0,有懲罰作用.因

邊界時,懲罰項中大括號中的值趨于0,為保證懲罰作用,應取2022/12/7332.SUMT外點點法法的的迭迭代代步步驟驟給定X0，c,r0,ε1,ε2,ε3k=0,r(k)=r0,X(K)=X0輸出X*，F(xiàn)*=F（X*）結束是是是否否否求解

得極小點X*k=k+1r(k)=cr(k)X(k)=X*---初始點,對凸規(guī)劃可任意給定;*---外點法點距精度;---等式約束允許的誤差限;---不等式約束允許的誤差限;---罰因子的放大系數(shù);**為使使迭迭代代點點進進入入可可行行域域,可設設約束束容容差差帶帶:2022/12/734例:解:懲罰罰函函數(shù)數(shù)在D外

,對于固定的

,令得r(k)x*f(x*)11.50.250.5101.909090.826540.909091001.990990.9802960.99009910001.9990010.9980030.999001…2112022/12/7353.外點點法法與與內內點點法法的的比比較較1)外點點法法可可解解各各類類問問題題,內點點法法僅僅適適于于IP型問問題題;2)外點點法法的的初初始始點點可可任任選選,內點點法法的的初初始始點點必必須須為為內內點點;3)外點點法法的的極極小小點點系系列列一一般般在在D外,內點點法法的的極極小小點點系系列列在D內(全為為可可行行點點);2022/12/736四.SUMT混合合法法有等式約約束時內內點法不不能用,要求迭代代點始終終滿足不不等式約約束時外外點法不不能用.此時可將將外點法法和內點點法結合合起來解解GP型問題.*1)迭代點應應始終滿滿足2)Fiacco等人建議議2022/12/737§5-7拉格朗日日乘子法法一.等式約束束問題的的拉格朗朗日乘子子法s.t.1.建立拉氏氏函數(shù)2.在最優(yōu)點點處有如如下n+q個方程成成立其解為2022/12/738s.t.二.含不等式約約束問題的的拉格朗日日乘子法1.建立拉氏函函數(shù)再用前述方方法建立拉拉氏函數(shù)

對不等式約束引入松弛變量

,使之成為等式約束:2022/12/7392.在最優(yōu)點處處有如下n+q+2p個方程成立立其解為2022/12/740三.增廣拉格朗朗日乘子法法采用拉格朗朗日乘子法法時求解有有難度,而罰函數(shù)法法當?shù)c點接近邊界界時函數(shù)常常有病態(tài),此法的思路路是把兩者者結合起來來.其增廣拉格格朗日函數(shù)數(shù)為:特點:1.初始點可為為非可行點點;2.因增加了可調參數(shù)

,其收斂速度和穩(wěn)定性都優(yōu)于罰函數(shù)法.2022/12/741§5-8簡約梯梯度法法及廣廣義簡簡約梯梯度法法思路：：利用用約束束條件件消去去非獨獨立變變量，，使問問題簡簡化，，再沿沿簡化化后的的目標標函數(shù)數(shù)的負負梯度度方向向搜索索.一簡簡約梯梯度法法1.問題題

s.t.2.簡約約梯梯度度1）將問問題題降降維維基向向量量（（狀狀態(tài)態(tài)））式中將X分成兩部分：2022/12/742非基向量（決策)對應的系數(shù)矩陣也分成兩部分式中，B為對應于XB的m階方陣，且必須為滿秩矩陣；C為對應于XN的

階矩陣；于是，（1）故2022/12/7432）求求簡簡約約梯梯度度（2）式中中,3.迭代代計計算算1）迭迭代代公公式式（3）2022/12/744*(1)在迭迭代代中中需需保保證證各各分分量量值值大大于于或或等等于于零零