第四章 非線性規(guī)劃 山大刁在筠 運籌學(xué)講義.doc

第四章 非線性規(guī)劃教學(xué)重點：凸規(guī)劃及其性質(zhì)，無約束最優(yōu)化問題的最優(yōu)性條件及最速下降法，約束最優(yōu)化問題的最優(yōu)性條件及簡約梯度法。教學(xué)難點：約束最優(yōu)化問題的最優(yōu)性條件。教學(xué)課時：24學(xué)時主要教學(xué)環(huán)節(jié)的組織：在詳細講解各種算法的基礎(chǔ)上，結(jié)合例題，給學(xué)生以具體的認(rèn)識，再通過大量習(xí)題加以鞏固，也可以應(yīng)用軟件包解決一些問題。第一節(jié) 基本概念教學(xué)重點：非線性規(guī)劃問題的引入，非線性方法概述。教學(xué)難點：無。教學(xué)課時：2學(xué)時主要教學(xué)環(huán)節(jié)的組織：通過具體問題引入非線性規(guī)劃模型，在具體講述非線性規(guī)劃方法的求解難題。1、非線性規(guī)劃問題舉例例1 曲線最優(yōu)擬合問題已知某物體的溫度與時間t之間有如下形式的經(jīng)驗函數(shù)關(guān)系： （*）其中，是待定參數(shù)?，F(xiàn)通過測試獲得n組與t之間的實驗數(shù)據(jù)，i=1，2，,n。試確定參數(shù)，使理論曲線(*)盡可能地與n個測試點擬合。例 2 構(gòu)件容積問題通過分析我們可以得到如下的規(guī)劃模型：基本概念設(shè)，,如下的數(shù)學(xué)模型稱為數(shù)學(xué)規(guī)劃(Mathematical Programming, MP)：約束集或可行域 MP的可行解或可行點MP中目標(biāo)函數(shù)和約束函數(shù)中至少有一個不是x的線性函數(shù)，稱(MP)為非線性規(guī)劃令 ，其中，那么(MP)可簡記為 或者 當(dāng)p=0,q=0時，稱為無約束非線性規(guī)劃或者無約束最優(yōu)化問題。否則，稱為約束非線性規(guī)劃或者約束最優(yōu)化問題。定義4.1.1 對于非線性規(guī)劃(MP)，若，并且有則稱是(MP)的整體最優(yōu)解或整體極小點，稱是(MP)的整體最優(yōu)值或整體極小值。如果有則稱是(MP)的嚴(yán)格整體最優(yōu)解或嚴(yán)格整體極小點，稱是(MP)的嚴(yán)格整體最優(yōu)值或嚴(yán)格整體極小值。定義 4.1.2 對于非線性規(guī)劃(MP)，若，并且存在的一個領(lǐng)域，使，則稱是(MP)的局部最優(yōu)解或局部極小點，稱是(MP)的局部最優(yōu)值或局部極小點。如果有，則稱是(MP)的嚴(yán)格局部最優(yōu)解或嚴(yán)格局部極小點，稱是(MP)的嚴(yán)格局部最優(yōu)值或嚴(yán)格局部極小點。定義 4.1.3 設(shè)，若存在，使則稱向量p是函數(shù)f(x)在點處的下降方向。定義 4.1.4 設(shè)，若存在，使則稱向量p是函數(shù)f(x)在點處關(guān)于X的可行方向。一般解非線性規(guī)劃問題的迭代方法的步驟：第一步：選取初始點；第二步：構(gòu)造搜索方向；第三步：根據(jù)，確定步長；第四步：令若已滿足某種終止條件，停止迭代，輸出近似最優(yōu)解，否則令，轉(zhuǎn)回第二步。常用規(guī)則：1、相鄰兩次迭代點的絕對差小于給定誤差，即；2、相鄰兩次迭代點的相對差小于給定誤差，即；3、；4、第二節(jié) 凸函數(shù)和凸規(guī)劃教學(xué)重點：凸函數(shù)的概念及性質(zhì)，凸規(guī)劃的概念、性質(zhì)及判定。教學(xué)難點：凸規(guī)劃的概念及性質(zhì)。教學(xué)課時：4學(xué)時主要教學(xué)環(huán)節(jié)的組織：首先介紹凸函數(shù)的定義，然后給出凸函數(shù)及凸規(guī)劃的性質(zhì)。凸函數(shù)的定義及性質(zhì)：定義 4.2.1 設(shè)是非空凸集，如果對任意的有，則稱f是S上的凸函數(shù)，或f在S上是凸的。如果對于任意的有，則稱f是S上的嚴(yán)格凸函數(shù)，或f在S上是嚴(yán)格凸的。若-f是S上的（嚴(yán)格）凸函數(shù)，則稱f是S上的（嚴(yán)格）凹函數(shù)，或f在S上是（嚴(yán)格）凹的。(a) 凸函數(shù) (b)凹函數(shù)凸函數(shù)的性質(zhì)：定理 4.2.1 設(shè)是非空凸集。（1）若是S上的凸函數(shù)，則 是S上的凸函數(shù)；（2）若都是S上的凸函數(shù)，則是S上的凸函數(shù)。定理 4.2.2 設(shè)是非空凸集，是凸函數(shù)，則集合是凸集。注：一般來說上述定理的逆是不成立的。定理 4.2.3 設(shè)是非空開凸集，可微，則（1） f是S上的凸函數(shù)的充要條件是， 其中是函數(shù)f在點處的一階導(dǎo)數(shù)或梯度。（2） f是S上的嚴(yán)格凸函數(shù)的充要條件是， 證明 （1）. 必要性.設(shè)是上的凸函數(shù)，對有：故（4.2.3）由多元函數(shù)Taylor展開式可知：將其帶入（4.2.3）并令便便可得到充分性.設(shè)對取，由凸知，對分別有：（4.2.4）和（4.2.5）將（4.2.4）乘以，（4.2.5）乘以，兩式相加得到（2）. 證明和（1）類似.定理 4.2.4 設(shè)是非空開凸集，二階連續(xù)可導(dǎo)，則f是S上的凸函數(shù)的充要條件是f的Hesse矩陣在S上是半正定的。當(dāng)在S上是正定矩陣時，f是S上的嚴(yán)格凸函數(shù)。（注意：該逆命題不成立。）凸規(guī)劃及其性質(zhì) 約束集如果(MP)的約束集X是凸集，目標(biāo)函數(shù)f是X上的凸函數(shù)，則(MP)叫做非線性凸規(guī)劃，或簡稱為凸規(guī)劃。凸規(guī)劃的性質(zhì)定理 4.2.5 對于非線性規(guī)劃(MP)，若皆為上的凸函數(shù)，皆為線性函數(shù)，并且f是X上的凸函數(shù)，則(MP)是凸規(guī)劃。定理 4.2.6 凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。證明：設(shè)是凸規(guī)劃（MP）的一個局部解，存在則的臨域使得若不是（MP）的整數(shù)最優(yōu)解，則存在，使又因為是凸函數(shù)，有顯然，當(dāng)充分小時，有出現(xiàn)矛盾。例 4.2.3 驗證下列（MP）是凸規(guī)劃解答：將二次目標(biāo)函數(shù)改寫為：由例4.2.2知的 Hesse矩陣為： 的一、二、三階順序主子式分別為：正定，為凸函數(shù)。而半正定，是凸函數(shù)。其他約束條件均為線性。故改（MP）為凸規(guī)劃。第三節(jié) 一維搜索教學(xué)重點：0.618法，牛頓法，非精確一維搜索方法。教學(xué)難點：0.618法和牛頓法。教學(xué)課時：4學(xué)時主要教學(xué)環(huán)節(jié)的組織：首先介紹凸函數(shù)的定義，然后給出凸函數(shù)及凸規(guī)劃的性質(zhì)。目標(biāo)函數(shù)為單變量的非線性規(guī)劃問題稱為一維搜索問題(或線性搜索問題)，其數(shù)學(xué)模型為，其中。1、0.618法函數(shù)稱為在a,b上是單谷的，如果存在一個，使得在上嚴(yán)格遞減，且在上嚴(yán)格遞增。區(qū)間a,b稱為的單谷區(qū)間。第一步： 插入等長度，令第二步： 使區(qū)間縮小同樣的比例，不妨設(shè)新區(qū)間為 設(shè)插入，則 若令，則有；若令，則有以后類似迭代算法的具體步驟：第1步 確定單谷區(qū)間a,b，給定最后區(qū)間精度;第2步 計算最初兩個探索點并計算，；第3步 若，轉(zhuǎn)第4步。否則轉(zhuǎn)第5步；第4步 若，停止迭代，輸出。否則令，計算，轉(zhuǎn)第3步；第5步 若，停止迭代，輸出。否則令，計算，轉(zhuǎn)第3步。 例4.3.1 用0.618法求解的單谷區(qū)間為0,3，迭代步驟可以由下表給出：012340000.4380.70831.8541.1461.1461.1461.1460.7080.4380.7081.8541.1460.7080.8760.2131 3.6648-0.0611 0.21310.2082 -0.0611-0.0611 -0.0798 換 換在0.618法中每次迭代搜索區(qū)間按常比例縮小，所以要使給定的單谷區(qū)間減少到所要求的區(qū)間精度，需要的迭代次數(shù)是可以預(yù)估的。另外若每次每次迭代按不同比例縮小搜索區(qū)間，但仍要求每次迭代只計算一個函數(shù)值，且希望在搜索點個數(shù)相同的情況下使最終的搜索區(qū)間的長度最小，按此要求設(shè)計的方法是Fibonacci法2、牛頓法考慮一維搜索問題，其中是二次可微的，且。Newton法的基本思想是：用在探索點處的二階泰勒展開式來替代，然后用的最小點作為新的探索點.據(jù)此，可得：開始時給定一個初始點，然后按照上式進行迭代計算，當(dāng)時，終止迭代，為的最小點的近似。Newton法步驟第1步 給定初始點，；第2步 如果，停止迭代，輸出.否則，當(dāng)時，停止，解題失??；當(dāng)時，轉(zhuǎn)下一步；第3步 計算，如果，停止迭代，輸出，否則，轉(zhuǎn)至第2步；例 用牛頓法求下題。解：首先求出，取，計算結(jié)果列于下表110.785422-0.5708-0.51781.325830.11690.11631.01374-0.001061用數(shù)學(xué)分析方法知，的精確最優(yōu)解是，用Newton法迭代三此后就已經(jīng)十分接近該最優(yōu)解。但是取，則有：121.107152-3.5357-1.295213.50313.95點列不收斂于從任意初始點開始的Newton法產(chǎn)生的點列，一般來說不一定收斂，即使收斂，其極限點也不一定是 的極小點，只能保證它是 的駐點。但當(dāng)初始點充分接近 時，可以證明Newton法是收斂的。非精確一維搜索：3、Goldstein法思想預(yù)先指定兩個數(shù)滿足，用一下兩個式子限定 （4.3.10） （4.3.11）（4.3.10）式所限定的是使位于直線之下的點，用以控制不太大；（4.3.11）用于限定使位于直線之上的點，用以控制不太小.第1步 給定滿足的正數(shù)，增大探索點系數(shù)；初始探索點（或）。令（或），第2步 計算若，進行第3步；否則，令轉(zhuǎn)第4步；第3步 若，停止迭代，輸出。否則，令若，進行第4步；否則，令，轉(zhuǎn)第2步；第4步 取，令，轉(zhuǎn)第2步。例 用 法 求解下題 解答：取并且因為，令由于，選取新探索點并計算，因為有和停止迭代，得到非精確解4.Armijo法取定，用以下兩個式子限定不太大也不太?。旱谒墓?jié) 無約束最優(yōu)化問題教學(xué)重點：無約束最優(yōu)化問題的最優(yōu)性條件，最速下降法。教學(xué)難點：最速下降法。教學(xué)課時：6學(xué)時主要教學(xué)環(huán)節(jié)的組織：首先給出無約束最優(yōu)化條件，然后介紹無約束最優(yōu)化問題的兩種算法，最速下降法、共軛方向法。1 無約束問題的最優(yōu)性條件定理4.4.1 設(shè)在點處可微。若存在，使則向量p是f在點處的下降方向。證：因為在點處可微，有泰勒展開， （4.4.1）由于，因而，則存在，對有 由（4.4.1）由定義知是在點的處下降方向定理 4.4.2 設(shè)在點處可微。若是(UMP)的局部最優(yōu)解，則 定理4.4.3 設(shè)在點處的Hesse矩陣存在。若，并且正定則是(UMP)的局部最優(yōu)解。 定理4.4.4 設(shè)，f是上得可微凸函數(shù)。若有則是(UMP)的整體最優(yōu)解。證：因為是上的可微凸函數(shù)，由定理4.2.3知由于，因而推知由此是（UMP）問題的整數(shù)最優(yōu)解2 最速下降法設(shè)（NMP）問題中的目標(biāo)函數(shù)一階連續(xù)可微最速下降法基本思想：從當(dāng)前點出發(fā)，取函數(shù)在點處下降最快的方向作為我們的搜索方向，由的Taylor展開式知忽略的高階無窮小項，可見取時，函數(shù)值下降的最多。最速下降法的計算步驟：第1步 選取初始點，給定終止誤差，令；第2步 計算，若，停止迭代，輸出。否則進行第3步；第3步 取第4步 進行一維搜索，求，使得令，轉(zhuǎn)第2步。例4.4.2 用最速下降法求解如下（UMP）問題 取初始點終止誤差顯然，該問題的整體最優(yōu)解為下面用最速下降法求解.由構(gòu)造負梯度方向則令，解得：，所以重復(fù)上述過程，經(jīng)十輪迭代可得滿足誤差要求的解。最速下降法算法分析：1）隨著迭代次數(shù)的增加，收斂速度越來越慢；2）最速下降法的相鄰兩個搜索方向是彼此正交的；3）具有全局收斂性。3 共軛方向法定義 4.4.1 設(shè)A為n階實對稱，對于非零向量，若有則稱p和q是相互A共軛的。對于非零向量組，若有則稱是A共軛方向組，也稱它們?yōu)橐唤MA共軛方向。定理4.4.5 設(shè)A是n階實對稱正定矩陣，是非零向量。若是一組A共軛方向，則它們一定是線性無關(guān)的?？紤]二次嚴(yán)格凸函數(shù)的無約束最優(yōu)化問題： （AP）其中A是n階實對稱正定矩陣，定理 4.4.6 對于問題(AP)，若為任意一組A共軛方向，則由任意初始點出發(fā)，依次沿進行精確一維搜索，則最多經(jīng)n次迭代可達(AP)的整體最優(yōu)解。共軛方向法-步驟第1步 選取初始點，給定終止誤差；第2步 計算，若，停止迭代，輸出；否則，進行第3步；第3步 取，令；第4步 進行一維搜索求使得，令；第5步 計算，若，停止迭代，輸出；否則，進行第6步；第6步 若k+1=n，令，轉(zhuǎn)第3步；否則進行第7步；第7步 用F-R公式取，其中。令k:=k+1，轉(zhuǎn)第4步。例 用F-R法求解如下（UMP）問題 取初始點終止誤差解： F-R方法的第一輪迭代與最速下降法相同，由例4.4.2知下面利用F-R公式（4.4.9）構(gòu)造新的共軛方向，其中：所以令，有，因而得到下一個迭代點,由于，停止迭代，輸出整體最優(yōu)解共軛方向法-算法分析：1）F-R法具有二次終止性。對一般可微函數(shù)的無約束優(yōu)化問題，當(dāng)函數(shù)滿足一定的條件時，可以證明F-R方法具有全局收斂性其收斂速度比最速下降法快；2）F-R法強烈依賴于一位搜索的精確性。第五節(jié) 約束最優(yōu)化方法教學(xué)重點：約束最優(yōu)化問題的最優(yōu)性條件，簡約梯度法和懲罰函數(shù)法。教學(xué)難點：約束最優(yōu)化問題的最優(yōu)性條件。教學(xué)課時：8學(xué)時主要教學(xué)環(huán)節(jié)的組織：首先給出約束最優(yōu)化問題的最優(yōu)性條件即K_T條件，然后介紹兩種約束最優(yōu)化方法：簡約梯度法和懲罰函數(shù)法。1、約束最優(yōu)化問題的最優(yōu)性條件給定約束最優(yōu)化問題： 其中 積極約束：稱使的約束為點的一個積極約束。我們記積極約束的下標(biāo)集為：K-T條件：定理 4.5.1 設(shè)和在點處可微，在點處連續(xù)，在點處連續(xù)可微，并且各線性無關(guān)。若是(MP)的局部最優(yōu)解，則存在兩組實數(shù)和，使得：“向量組線性無關(guān)”這個條件稱為約束規(guī)范條件其幾何意義可以用下圖來說明。圖4.5.1若定理4.5.1中進一步要求在點處均可微，則K-T條件可簡便寫為（4.5.8）其中為互補松緊條件例4.5.1用K-T條件求解下列問題解：問題（4.5.1）的Lagrange函數(shù)為：得到K-T條件如下作為K-T點，還應(yīng)滿足可行性條件：從互補松緊條件入手進行討論（1） 設(shè)此時可求解出，不滿足可行性條件中的不等式約束。舍棄。（2） 設(shè)解出為K-T點由定理4.5.2知為整體最優(yōu)解定理 4.5.2 對于(MP)問題，若，在點處連續(xù)可微，可行點滿足(MP)的K-T條件，且是凸函數(shù)，是線性函數(shù)，則是(MP)的整體最優(yōu)解。2. 簡約梯度法其中，簡約梯度法-基本思想首先，分析等式約束得，帶入目標(biāo)函數(shù);令，即為在處對應(yīng)的簡約梯度.其次，再由構(gòu)造定理 4.5.3 對于非線性規(guī)劃問題(4.5.12)，設(shè)f是可微函數(shù)，并且有分解，。若由下式確定， (*)則：（1） 當(dāng)時，是f在點處關(guān)于的可行下降方向；（2） 的充要條件是是問題(4.5.12)的K-T點。簡約梯度法-Wolfe法步驟第1步 選取初始可行點，給定終止誤差，令k:=0;第2步 設(shè)是的m個最大分量的下標(biāo)集，對矩陣A進行相應(yīng)分解第3步 計算，然后，計算簡約梯度記的第個分量為；第4步 按(*)式構(gòu)造可行下降方向。若，停止迭代，輸出；否則進行第5步；第5步 進行有效一維搜索，求解，得到最優(yōu)解，其中，令，k:=k+1，轉(zhuǎn)第2步例 用Wolfe法求解約束極小化問題解：首先將問題化為：第一輪迭代： ，相應(yīng)分解為由公式（4.5.20）有，由此可得可行下降方向為根據(jù)（4.5.23）式有，求解可得最優(yōu)解，于是得到下一個迭代點。然后依次進行第二輪第三輪迭代，最后得到整體最優(yōu)解3. 懲罰函數(shù)法思想：利用問題中的約束函數(shù)做出適當(dāng)?shù)膸в袇?shù)的懲罰函數(shù)，然后在原來的目標(biāo)函數(shù)上加上懲罰函數(shù)構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把(MP)問題的求解轉(zhuǎn)換為求解一系列無約束非線性規(guī)劃問題。 設(shè)法適當(dāng)?shù)丶哟蟛豢尚悬c處對應(yīng)的目標(biāo)函數(shù)值，使不可行點不能成為相應(yīng)無約束極小化問題的最優(yōu)解?？扇×P函數(shù)：相應(yīng)的構(gòu)造增廣目標(biāo)函數(shù)：當(dāng)充分大時，總可使（MP）問題轉(zhuǎn)換為無約束的極小化問題實際應(yīng)用中，選取一個遞增且趨于無窮的正罰函數(shù)參數(shù)列：其中， 罰函數(shù)法