第十講非線性規(guī)劃一運(yùn)籌學(xué)清華大學(xué)林謙演示文稿

第十講非線性規(guī)劃一運(yùn)籌學(xué)清華大學(xué)林謙演示文稿目前一頁\總數(shù)四十三頁\編于十八點(diǎn)（優(yōu)選）第十講非線性規(guī)劃一運(yùn)籌學(xué)清華大學(xué)林謙目前二頁\總數(shù)四十三頁\編于十八點(diǎn)§1非線性規(guī)劃問題的現(xiàn)實(shí)來源－問題的提出

（2）

[解]設(shè)公司應(yīng)經(jīng)營銷售第一、二種設(shè)備數(shù)額分別為x1件和x2件，追求的目標(biāo)為最大銷售額，即：目標(biāo)函數(shù)f(X)=30x1+450x2取極大由于營業(yè)時間有限，必須滿足：0.5x1+(2+0.25x2)x2≤800當(dāng)然，銷售設(shè)備數(shù)不會為負(fù)數(shù)，即：x1≥0，x2≥0綜合得出該問題數(shù)學(xué)模型為：

目標(biāo)函數(shù)max：f(X)=30x1+450x2約束條件0.5x1+2x2+0.25x22≤800

x1≥0，x2≥0目前三頁\總數(shù)四十三頁\編于十八點(diǎn)§2非線性規(guī)劃的數(shù)學(xué)模型及特點(diǎn)

（1）

非線性規(guī)劃的數(shù)學(xué)模型通常表示成以下形式。

minf(X)

hi(X)=0i=1，2，…，m

gj(X)≥0j=1，2，…，l[例4-3]求解下述非線性規(guī)劃

minf(X)=(x1－2)2+(x2－2)2

h(X)=x1+x2－6=0 目前四頁\總數(shù)四十三頁\編于十八點(diǎn)顯然，與直線AB相切的點(diǎn)必為最優(yōu)解。圖4-1(a)中的D點(diǎn)即為最優(yōu)點(diǎn)，此時目標(biāo)函數(shù)值為：f(X*)=2，x1*=x*2=3Af(X)=4f(X)=2x1x26320236BCD圖4-1(a)§2非線性規(guī)劃的數(shù)學(xué)模型及特點(diǎn)

（2）目前五頁\總數(shù)四十三頁\編于十八點(diǎn)[例4-4]非線性規(guī)劃為minf(X)=(x1－2)2+(x2－2)2

h(X)=x1+x2－6≤0顯然，此時的最優(yōu)解為C點(diǎn)(x1*=x2*=2，f(X*)=0)，該點(diǎn)落在可行或內(nèi)部，其邊界約束失去作用。從前面例中看出，非線性規(guī)劃的最優(yōu)解（如果存在）可在其可行域上任一點(diǎn)達(dá)到。因而，非線性規(guī)劃數(shù)學(xué)模型可以沒有約束條件，即存在無約束最優(yōu)化問題。

§2非線性規(guī)劃的數(shù)學(xué)模型及特點(diǎn)

（3）目前六頁\總數(shù)四十三頁\編于十八點(diǎn)§3解和算法的基本性質(zhì)

（1）

1．極小點(diǎn)、凸集及其關(guān)系①極小點(diǎn)定義i)對于X*

Q，如果存在一個

>0，使所有與X*的距離小于

的X

Q（即X

Q，且|X－X*|<）都滿足不等式f(X)≥f(X*)，則稱X*為f在Q上的一個相對極小點(diǎn)或局部極小點(diǎn)。若對于所有X

Q，X≠X*且與X*距離小于

，有f(X)>f(X*)，則稱X*為f在Q上的一個嚴(yán)格相對極小點(diǎn)。目前七頁\總數(shù)四十三頁\編于十八點(diǎn)§3解和算法的基本性質(zhì)

（2）

ii)點(diǎn)X*

Q，如果對于所有X

Q成立f(X)≥f(X*)，則稱X*為f在Q上的全局極小點(diǎn)。同樣，若對于所有X

Q，X≠X*時，存在f(X)>f(X*)，則稱X*為f在Q上的嚴(yán)格全局極小點(diǎn)。盡管問題的提法往往求全局極小點(diǎn)，然而，無論從理論上或從計(jì)算觀點(diǎn)看，實(shí)踐現(xiàn)實(shí)性表明我們必須以很多情形上滿足一個相對極小點(diǎn)。當(dāng)然，對于凸規(guī)劃，這二者是統(tǒng)一的。

目前八頁\總數(shù)四十三頁\編于十八點(diǎn)§3解和算法的基本性質(zhì)

（3）

②相對極小點(diǎn)的判定可行方向概念：沿給定方向作離開該點(diǎn)運(yùn)動，若運(yùn)動軌跡在可行域內(nèi)，則稱該運(yùn)動方向?yàn)榭尚蟹较颍ㄍǔＳ胐表示）。若從某點(diǎn)開始，沿任一可行方向運(yùn)動（運(yùn)動距離很小）都不能使目標(biāo)函數(shù)減少，則據(jù)定義，知該點(diǎn)即為相對極小點(diǎn)。i)判定極小點(diǎn)的必要條件（證明從略）

目前九頁\總數(shù)四十三頁\編于十八點(diǎn)§3解和算法的基本性質(zhì)

（4）

命題1（一階必要條件）：設(shè)是En子集，f(X)C1(C1表明存在一階導(dǎo)數(shù))是上函數(shù)，若X*是f(

X)在上一個相對極小點(diǎn)，則對于任一X*的可行方向dEn必有▽f(X*)·d≥0。（其中，▽f(X*)表示函數(shù)f(

X)的一階梯度或?qū)?shù)）命題2（二階必要條件——有約束情況）：設(shè)是En的一個子集，且f(

X)Ｃ2（Ｃ2表明存在二階導(dǎo)數(shù)）是上的一個函數(shù)。若X*是f(

X)在上的一個相對極小點(diǎn)。則對于任一X*處的可行方向dＥn有：A)▽f(X*)·d≥0B)▽f(X*)·d=0，則必有dT·▽2f(X*)·d≥0▽2f(

X)表示f(

X)的第二階梯度或二階導(dǎo)數(shù)，又稱Hess或海森陣，亦可用H或F表示。

目前十頁\總數(shù)四十三頁\編于十八點(diǎn)§3解和算法的基本性質(zhì)

（5）

命題3（二階必要條件——無約束情況）：設(shè)X*是集合的內(nèi)點(diǎn)，且X*是函數(shù)f(X)C2在上一個相對極小點(diǎn)。則：A)▽f(X*)=0B)對于所有d，則dT▽2f(X*)·d≥0ii)判斷極小點(diǎn)的充分條件命題（二階充分條件——無約束）：設(shè)f(X)C2是定義在以X*為內(nèi)點(diǎn)的一個區(qū)域上的函數(shù)，若A)▽f(X*)=0B)Hess陣H(X*)正定（或負(fù)定）則X*是f(X)的嚴(yán)格極小點(diǎn)（或極大點(diǎn)）

目前十一頁\總數(shù)四十三頁\編于十八點(diǎn)§3解和算法的基本性質(zhì)

（6）

iii)極小點(diǎn)的充分必要條件——無約束情形。（略）③凸函數(shù)與凹函數(shù)i)定義：·凸集：若在X集合中，任意兩點(diǎn)之聯(lián)線都落在該集合內(nèi)，則稱該集合為X的凸集。·凸函數(shù)：定義在凸集上的函數(shù)f(X)稱為凸函數(shù)，條件是對于每一對x1，x2及每一個a，0≤a≤1存在：f(ax1+(1－a)x2)≤af(x1)+1(1－a)f(x2)

上式中，若≤變?yōu)?lt;，則稱為嚴(yán)格凸函數(shù)。

目前十二頁\總數(shù)四十三頁\編于十八點(diǎn)§3解和算法的基本性質(zhì)

（7）凸函數(shù)在2維空間的形狀象一口鍋的縱剖面，參見圖4-2?！ぐ己瘮?shù)：定義在凸集上的函數(shù)g(X)稱為凹函數(shù)，條件是函數(shù)f(X)=－g(X)是凸的。若

－g(X)是嚴(yán)格凸的，則g(X)是嚴(yán)格凹的，因此凸與凹是嚴(yán)格對應(yīng)的，以后就只研究凸函數(shù)即可。

(a)嚴(yán)格凸x凸x非凸x圖4-2(b)(c)目前十三頁\總數(shù)四十三頁\編于十八點(diǎn)§3解和算法的基本性質(zhì)

（8）

ii）有關(guān)性質(zhì)（凸函數(shù)性質(zhì)）·設(shè)f1(X)，f2(X)是凸集上的凸函數(shù)，則函數(shù)f1(X)+f2(X)在上也是凸函數(shù)?！ぴO(shè)f(X)是凸集上的凸函數(shù)，則對任意的a≥0，函數(shù)af(X)是凸的?！ぴO(shè)f(X)是凸集上的凸函數(shù)，對每一個實(shí)數(shù)C，則集合C＝{x：x，f(X)C}是凸集。iii)凸函數(shù)的判定（略）

目前十四頁\總數(shù)四十三頁\編于十八點(diǎn)§3解和算法的基本性質(zhì)

（9）

④凸規(guī)劃定義：已知非線性規(guī)劃：

minf(X)gj(X)≥0若f(X)為凸函數(shù)，gj(X)為凹函數(shù)，則稱該規(guī)劃為凸規(guī)劃。凸規(guī)劃的局部極值點(diǎn)即為全局極值點(diǎn)。線性規(guī)劃為凸規(guī)劃。2．下降算法的收斂性問題（定性分析）（略）

目前十五頁\總數(shù)四十三頁\編于十八點(diǎn)§4非線性規(guī)劃求解方法分類（1）

1．一維最優(yōu)化①斐波那契（Fibonacci）法②黃金分割法（0.618法）③牛頓法（切線法）④拋物線逼近法⑤成功和失敗法目前十六頁\總數(shù)四十三頁\編于十八點(diǎn)§4非線性規(guī)劃求解方法分類（2）

2．多維最優(yōu)化①無約束情形(i)采用導(dǎo)數(shù)：

(a)梯度法

(b)牛頓法

(c)共軛梯度法

(d)變尺度法目前十七頁\總數(shù)四十三頁\編于十八點(diǎn)§4非線性規(guī)劃求解方法分類（3）

(ii)不采用導(dǎo)數(shù)：

(a)直接法（模式搜索法）

(b)可變多面體法

(c)鮑威爾法

(d)隨機(jī)搜索法

目前十八頁\總數(shù)四十三頁\編于十八點(diǎn)§4非線性規(guī)劃求解方法分類（4）

②有約束情形(i)線性逼近法(ii)可行方向法(iii)罰函數(shù)法(iv)可變?nèi)莶罘ǚ蔷€性規(guī)劃的求解方法很多，上面列出的僅是一些常用的方法。后面將簡單介紹幾個最基本解法的思路和步驟。目前十九頁\總數(shù)四十三頁\編于十八點(diǎn)第十講非線性規(guī)劃（二）§1一維最優(yōu)化方法

§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）目前二十頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（1）

目前常用的一些方法有：·斐波那契（

Fibonacci）法——序貫試驗(yàn)法·黃金分割法（0.618法）·牛頓切線法·拋物線逼近法·成功與失敗試探法下面將著重介紹斐波那契與黃金分割法的主要思路及步驟。目前二十一頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（2）

一、斐波那契法與黃金分割法的基本思路1．非線性規(guī)性的所有求解方法在理論上都是尋找出局部極值點(diǎn)，即所搜尋區(qū)域是單峰函數(shù)。當(dāng)然，作為一維搜索方法的斐波那契法與黃金分割法亦不例外。然而，這兩種方法的尋優(yōu)途徑不是直接找出最優(yōu)點(diǎn)，而是不斷縮小最優(yōu)點(diǎn)所處區(qū)域，直到符合精度為止。這兩種方法的主要特點(diǎn)為：①適于單峰（谷）函數(shù)；②壓縮峰（谷）點(diǎn)所處的區(qū)域。目前二十二頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（3）

現(xiàn)在分析該法是如何進(jìn)行尋優(yōu)的：設(shè)已知單峰函數(shù)f(t)的峰點(diǎn)t*（最小點(diǎn)）處在t=[a，b]區(qū)間（見圖4-3a）在區(qū)間[a，b]中，任取兩點(diǎn)a1、b1且a1<b1，并計(jì)算f(a1)和f(b1)，則可出現(xiàn)下列結(jié)果：1）f(a1)<f(b1)，則t*必在區(qū)間[a，b1]，如圖4-3中(a)所示。2）f(a1)≥f(b1)，則t*必在[a1，b]中。如圖4-3(b)所示。目前二十三頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（4）

0a

b2

t*

a1

b1

b

tf(t)(a)0a

a1

t*

b1

b

t圖4-3f(t)f(t)f(t)(b)可見，只要在[a，b]內(nèi)任取兩點(diǎn)，就必能把t*壓縮在區(qū)間[a，b1]或[a1，b]內(nèi)。若要繼續(xù)縮小區(qū)間，只需再計(jì)算1個點(diǎn)，又可縮短一部分區(qū)間長度。

目前二十四頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（5）

例如，如果已知t*在[a，b1]內(nèi)，由于a1已在[a，b1]中，故只需取一點(diǎn)計(jì)算。假定取為b2，則計(jì)算f(b2),并與已計(jì)算過的f(a1)比較，又可確定出t*在[a，a1]或者在[b2，b1]中，具體見圖4-3中的(a)。這樣反復(fù)進(jìn)行，直到把區(qū)間縮小到一定精度為止。從上述分析知，包含t*的區(qū)間縮小率與計(jì)算函數(shù)值次數(shù)及取點(diǎn)技巧有關(guān)?，F(xiàn)問，采用最佳取點(diǎn)法，計(jì)算函數(shù)值n次，能把多大區(qū)間縮短為1呢？令Fn表示計(jì)算n個函數(shù)值后能縮短為1的最大原區(qū)間長度，則知F0=F1=1（不計(jì)算或計(jì)算一點(diǎn)不能把原區(qū)間縮短，參見圖4-3，開始只算一點(diǎn)a1或b1，都不能壓縮原區(qū)間）。目前二十五頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（6）

F2=2（a1、b1取在中間點(diǎn)附近，可近似縮短一半，故把新區(qū)間作為1，則原區(qū)間為2）。同理可得，F(xiàn)3=3，F(xiàn)4=5，…經(jīng)分析，知序列{Fn}符合遞推公式Fn=Fn－1+Fn－2(n≥2)計(jì)算點(diǎn)數(shù)n與原區(qū)間長度（令新區(qū)間為1時）Fn的關(guān)系可示于表4-1中。目前二十六頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（7）

Fn又稱為斐波那契常數(shù)，其含義是經(jīng)過n次計(jì)算后，區(qū)間縮短率為1/Fn，采用斐波那契常數(shù)進(jìn)行一維尋優(yōu)稱為斐波那契法。用該法尋優(yōu)收斂快。計(jì)算次數(shù)少，然而每步取點(diǎn)繁瑣，且各步縮短率不同。為此，引出黃金分割法。

表4-1

n

012345…Fn

112358…目前二十七頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（8）

黃金分割法與斐波那契法思路完全相同，僅僅是在區(qū)間內(nèi)的取點(diǎn)方式簡單化，現(xiàn)不加推導(dǎo)的引出該法的區(qū)間內(nèi)取點(diǎn)規(guī)則。設(shè)原區(qū)間為[a0，b0]，中間取兩點(diǎn)為a1，b1（見圖4-4）

00.3820.6181a0b2a1b1b0圖4-4目前二十八頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（9）

令線段即，若經(jīng)計(jì)算f(a1)與f(b1)后，知f(a1)<f(b1)，則保留[a0，b1]區(qū)間。此時即a1在新區(qū)間地位等同于目前b1在原區(qū)間地位，于是在新區(qū)間[a0，b1]中只需取點(diǎn)b2，使，便又可進(jìn)行下一步計(jì)算。該法每迭代一次，使區(qū)間縮小到原來的0.618倍，故又稱0.618法。目前二十九頁\總數(shù)四十三頁\編于十八點(diǎn)§1一維最優(yōu)化方法

（10）

二、其它有關(guān)方法概述1．牛頓切線法2．拋物線擬合法3．成功與失敗試探法目前三十頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（1）

無約束極值問題可簡單表述為：minf(X)，XEn

（n維歐氏空間）X(k+1)=X(k)+p(k)且滿足f[X(k+1)]<f[X(k)]這樣逐步迭代直至滿足精度條件

‖▽f[X(k+1)]‖<

1(梯度絕對值<1)或‖f[X(k+1)]－f[X(k)]‖<

2（兩步計(jì)算的函數(shù)值之差的絕對值<

2）時迭代停止（其中，1，2為給定精度）。目前三十一頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（2）

求解非線性規(guī)劃問題的迭代法，關(guān)鍵是如何求出每步的搜索方向p(k)及步長。由于確定p(k)及的途徑不同，從而導(dǎo)致不同的尋優(yōu)方法。其中可分兩大類，一類在迭代中需用到函數(shù)的一階導(dǎo)數(shù)（梯度）或二階導(dǎo)數(shù)，稱為“解析法”，另一類不用函數(shù)的導(dǎo)數(shù)值，稱為“直接法”。通常，“直接法”速度較慢，但由于不用函數(shù)導(dǎo)數(shù)值，使得十分復(fù)雜的函數(shù)極值問題可得到解決。目前三十二頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（3）

一、使用導(dǎo)數(shù)（梯度）的無約束尋優(yōu)方法１．梯度法（最速下降法）由于選擇方向時只考慮到當(dāng)前下降最快，未顧及到總尋優(yōu)快慢，因而又稱“瞎子爬山法”。令▽f[X(k)]表示X(k)點(diǎn)的梯度，則X(k+1)=X(k)－(k)▽f[X(k)]其中，步長(k)為尋優(yōu)步長，有二種選擇方法：①試探法目前三十三頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（4）

②解析法*(k)=X(k+1)=X(k)－·▽f[例4-12]采用梯度法求解函數(shù)f(X)=x21+25x22的極小點(diǎn)：[解]設(shè)初始點(diǎn)為：

X(0)=，則f[X(0)]=104。

目前三十四頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（5）

X(0)處梯度▽f[X(0)]=然后沿負(fù)梯度方向求一維極小值。X(1)=X(0)－▽f[X(0)]=f[X(1)]=(2－4)2+25(2－100)2令df/d=0，得：2(2－4)(－4)+50(2－100)(－100)=0目前三十五頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（6）

解得0=0.02003072X(1)=X(0)－0▽f[X(0)]==f[X(1)]=3.686164然后從X(1)出發(fā)，與上面同樣迭代可得X(2)，直到進(jìn)行約10次迭代，即可得最優(yōu)解為：X*=，f*=0梯度法簡單易行，雖是古老方法，至今仍被普遍應(yīng)用。該法速度較慢。目前三十六頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（7）

2．二階導(dǎo)數(shù)法（牛頓法）梯度法的每步尋優(yōu)方向可看作為目標(biāo)函數(shù)設(shè)計(jì)的一種線性逼近；而牛頓法是二階導(dǎo)數(shù)法，它是目標(biāo)函數(shù)的一種二次逼近。牛頓法的每步搜索方向S選擇如下：令△X(k)=X(k+1)－f[X(k+1)]則f[X(k+1)]用△X(k)表示的二次逼近式為：f[X(k+1)]=f[X(k)]+▽Tf[X(k)]△X(k)+[△X(k)]T▽2f[X(k)]△X(k)為求f[X]在△X(k)方向上的極值點(diǎn)，可將f[X]對△X分量微分然后令為零便得：△X(k)=－{▽2f[X(k)]}－1▽f[X(k)]∴X(k+1)=X(k)－{▽2f[X(k)]}－1▽f[X(k)]=X(k)－H－1[X(k)]▽f[X(k)]目前三十七頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（8）

即，牛頓法的尋優(yōu)方向及步長為在原有梯度向量上左乘二階段度陣▽2f(X)（即海森陣H(X)）之逆陣。（上述牛頓法迭代公式對求極大值和極小值都適用）牛頓法通常比梯度法收斂快，然而需采用二階梯度陣之逆陣，逆陣計(jì)算往往比較繁瑣。[例4-13]由Rosenbrock設(shè)計(jì)的求無約束極小值的目標(biāo)函數(shù)表達(dá)式如下（見圖4-9）如下：f[X]=100(x2－x12)2+(1－x1)2目前三十八頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（9）

1)采用梯度法設(shè)X(k)=[－0.5，0.5]T，f[X(k)]=8.5f[X]規(guī)格化梯度在X(k)=[－0.5，0.5]T處為=[0.685，0.729]T目前三十九頁\總數(shù)四十三頁\編于十八點(diǎn)§2多維無約束尋優(yōu)方法（使用導(dǎo)數(shù)）（10）

而此處規(guī)格化負(fù)梯度

=[－0.685，－0.729]T沿這方向?qū)ふ襒(k+1)，采用