化工系統(tǒng)工程_03非線性規(guī)劃

1、nonlinear programming, NLP非線性規(guī)劃一般包括無約束極值問題：沒有任何約束條件約束極值問題：在等式或不等式約束下求最大或最小。非線性規(guī)劃解理論現(xiàn)狀：解析理論：非線性規(guī)劃問題的解理論本身在所有應用數學進行分析的學科中都是非常重要的基礎，例如經濟學中的消費者理論、廠商理論都是在非線性規(guī)劃解理論基礎上發(fā)展起來的。數值求解：實際求解時，往往只能得到近似解；不能保證是全局最優(yōu)；常常出現(xiàn)不收斂的情況。因此只要可能，實際建模時盡可能建為線性模型。幾類基本優(yōu)化問題及其困難性幾類基本優(yōu)化問題及其困難性)(minxfSx其中其中一般形式一般形式nRS mRxf)(可行域可行域目標函數目標函

2、數有無約束有無約束, 連續(xù)連續(xù), 離散離散, 凸凸, 非凸非凸, 確定確定, 隨機隨機單目標單目標, 多目標多目標, 連續(xù)連續(xù), 可導可導, 凸凸, 非凸非凸求解多元函數的無約束極小點問題目前被人們所廣泛接受的一種方法就是下降迭代算法，也稱為搜索法。搜索法發(fā)展的理由在于：在許多實際問題中，目標函數不滿足凸性，于是促使人們考慮直接從函數的特性出發(fā)，對局部最優(yōu)解進行搜索。只利用目標函數值的變化進行試探性搜索稱為直接搜索法；根據目標函數的解析性質確定搜索的方法稱為解析搜索法。 )(minxfnRx無約束無約束, 單目標單目標, 連續(xù)變量連續(xù)變量基本方法基本方法尋找下降方向尋找下降方向, 局部搜索前進

3、局部搜索前進一階可導函數理論解：Max（min）f(x)必要條件：一階條件：導數（偏導數）0。也就是或者說，梯度0：性質：只是必要條件，滿足一階條件并不一定是極值點。極大點和極小點都滿足同樣條件。需考察二階條件才能知道是否為極值點以及是極大點還是極小點。不能保證是全局極值而不是局部極值。01nxfxf0),(1nxfxff數值算法：迭代過程由四個部分組成初始點：可由用戶自行選擇；搜索方向：從什么方向去尋找下一個點；步長：在搜索方向上走多遠，一般有三種方法：固定步長：一次走固定距離；可變步長：如果固定距離目標函數值沒有改善，就擴大或縮小步長計算目標函數值；最優(yōu)步長：在搜索方向上尋找使目標函數值最

4、優(yōu)的步長（一維搜索）；終止條件：絕對誤差，如果|xk+1-xk|e或者|f(xk+1)-f(xk)|e ，e為最初選定的精度標準則停止；相對誤差，如果|xk+1-xk|/|xk|e或者|f(xk+1)-f(xk)|/|f(xk)|e，則停止；梯度：如果梯度的長度小于e，則停止。一個公司銷售四種藥品，每年在每個推銷員身上要花費5萬元，從推銷隊伍獲得的收入（排除了其他成本之后）為：其中xi為分配給每種藥品的推銷隊伍人數。如何使利潤最大呢？3.046.0375.025.013000 )4(1800 )3(1500 )2(2000 )1(xxxx一個公司要建立一個倉庫，從那里將貨物發(fā)送給四個客戶，客戶

5、的空間位置和需求量分別是：客戶 X坐標 Y坐標 年度需求量客戶1 5 10 200客戶2 10 5 150客戶3 0 12 180客戶4 12 0 250倉庫應該修在什么地方使得總運輸里程最小 1234x)(xf1dx 2d局部最優(yōu)局部最優(yōu)(陷阱陷阱)全局全局最優(yōu)最優(yōu)(一般情況下一般情況下)無法克服的困難無法克服的困難克服困難的兩種途徑克服困難的兩種途徑1) 限制問題的類型限制問題的類型前者理論上可徹底解決問題前者理論上可徹底解決問題, 但適用范圍小但適用范圍小2) 采取跳出局部陷阱的措施采取跳出局部陷阱的措施后者適用范圍大后者適用范圍大, 但理論上不能保證解決問題但理論上不能保證解決問題最常

6、用的條件最常用的條件 凸性凸性x)(xf)2(xx)1(x) 1 (xf xf)2(xf xl xlxf) 2()1 () 1 () 2()1 () 1 (xfxfxxf凸函數定義凸函數定義1, 0,) 2(),1 (nRxx對任意的對任意的總是成立總是成立x xl凸性能保證局部最優(yōu)就是全局最優(yōu)凸性能保證局部最優(yōu)就是全局最優(yōu) 1, 0()1 ()1 ()1 (*xfxfxfxfxfxxfxxxf設設*x是全局最優(yōu)解是全局最優(yōu)解如果如果 *xfxf, 由凸性可知由凸性可知說明這種點不會是局部最優(yōu)解說明這種點不會是局部最優(yōu)解凸集凸集的定義為：集合中任意兩個點的連接線段仍然屬于該集合，則該集合稱為凸

7、集。凸集定義可用數學符號表示如下：如s是凸集，則其中元素滿足10,)1 (,1221sxxxsxx定理：任意個凸集的交集仍是凸集設有K個凸集Ri（i1，2，K），用R表示它們的交集，若點x1、x2R，則從交集的定義知xx1（1）x2Ri（i1，2，K）式中01所以：xR也即R也是凸集。增加初始點有助于找到全局最優(yōu)解增加初始點有助于找到全局最優(yōu)解x)(xf1dx 2d例例 遺傳算法遺傳算法Genetic Algorithm容許目標函數上升有助于跳出局部陷阱容許目標函數上升有助于跳出局部陷阱x)(xf1dx 2d例例 禁忌搜索禁忌搜索 模擬退火模擬退火Taboo SearchSimulated A

8、nnealing當用迭代法求函數的極小點時，常常用到一維搜索，即沿某一已知方向求目標函數的極小點。一維搜索的方法很多，常用的有：1. 區(qū)域消去法（“成功失敗”，斐波那契Fibonacci法，0.618法等）；2. 插值法（拋物線插值法，三次插值法等）；3. 微積分中的求根法（切線法，二分法等）。)(mintfbta)(tf,ba,ba考慮一維極小化問題是區(qū)間上的下單峰函數，我們可以通過不斷地縮短的長度，來搜索得近似最優(yōu)解。單峰函數單峰函數設f(x)是定義在取間a.b上的一元函數。x*是f(x)在a,b上的全局極小點。如果f(x)在a,x*)上嚴格單調下降，在(x*,b上嚴格單調上升，則稱f(x

9、)是a,b上的單峰函數。（下單峰函數） *x*x定理：若f在閉區(qū)間axb內為下單峰連續(xù)函數，x*點為極小值。設x1、x2為區(qū)間內的兩點，且ax1x2f(x2)，則極小值不在(a,x1)內；2.若f(x1)f(x2)，則極小值不在(x2,b)內；3.若f(x1)=f(x2)，則極小值在(x1,x2)內。x)(xfba1x2x*x0.618法（黃金分割法）法（黃金分割法） 0.618法和斐波那契（Fibonacci）法都是分割方法，其基本思想是通過取試探點和進行函數值的比較，使包含極小點的搜索區(qū)間不斷縮短，當區(qū)間長度縮短到一定程度時，區(qū)間上各點的函數值均接近極小值，從而各點可以作為極小點的近似點。

10、這類方法僅需要計算函數值，用途很廣，尤其適用于非光滑及導數表達式復雜或寫不出的種種情況。 基本原理基本原理 通過比較搜索區(qū)間內兩點的函數值，逐步通過比較搜索區(qū)間內兩點的函數值，逐步縮短搜索區(qū)間縮短搜索區(qū)間； 比如：x1，x2(a,b),其中 x1x2 , 若f(x1)f(x2),取 x1,b為新的搜索區(qū)間。對新的搜索區(qū)間，再增加一個新的內點，通過比較上一次保留下來的內點和新選定內點的函數值便可得到一個新的縮小了的搜索區(qū)間。 x)(xfba1x2x3x如只進行一次消去操作，只需比較區(qū)間a,b中點及距中點很近一點函數值，如此至少可消去原區(qū)間的1/2。abx1x2如進行兩次消去操作，最好可使剩余區(qū)域

11、的中點恰好為消去中考慮的兩點中之一，如下圖所示消去ax1后x2為x1b的中點。此時便轉化為上面情形。abx1x2按此思想可將進行n次消去操作的過程轉化為進行n-1次消去的過程。這種方法對區(qū)間的劃分比例符合Fibonacci分數的定義。12111112111,nnnnnnnnnnnFFFFFFFFFbxbxFFabbxabx1x2在上述原則下，為使去掉的區(qū)間長一些，就一次而論，應使兩點盡量靠近區(qū)間中點，這樣無論去掉那一側，都可使區(qū)間縮短近一半，但是，由于此次留下的內點相當靠近留下的區(qū)間的一側，下一步再按對稱原則增選內點時，在去掉的區(qū)間部分必然較小，總體效益不好，于是可考慮采取如下對策所選內點使區(qū)間縮短率固定，即=固定值。按照取點對稱取點對稱和縮短率恒定縮短率恒定兩條原則，計算出=0.618，因此構造出來的算法就稱為0.618法。 1x1x2ab1 1 拋物線法拋物線法利用目標函數f（x）的某些信息，構造一個二次函數（拋物線）（x）作為目標函數的近似，用（x）的極小點代替f（x）的極小點。 這里介紹的三點二次法就是利用目標函數在三個不