《第11章約束問題的線性化方法》由會(huì)員分享，可在線閱讀，更多相關(guān)《第11章約束問題的線性化方法（49頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,11,約束問題的線性化方法,非線性約束問題求解策略,轉(zhuǎn)化為無約束問題,Lagrange,乘子法,懲罰函數(shù)法,線性化,直接搜索等其它方法,線化方法：,Taylor,展開,11.1,線性逐次逼近算法,線性約束問題,非線性約束問題,11.1.1,線性約束問題,在初始點(diǎn),x0,線化,線性約束問題算法,例：三級(jí)壓縮機(jī)優(yōu)化設(shè)計(jì),目標(biāo)：選擇中間級(jí)大力，最大限度節(jié)能,例：三級(jí)壓縮機(jī)優(yōu)化設(shè)計(jì),11.1.2,非線性約束問題,在點(diǎn),x,(t),線化,例：弱非線性問題的逐次線化求解,線化,應(yīng)用線性規(guī)劃算法求解,例：弱非線性問題的

2、逐次線化求解,11.1.2,非線性約束問題,對(duì)于較強(qiáng)的非線性問題，逐次線化方法會(huì)導(dǎo)致發(fā)散，解決辦法：,限制步長(zhǎng)：區(qū)域越小線性近似越準(zhǔn)確,使用懲罰函數(shù),懲罰逐次線性規(guī)劃算法,例：懲罰逐次線性規(guī)劃方法,限制步長(zhǎng)求解,線化,例：懲罰逐次線性規(guī)劃方法,x,(1),點(diǎn)的懲罰函數(shù)計(jì)算,在,x,(1),點(diǎn)線化求解：,例：懲罰逐次線性規(guī)劃方法,在,x,(2),點(diǎn)線化求解：,在,x,(3),點(diǎn)線化求解：,11.2,可分離規(guī)劃：分段線性近似,分段線性逼近,單變量分段線性近似,多變量可分離規(guī)劃,前提：函數(shù)可分離,多變量可分離規(guī)劃,例：多變量函數(shù)線性近似,例：可分離規(guī)劃求解,例：可分離規(guī)劃求解,x1,的網(wǎng)格點(diǎn)選?。?

3、函數(shù)的分段線性近似：,例：可分離規(guī)劃求解,線化之后的線性規(guī)劃標(biāo)準(zhǔn)形式：,單純形方法求解：,精確解,總結(jié),逐次線性逼近算法,步長(zhǎng)限制，懲罰函數(shù),適用于非線性不強(qiáng)的問題,分段線性逼近算法,精度隨格點(diǎn)數(shù)增加而增加,要求函數(shù)可分離,11.3,搜索方向的線性化生成,11.3.1,可行方向算法,可行方向算法,例：可行方向算法,例：可行方向算法,例：可行方向算法,可行方向算法修正,微擾法,TopkisVeinott,方法,11.3.2,單純形方法推廣,單純形方法回顧,約束標(biāo)準(zhǔn)型：,基本解：,相對(duì)收益：,基本變量的,選取與替換：,新的可行基本解：,最優(yōu)化準(zhǔn)則：,所有非基本變量的相對(duì)收益大于或等于,0,單純形方

4、法推廣到線性約束問題：,凸單純形方法,相對(duì)收益：,最優(yōu)化準(zhǔn)則：,最優(yōu)解可能不在頂點(diǎn)，非基本變量可能不為,0,約束標(biāo)準(zhǔn)型：,基本解：,相對(duì)收益：,最優(yōu)化準(zhǔn)則：,線性搜索,凸單純形算法,凸單純形算法,11.3.3,既約,(Reduced),梯度方法,類似于無約束優(yōu)化的梯度算法（,Cauchy,算法）。搜索方向,d,為梯度的負(fù)方向,約化梯度為 ，即凸單純形算法中非基本量的相對(duì)收益?？梢宰C明，它實(shí)際上是在約束條件,(m,個(gè),),下的以非基本變量為獨(dú)立變量,(n-m),的梯度：,稱為約化梯度，是在非基本變量子空間中的梯度。,11.3.3,既約,(Reduced),梯度方法,基本量的變化：,非基本量子空間

5、,中的搜索方向：,保證,x,在定義域內(nèi)：,確定搜索方向,11.3.3,既約,(Reduced),梯度方法,11.3.3,既約,(Reduced),梯度方法,約化梯度方法的加速,共軛梯度,準(zhǔn)牛頓方法,11.3.4,廣義既約梯度,(GRG),方法,推廣約化梯度方法到一般的非線性優(yōu)化問題,GRG,基本思想：等式約束可以通過消元的辦法化為無約束問題,將等式約束線化,消元,化為無約束形式,應(yīng)用無約束的基于梯度算法,11.3.4,廣義既約梯度,(GRG),方法,首先考慮等式約束問題，目標(biāo)函數(shù)和約束都是非線性的：,基本,GRG,算法,1、,約束的線化,2、,選擇獨(dú)立變量，即分解為基本量與非基本變量,基本量，

6、即非獨(dú)立變量的系數(shù)矩陣：,非基本量，即,獨(dú)立變量,的系數(shù)矩陣：,基本,GRG,算法,3、,以非基本變量為獨(dú)立變量，在線化的約束中解出基本量，實(shí)現(xiàn)消元,4、,計(jì)算目標(biāo)函數(shù)的梯度（獨(dú)立變量為非基本變量為），即線性規(guī)劃中的相對(duì)收益,5、,梯度為,0,即是最優(yōu)化的必要條件，可作為收斂準(zhǔn)則,基本,GRG,算法,6、,確定搜索方向,7、,在搜索方向上線性搜索,返回,4,基本,GRG,算法修正,問題,：搜索方向,d,具有下降的性質(zhì)，這是由于 是下降的，而,一般不具有這個(gè)性質(zhì)，因此會(huì)導(dǎo)致在,d,方向上搜索會(huì)違反約束,解決辦法,：將 往約束曲面上投影，在投影上進(jìn)行線性搜索：,具體方法：,（,1）,給定,，解出,（,2）,調(diào)變,，使,f(x),最速下降,完整,GRG,算法,完整,GRG,算法,11.3.5,最一般情形的,GRG,算法,包含不等式約束，定義域有上下界,定義域邊界處理：兩種方法,將其作為不等式約束,在基本,GRG,算法過程中對(duì)邊界特殊處理,不等式約束的處理：兩種方法,加入松弛變量，化為等式約束,在基本,GRG,算法過程中對(duì)邊界特殊處理,