第11章約束問題的線性化方法ppt課件

1、11 約束問題的線性化方法非線性約束問題求解戰(zhàn)略n 轉(zhuǎn)化為無約束問題n Lagrange乘子法n 懲罰函數(shù)法n 線性化n 直接搜索等其它方法線化方法：Taylor展開11.1線性逐次逼近算法n線性約束問題n非線性約束問題11.1.1線性約束問題在初始點x0線化線性約束問題算法例：三級緊縮機優(yōu)化設計n目的：選擇中間級大力，最大限制節(jié)能例：三級緊縮機優(yōu)化設計11.1.2非線性約束問題在點x(t)線化例：弱非線性問題的逐次線化求解線化線化運用線性規(guī)劃算法求解運用線性規(guī)劃算法求解例：弱非線性問題的逐次線化求解11.1.2非線性約束問題n對于較強的非線性問題，逐次線化方法會導致發(fā)散，處理方法：n限制步長

2、：區(qū)域越小線性近似越準確n運用懲罰函數(shù)懲罰逐次線性規(guī)劃算法例：懲罰逐次線性規(guī)劃方法限制步長求解限制步長求解線化例：懲罰逐次線性規(guī)劃方法x(1)點的懲罰函數(shù)計算點的懲罰函數(shù)計算在在x(1)點線化求解：點線化求解：例：懲罰逐次線性規(guī)劃方法在在x(2)點線化求解：點線化求解：在在x(3)點線化求解：點線化求解：11.2可分別規(guī)劃：分段線性近似n分段線性逼近單變量分段線性近似多變量可分別規(guī)劃n前提：函數(shù)可分別多變量可分別規(guī)劃例：多變量函數(shù)線性近似( )22f x=%L例：可分別規(guī)劃求解例：可分別規(guī)劃求解x1的網(wǎng)格點選?。旱木W(wǎng)格點選?。汉瘮?shù)的分段線性近似：函數(shù)的分段線性近似：例：可分別規(guī)劃求解線化之后的

3、線性規(guī)劃規(guī)范方式：線化之后的線性規(guī)劃規(guī)范方式：單純形方法求解：單純形方法求解：準確解總結(jié)n逐次線性逼近算法n步長限制，懲罰函數(shù)n適用于非線性不強的問題n分段線性逼近算法n精度隨格點數(shù)添加而添加n要求函數(shù)可分別11.3搜索方向的線性化生成11.3.1可行方向算法可行方向算法例：可行方向算法例：可行方向算法例：可行方向算法可行方向算法修正n微擾法nTopkisVeinott方法11.3.2單純形方法推行單純形方法回想單純形方法回想約束規(guī)范型：根本解：相對收益：根本變量的選取與交換：新的可行根本解：最優(yōu)化準那么： 一切非根本變量的相對收益大于或等于0單純形方法推行到線性約束問題：凸單純形方法相對收益

4、：最優(yōu)化準那么：最優(yōu)解能夠不在頂點，非根本變量能夠不為0( )0m i ni m i zef xx約束規(guī)范型：根本解：相對收益：( )0f xc勛最優(yōu)化準那么： 0c%線性搜索凸單純形算法凸單純形算法11.3.3既約(Reduced)梯度方法n類似于無約束優(yōu)化的梯度算法Cauchy算法。搜索方向d 為梯度的負方向n約化梯度為 ，即凸單純形算法中非根本量的相對收益。可以證明，它實踐上是在約束條件(m個)下的以非根本變量為獨立變量(n-m)的梯度：n稱為約化梯度，是在非根本變量子空間中的梯度。ffx=%11.3.3既約(Reduced)梯度方法根本量的變化：根本量的變化：非根本量子空間非根本量子空

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

6、解為根本量與非根本變量根本量，即非獨立變量的系數(shù)矩陣：非根本量，即獨立變量的系數(shù)矩陣：根本GRG算法3、以非根本變量為獨立變量，在線化的約束中解出根本量，實現(xiàn)消元、以非根本變量為獨立變量，在線化的約束中解出根本量，實現(xiàn)消元4、計算目的函數(shù)的梯度獨立變量為非根本變量為，即線性規(guī)劃中的相對收益、計算目的函數(shù)的梯度獨立變量為非根本變量為，即線性規(guī)劃中的相對收益5、梯度為、梯度為0即是最優(yōu)化的必要條件，可作為收斂準那么即是最優(yōu)化的必要條件，可作為收斂準那么根本GRG算法6、確定搜索方向、確定搜索方向7、在搜索方向上線性搜索、在搜索方向上線性搜索前往前往4根本GRG算法修正問題：搜索方向問題：搜索方向d具有下降的性質(zhì)，這是由于具有下降的性質(zhì)，這是由于 是下降的，而是下降的，而普通不具有這個性質(zhì)，因此會導致在d方向上搜索會違反約束處理方法：將處理方法：將 往約束曲面上投影，在投影上進展線性搜索：往約束曲面上投影，在投影上進展線性搜索：詳細方法：詳細方法：1給定，解出2調(diào)變，使f(x)最速下降完好GRG算法完好GRG算法11.3.5 最普通情形的GRG算法n