約束問題的線性化方法

《約束問題的線性化方法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、11約束問題的線性化方法非線性約束問題求解策略轉(zhuǎn)化為無約束問題Lagrange乘子法懲罰函數(shù)法線性化直接搜索等其它方法線化方法：Taylor展開11.1線性逐次逼近算法線性約束問題非線性約束問題11.1.1線性約束問題在初始點x0線化線性約束問題算法例：三級壓縮機優(yōu)化設(shè)計目標：選擇中間級大力，最大限度節(jié)能例：三級壓縮機優(yōu)化設(shè)計11.1.2非線性約束問題在點x(t)線化例：弱非線性問題的逐次線化求解線化應(yīng)用線性規(guī)劃算法求解例：弱非線性問題的逐次線化求解…11.1.2非線性約束問題對于較強的非線性問題，逐次線化方法會導(dǎo)致發(fā)散，解決辦法：限制步長：區(qū)域越小線性近似越準確

2、使用懲罰函數(shù)懲罰逐次線性規(guī)劃算法例：懲罰逐次線性規(guī)劃方法限制步長求解線化例：懲罰逐次線性規(guī)劃方法x(1)點的懲罰函數(shù)計算在x(1)點線化求解：例：懲罰逐次線性規(guī)劃方法在x(2)點線化求解：在x(3)點線化求解：…11.2可分離規(guī)劃：分段線性近似分段線性逼近單變量分段線性近似多變量可分離規(guī)劃前提：函數(shù)可分離多變量可分離規(guī)劃例：多變量函數(shù)線性近似例：可分離規(guī)劃求解例：可分離規(guī)劃求解x1的網(wǎng)格點選?。汉瘮?shù)的分段線性近似：例：可分離規(guī)劃求解線化之后的線性規(guī)劃標準形式：單純形方法求解：精確解總結(jié)逐次線性逼近算法步長限制，懲罰函數(shù)適用于非線性不強的問題分段線性逼近算法精度隨格

3、點數(shù)增加而增加要求函數(shù)可分離11.3搜索方向的線性化生成11.3.1可行方向算法可行方向算法例：可行方向算法例：可行方向算法例：可行方向算法…可行方向算法修正ε微擾法Topkis–Veinott方法11.3.2單純形方法推廣單純形方法回顧約束標準型：基本解：相對收益：基本變量的選取與替換：新的可行基本解：最優(yōu)化準則：所有非基本變量的相對收益大于或等于0單純形方法推廣到線性約束問題：凸單純形方法相對收益：最優(yōu)化準則：最優(yōu)解可能不在頂點，非基本變量可能不為0約束標準型：基本解：相對收益：最優(yōu)化準則：線性搜索凸單純形算法凸單純形算法11.3.3既約(Reduced)梯度

4、方法類似于無約束優(yōu)化的梯度算法（Cauchy算法）。搜索方向d為梯度的負方向約化梯度為，即凸單純形算法中非基本量的相對收益?？梢宰C明，它實際上是在約束條件(m個)下的以非基本變量為獨立變量(n-m)的梯度：稱為約化梯度，是在非基本變量子空間中的梯度。11.3.3既約(Reduced)梯度方法基本量的變化：非基本量子空間中的搜索方向：保證x在定義域內(nèi)：確定搜索方向11.3.3既約(Reduced)梯度方法11.3.3既約(Reduced)梯度方法約化梯度方法的加速共軛梯度準牛頓方法11.3.4廣義既約梯度(GRG)方法推廣約化梯度方法到一般的非線性優(yōu)化問題GRG基本

5、思想：等式約束可以通過消元的辦法化為無約束問題將等式約束線化消元化為無約束形式應(yīng)用無約束的基于梯度算法11.3.4廣義既約梯度(GRG)方法首先考慮等式約束問題，目標函數(shù)和約束都是非線性的：基本GRG算法1、約束的線化2、選擇獨立變量，即分解為基本量與非基本變量基本量，即非獨立變量的系數(shù)矩陣：非基本量，即獨立變量的系數(shù)矩陣：基本GRG算法3、以非基本變量為獨立變量，在線化的約束中解出基本量，實現(xiàn)消元4、計算目標函數(shù)的梯度（獨立變量為非基本變量為），即線性規(guī)劃中的相對收益5、梯度為0即是最優(yōu)化的必要條件，可作為收斂準則≤基本GRG算法6、確定搜索方向7、在搜索方向上

6、線性搜索返回4基本GRG算法修正問題：搜索方向d具有下降的性質(zhì)，這是由于是下降的，而一般不具有這個性質(zhì)，因此會導(dǎo)致在d方向上搜索會違反約束解決辦法：將往約束曲面上投影，在投影上進行線性搜索：具體方法：（1）給定α，解出（2）調(diào)變α，使f(x)最速下降完整GRG算法完整GRG算法11.3.5最一般情形的GRG算法包含不等式約束，定義域有上下界定義域邊界處理：兩種方法將其作為不等式約束在基本GRG算法過程中對邊界特殊處理不等式約束的處理：兩種方法加入松弛變量，化為等式約束在基本GRG算法過程中對邊界特殊處理