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

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)線化,例：弱非線性問題的逐

2、次線化求解,,線化,,應(yīng)用線性規(guī)劃算法求解,例：弱非線性問題的逐次線化求解,,,…,11.1.2非線性約束問題,對于較強的非線性問題，逐次線化方法會導(dǎo)致發(fā)散，解決辦法：限制步長：區(qū)域越小線性近似越準確使用懲罰函數(shù),懲罰逐次線性規(guī)劃算法,例：懲罰逐次線性規(guī)劃方法,限制步長求解,,線化,,,,例：懲罰逐次線性規(guī)劃方法,x(1)點的懲罰函數(shù)計算,在x(1)點線化求解：,,,例：懲罰逐次線性規(guī)劃方法,在x(2)點線化求解：,,,,,,在x

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

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

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

6、的梯度：稱為約化梯度，是在非基本變量子空間中的梯度。,11.3.3既約(Reduced)梯度方法,基本量的變化：,非基本量子空間中的搜索方向：,保證x在定義域內(nèi)：,確定搜索方向,,11.3.3既約(Reduced)梯度方法,11.3.3既約(Reduced)梯度方法,約化梯度方法的加速共軛梯度準牛頓方法,11.3.4廣義既約梯度(GRG)方法,推廣約化梯度方法到一般的非線性優(yōu)化問題GRG基本思想：等式約束可以通過消元的辦法化

7、為無約束問題,將等式約束線化,消元,化為無約束形式,應(yīng)用無約束的基于梯度算法,,,,,11.3.4廣義既約梯度(GRG)方法,首先考慮等式約束問題，目標函數(shù)和約束都是非線性的：,基本GRG算法,1、約束的線化,,2、選擇獨立變量，即分解為基本量與非基本變量,基本量，即非獨立變量的系數(shù)矩陣：,非基本量，即獨立變量的系數(shù)矩陣：,基本GRG算法,3、以非基本變量為獨立變量，在線化的約束中解出基本量，實現(xiàn)消元,4、計算目標函數(shù)的梯度（獨立變量為

8、非基本變量為），即線性規(guī)劃中的相對收益,5、梯度為0即是最優(yōu)化的必要條件，可作為收斂準則,≤,,基本GRG算法,6、確定搜索方向,7、在搜索方向上線性搜索,,返回4,基本GRG算法修正,問題：搜索方向d具有下降的性質(zhì)，這是由于 是下降的，而,一般不具有這個性質(zhì)，因此會導(dǎo)致在d方向上搜索會違反約束,解決辦法：將 往約束曲面上投影，在投影上進行線性搜索：,具體方法：,（1）給定α，解出,（2）調(diào)變α，使f(x)最速下降,完整GR