《第11章約束問題的線性化方法》由會員分享，可在線閱讀，更多相關《第11章約束問題的線性化方法（49頁珍藏版）》請在裝配圖網上搜索。

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

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

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

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

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

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