最優(yōu)化方法教案

1、第一章最優(yōu)化問題與數(shù)學(xué)預(yù)備知識(shí)最優(yōu)化分支：線性規(guī)劃，整數(shù)規(guī)劃，幾何規(guī)劃，非線性規(guī)劃，動(dòng) 態(tài)規(guī)劃傳統(tǒng)；隨機(jī)規(guī)劃，模糊規(guī)劃，網(wǎng)絡(luò)規(guī)劃等較新。又稱規(guī) 劃論。應(yīng)用最優(yōu)化方法解決問題時(shí)一般有以下幾個(gè)特點(diǎn)：1. 實(shí)用性強(qiáng)2. 采用定量分析的科學(xué)手段3計(jì)算量大，必須借助于計(jì)算機(jī)4.理論涉及面廣應(yīng)用領(lǐng)域：工業(yè)，農(nóng)業(yè)，交通運(yùn)輸，能源開發(fā)，經(jīng)濟(jì)方案，企業(yè) 管理，軍事作戰(zhàn)。§ 1.1最優(yōu)化問題實(shí)例最優(yōu)化問題：追求最優(yōu)目標(biāo)的數(shù)學(xué)問題。經(jīng)典最優(yōu)化理論：1 無約束極值問題：opt fXi，X2， ,Xnmin fxX2， ,Xn或 max f Xi，X2， ,Xn其中，f Xi，X2， ,xn是定義在n維空間上

2、的可微函數(shù)。解法求極值點(diǎn)：求駐點(diǎn)，即滿足彳治Xi, ,Xn0fx2 Xi, ,Xn0fXn X1, ,Xn0并驗(yàn)證這些駐點(diǎn)是否極值點(diǎn)。2約束極值問題：Opt f Xi，X2， ,Xns.t.hj(Xi，X2，, Xn)0, j 1,2,1(1 n)解法：采用Lagrange乘子法，即將問題轉(zhuǎn)化為求 Lagrange函數(shù)L(X1,X2,l) f (X1,X2,l,Xn)jhj(X,Xn)j 1的無約束極值問題近代最優(yōu)化理論的實(shí)例:例1 生產(chǎn)方案問題設(shè)某工廠有3種資源B1，B2，Bs，數(shù)量各 為b1, b2, bs,要生產(chǎn)10種產(chǎn)品A1，A10。每生產(chǎn)一個(gè)單位的Aj需要消耗Bi的量為aij，根據(jù)合

3、同規(guī)定，產(chǎn)品Aj的量不少于dj，再 設(shè)Aj的單價(jià)為q。問如何安排生產(chǎn)方案，才能既完成合同，又使總收入最多？線性規(guī)劃問題數(shù)學(xué)模型：設(shè)Aj的方案產(chǎn)量為Xj , z為總收入10目標(biāo)函數(shù)：maxzCjXjj i10ajXj bi,i 1,2,3約束條件：j 1Xj dj, j 1,2,10線性規(guī)劃問題通常采用單純形法來求解。例2 工廠設(shè)址問題要在m個(gè)不同地點(diǎn)方案修建 m個(gè)規(guī)模不完 全相同的工廠，他們的生產(chǎn)能力分別是 a1,a2 ,am 為簡(jiǎn)便起見， 假設(shè)生產(chǎn)同一種產(chǎn)品，第i個(gè)工廠的建設(shè)費(fèi)用fj 1,2, ,m。又 有n個(gè)零售商店銷售這種產(chǎn)品，對(duì)這種產(chǎn)品的需求量分別為 bb2 ,bn，從第i個(gè)工廠運(yùn)送一

4、個(gè)單位產(chǎn)品到第j個(gè)零售商店的運(yùn) 費(fèi)為q。試決定應(yīng)修建哪個(gè)工廠，使得既滿足零售商店的需求，又使 建設(shè)工廠和運(yùn)輸?shù)目傎M(fèi)用最小?；旌险麛?shù)規(guī)劃問題數(shù)學(xué)模型： 設(shè)第i個(gè)工廠運(yùn)往第j個(gè)零售商店的產(chǎn)品數(shù)量為Xj i=1，m; j=1，n,且1,如果修建第i個(gè)工廠0,否那么,mmn目標(biāo)函數(shù)：min zfi yc Xji 1j 1yinXij4 yi, i1, ,mj 1mXijbj, j約束條件：i 11, ,nyi 0 或 1, i1, ,mXj 0, i 1,m; j 1, ,n整數(shù)規(guī)劃問題通?？捎梅种Χń绶ɑ蚋钇矫娣▉砬蠼狻＠? 投資方案問題假設(shè)某一個(gè)生產(chǎn)部門在一段時(shí)間內(nèi)可用于 投資的總金額為a億元，可

5、供選擇的工程總共有n個(gè)，分別記為1, 2,n。并且對(duì)第j個(gè)工程的投資總數(shù)為aj億元，而收益額總數(shù) 為Cj億元。問如何使用資金a億元，才能使單位投資獲得的收益最大。非線性規(guī)劃問題1,對(duì)第j個(gè)工程投資.數(shù)學(xué)模型：設(shè)Xj0,否那么,j 1, ,nnCjXj目標(biāo)函數(shù)：maXZj 1najXjj inajxj a約束條件：j 1Xj 0 或 1, j 1, n非線性規(guī)劃問題的求解方法很多，是本課的重點(diǎn)。動(dòng)態(tài)規(guī)劃是解決“多階段決策過程的最優(yōu)化問題的一種方法，基于“Bellman最優(yōu)性原理，例如：資源分配問題，生產(chǎn)與存儲(chǔ)問題。例4 (多參數(shù)曲線擬合問題)熱敏電阻R依賴于溫度T的函數(shù)關(guān)系為X2R x1eT X

6、3 *其中，Xi，x2,X3是待定的參數(shù)，通過實(shí)驗(yàn)測(cè)得 T和R的15組數(shù)據(jù)列表如下，如何確定參數(shù)Xi,X2,X3 ？i12345678T/c5055606570758085R/k34.7828.6123.6519.6316.3713.7211.549.744i9101112131415T/c9095100105110115120R/k8.2617.036.0055.1474.4273.823.307建立數(shù)學(xué)模型：測(cè)量點(diǎn)(Ti,Ri)與曲線R(T)對(duì)應(yīng)的點(diǎn)產(chǎn)生“偏差 即15亠S Rj X1eTi X32i 1得如下無約束最優(yōu)化問題：15X2min f(x) R X,eT X32i 1通常采用最小

7、二乘法。§ 1.2最優(yōu)化問題的數(shù)學(xué)模型最優(yōu)化問題的數(shù)學(xué)模型假設(shè)aibi(i1,2,m，那么記或；假設(shè)aibi(i1,2,m，那么記或。2.般模型：opt f (x)f (X1,X2,xn) (minf (x)或maxf (x),(1)1. 定義1：設(shè)向量 包，,amT,Qb， ,bmT .Si(x) 0, i 1, , m hj(x)0, j 1, ,l其中，x X1, X2,XnT ； f(x) , Si(x) , hj(x)是關(guān)于變量X1 , x2 , Xn的實(shí)值連續(xù)函數(shù)，一般可假定它們具有二階連續(xù)偏導(dǎo)數(shù)。3.向量模型:opt f (x) (minf(x) 或 maxf (x),

8、(1)S(x)C 4-0,(2)h(x)0,(3)其中，xX1,X2,XnT ,fx稱為目標(biāo)函數(shù)；S(x)S(X),Sm(x) h(x) h(x),hl(xV。有如下概念：Six , hjx稱為約束函數(shù)；滿足約束條件2, 3的點(diǎn)稱為容許解或容許點(diǎn)或可行解|; 容許解的全體稱為容許域或可行域，記為D或R;滿足1的容許點(diǎn)稱為最優(yōu)點(diǎn)或最優(yōu)解或極小大點(diǎn)，記為x* ； f(x)稱為最優(yōu)值；不帶約束的問題稱為無約束問題，帶約束的問題稱為約束問題；假設(shè)目標(biāo)函數(shù)f(x)，約束函數(shù)Si(x) , hj(x)都是線性函數(shù)，那么 稱為線性規(guī)劃；假設(shè)其中存在非線性函數(shù)，那么稱為非線性規(guī)劃；假設(shè)變量只取整數(shù)，稱為整數(shù)規(guī)

9、劃；假設(shè)變量只取0， 1，稱為0 1規(guī)劃。注：因h(x) 0 h(x) 0，-h(x)0，那么最優(yōu)化問題一般可寫成opt f (x)s.t. S(x) 0最優(yōu)化問題的分類無約束問題最優(yōu)化問題靜態(tài)規(guī)劃約束問題一維問題n維問題線性規(guī)劃非線性規(guī)劃動(dòng)態(tài)規(guī)劃§ 1.3二維問題的圖解法例 1. max z 2x1 3x2x1 2x28s.t.4x1 16x1, x20解：1.由全部約束條件作圖，求出可行域 R:凸多邊形OABC 2作出一條目標(biāo)函數(shù)的等值線：設(shè) 2X1 3X2 6，作該直線即 為一條目標(biāo)函數(shù)的等值線，并確定在可行域內(nèi)，這條等值線向哪個(gè)方 向平移可使z值增大。3.平移目標(biāo)函數(shù)等值線，

10、做圖求解最優(yōu)點(diǎn)，再算出最優(yōu)值。頂 點(diǎn)B4,2是最優(yōu)點(diǎn)，即最優(yōu)解x 4 2t，最優(yōu)值z(mì) 14。分析：線性規(guī)劃問題解的幾種情況1有唯一最優(yōu)解上例；2有無窮多組最優(yōu)解：目標(biāo)函數(shù)改為 max z 2石4x?3無可行解：增加約束X25，那么R 。4無有限最優(yōu)解無界解：例max z旨 化x1 2x24s.t.- x1 x2 2x1, x20結(jié)論：1線性規(guī)劃問題的可行域?yàn)橥辜厥馇闆r下為無界域 或空集。2線性規(guī)劃問題假設(shè)有最優(yōu)解，一定可在其可行域的頂點(diǎn)上 得到。例 2.min Xi 22 x2-12x1 x； 5x20s.t.x1 x2 5 0x, x20解：目標(biāo)函數(shù)等值線：Xi 22 X2-12 1x1

11、 x； 5x20TC為最優(yōu)點(diǎn)x x 50 ，得x 4 1定義2:在三維及三維以上的空間中，使目標(biāo)函數(shù)取同一常數(shù)的 點(diǎn)集xfx r, r是常數(shù)稱為等值面。§ 1.4預(yù)備知識(shí)線性代數(shù)一、 n維向量空間Rn1.向量的內(nèi)積：設(shè)xX1,X2, ,XnT, y%小，ynT，那么內(nèi)積為Tx yXX22XnynnXi yii 12.向量的范數(shù)或長(zhǎng)度或模：設(shè)x Rn，假設(shè)實(shí)數(shù)x具有以下性質(zhì)：1|x|0,當(dāng)且僅當(dāng)x 0時(shí)Ix 0 ；2I x| I x, R ；3I x y HI I y, x,y Rn. 那么稱|x|為Rn上的向量的范數(shù)，簡(jiǎn)記為III。規(guī)定了向量范數(shù)的線性空間Rn稱為線性賦范空間，記為R

12、 n|.3.常見的向量范數(shù)1n帀向量的Lp范數(shù)：|x|p人卩,1 pi 1三個(gè)重要的向量范數(shù)：I X1 ,|x|2 , I x|注：假設(shè)無特殊說明，本書中的11指的是IXI2。4. x, y間的距離：x y5. x與y正交：xTy 0假設(shè)非零向量組x，x(k)的向量?jī)蓛烧?，稱它們是正交向 量組。6.標(biāo)準(zhǔn)正交基：e(1)，e(n)是n個(gè)正交的單位向量，即e(i)T1, i j0, i j二、特征值和特征向量定義：設(shè)A為n階方陣，存在數(shù) 和非零向量x，使Ax x,那么稱 為矩陣A的特征值，非零向量x為矩陣A屬于特征值 的特 征向量。三、正定矩陣定義：設(shè)A為n階實(shí)對(duì)稱方陣，假設(shè)對(duì)任意非零向量 x，

13、均有 xTAx 0,那么稱xTAx為正定二次型，A為正定矩陣，記A 0 ；假設(shè) xTAx 0，半正定二次型，A為半正定矩陣，記A 0。類似有負(fù)定(半負(fù)定)二次型，負(fù)定(半負(fù)定)矩陣的概念性質(zhì)：實(shí)對(duì)稱方陣A為正定矩陣負(fù)A的特征值均為正負(fù)A的各階順序主子式均為正奇數(shù)階為負(fù)，偶數(shù)階為正實(shí)對(duì)稱方陣A為半正定矩陣A的特征值均非負(fù)A的各階順序主子式均為非負(fù)二數(shù)學(xué)分析、 梯度和海色Hesse矩陣1.多元函數(shù)的可微性可微定義：設(shè)f : D Rn R1，xo D，假設(shè)存在n維向量I，對(duì)p 0 Rn，總有l(wèi)im f(XoP)IN of (Xo)|Tplpllo(1)那么稱函數(shù)f X在點(diǎn)Xo處可微。式1等價(jià)于f (

14、Xo p) f (Xo) |T p 0pll(2)其中，0|p|是| p的高階無窮小。定理1：可微的必要條件假設(shè)函數(shù)f x在點(diǎn)X。處可微，那么f x在該點(diǎn)關(guān)于各個(gè)變量的偏導(dǎo)數(shù)存在，且T|fX。 fX。fX。I555XiX2Xn2.梯度(1)概念梯度：令f(x)f(x)Xif(x)X2f(x)Xn那么稱f (x)為n元函數(shù)f (x)在x處的梯度(或記為gradf(x)。又稱為f(x)關(guān)于x的一階導(dǎo)數(shù)。注：式(2)等價(jià)于f(X° p) f(x°)f(X°)Tp 0 | p(3)方向?qū)?shù)：設(shè)f：RnR1在點(diǎn)Xo處可微，向量p 0 Rn，e是p方向上的單位向量，那么極限l

15、im f(x0 te) f (X0)t 0f (X0)。p方向?qū)?shù)的幾何解釋：方向?qū)?shù)七應(yīng)表示函數(shù)f(x)在點(diǎn)X0處P稱為函數(shù)f (X)在點(diǎn)Xo處沿p方向的方向?qū)?shù)，記作沿方向的p的變化率。函數(shù)的下降(上升)方向：設(shè)f :RnR1是連續(xù)函數(shù)，點(diǎn)X0Rn，p 0R n為一方向，假設(shè)存在0，對(duì)于 t (0,)，都有f(X。tp)f(x°)( f(x°tp)f (X0)那么稱p方向是函數(shù)f (X)在點(diǎn)X。處的下降(上升)方向;結(jié)論1：假設(shè)方向?qū)?shù)0，那么方向p是f(x)在點(diǎn)X0處的Pf (x0)下降方向；假設(shè)方向?qū)?shù)一 °，那么方向p是f(x)在點(diǎn)X。處的上p升方向；(

16、2)性質(zhì)【性質(zhì)1】：梯度f(x°)為等值面f (x) f (x°)在點(diǎn)x°處的切平面的法矢(向)量?！拘再|(zhì)2】：梯度方向是函數(shù)具有最大變化率的方向。定理2：設(shè)f ：RnR1在點(diǎn)x°處可微，那么方向?qū)?shù)f(x°)Tef(x°)cosP其中，e是p方向上的單位向量，為梯度與P的夾角。結(jié)論2： 1)與梯度f(x°)方向成銳角的方向是上升方向；與梯 度f(x°)方向成鈍角的方向是下降方向；2)梯度方向是函數(shù)值上升最快的方向，稱為最速上升方向；負(fù) 梯度方向是函數(shù)值下降最快的方向，稱為最速下降方向。(3)幾種特殊函數(shù)的梯度公式

17、(1)C 0，C為常數(shù)；(2)(bTx)b，其中 bbib, ,bn T ；(3)(xTx) 2x ；(4)假設(shè)Q是對(duì)稱方陣，那么(xTQx) 2Qx例3.泰勒(Taylor)公式與Hesse矩陣性質(zhì)1:設(shè)f (x): Rn R具有一階連續(xù)偏導(dǎo)數(shù)，那么f(x p) f(x) f( )Tp(*)其中，X p (01，即介于X與Xp之間。性質(zhì)2:設(shè) f (X):RnR具有一階連續(xù)偏導(dǎo)數(shù)，那么f(X p)f(X)T1Tf(x) p - p2f( )p(* )其中2f(X)2f(x)2f(x)X12X1 x2X1 Xn2f(X)2f(x)2f(x)2f(X)X2 X1X；X2 Xn2f(X)2f(x)

18、2f(x)Xn X1Xn X2Xn為函數(shù)f X關(guān)于X的二階導(dǎo)數(shù),稱為f x的海色HessH矩陣。結(jié)論1:當(dāng) f(X)c2 即二階偏導(dǎo)數(shù)連續(xù)時(shí)，有2f(X)N Xj2f(X) iXj Nj 1，n 即海色矩陣對(duì)稱注1：i設(shè)向量函數(shù)gXg1(x),g2(x),gm(x)T 時(shí)，gOg2(x)gm(x)X1X1X1gdx)g2xgm(x)g(X)X2X2X2gOg2xgm(x)XnXnXn稱為向量函數(shù)gx在點(diǎn)X處的導(dǎo)數(shù)梯度。2向量函數(shù)gx gix, g2x, gmXT在點(diǎn)X。處可微是指所有分量都在點(diǎn)X。處可微。關(guān)于向量函數(shù)常見的梯度:1COn，C Rn ；2(X)In，X Rn ；3(Ax)AT,

19、a Rmn4設(shè)f (Xo tp)，其中 f : RnR1，: R1R1，那么(t)f (Xo tp)Tp，(t) pT2f (Xo tp) p例:(三) 極小點(diǎn)的判定條件(求 min f(x)、 根本概念1點(diǎn) X0 的鄰域：N(Xo，) X X Xo,02. 局部極小點(diǎn)：設(shè)f : D RnR1.假設(shè)存在點(diǎn)x* D和數(shù)0，對(duì) x N(x*, ) D 都有 f(X) f(X*)，那么稱 x*為 f(X) 在D上的(非嚴(yán)格)局部極小點(diǎn)；假設(shè)f (x) f (x*)( x x*)，那么稱 x*為f(x)在D上的嚴(yán)格局部極小點(diǎn)。3. 全局極小點(diǎn)：設(shè)f : D Rn R1.假設(shè)存在點(diǎn)x* D，對(duì)于x D都

20、有f (x) f (x*)，那么稱x*為f (x)在D上的(非嚴(yán)格) 全局極小點(diǎn)；假設(shè)f (x) f (x*) ( x x*)，那么稱x*為f (x)在D上的 嚴(yán)格全局極小點(diǎn)。性質(zhì)：全局極小點(diǎn)必是局部極小點(diǎn)；但局部極小點(diǎn)不一定是全局 極小點(diǎn)。類似有極大點(diǎn)的概念。因maxf(x) min f (x)，本書主要給 出極小問題。4. 駐點(diǎn)：設(shè) f : D Rn R1 可微，x* D，假設(shè) f(x*) 0， 那么稱點(diǎn)X*為f(x)的駐點(diǎn)或臨界點(diǎn)。二、極值的條件定理1 (一階必要條件)設(shè)f ： D RnR1具有一階連續(xù)偏導(dǎo)數(shù)，x*是D的內(nèi)點(diǎn)，假設(shè)x*是f(x)的局部極小點(diǎn)，那么f(x*) o定理2 (二

21、階必要條件)設(shè)f ： D RnR1具有二階連續(xù)偏導(dǎo)數(shù)，假設(shè)X是D的內(nèi)點(diǎn)且為f (x)的局部極小點(diǎn)，那么2 f(X )是半正定 的，即對(duì) p Rn恒有PT 2f(X*)P 0例定理3 (二階充分條件)設(shè)f ： D RnR1具有二階連續(xù)偏導(dǎo)*a*數(shù)，x為D的內(nèi)點(diǎn)，且f (x )0，假設(shè) f (x )正定，那么x為f (x)的嚴(yán)格局部極小點(diǎn)。定理4 (二階充分條件)設(shè)f ： RnR1具有二階連續(xù)偏導(dǎo)數(shù)，*c*x R且f(X )0，假設(shè)存在x的 鄰域N (x ,)使對(duì)X N(X ,)，都有2f (x)半正定，那么x為f(x)的局部極小點(diǎn)。(四) 凸函數(shù)與凸規(guī)劃一、凸集1. 凸集的定義：一個(gè)n維向量空間

22、的點(diǎn)集D中任意兩點(diǎn)的連線 仍屬于這個(gè)集合，即對(duì)人公？ D，有X (1)X2 D (01)那么稱該點(diǎn)集D為凸集。2. 凸集的性質(zhì)：(1)凸集的交集仍是凸集(Di D2)；(2) 數(shù)乘凸集仍是凸集D yy x, x D；(3) 凸集的和集仍是凸集D1 D2 yy x z, x Dz D? 特別規(guī)定，空集是凸集。3.超平面：設(shè) Rn且 0, b R，那么集合TnnH x x b, x R 稱為Rn中的超平面，稱為該超平面的法向量，即H : a/ a?X2anXn b ；(是凸集)半空間：集合x Tx b, x Rn稱為Rn中的一個(gè)半空間。超球：IXI r。4. 凸組合：設(shè)xX2，必為Rn中的I個(gè)點(diǎn)，

23、假設(shè)存在dQ,41且0 q 1ai 1，使得i 1x a1x1 a2x2alxl那么稱x為Xi,X2, ,X|的凸組合。假設(shè)ai,a2, ,a|均為正，那么稱為嚴(yán)格凸組合。5. 頂點(diǎn)(或極點(diǎn))：設(shè)D是凸集，x D，假設(shè)x不能用D內(nèi)不同兩點(diǎn)X1和X2的凸組合表示，即X X1 (1 )X2 (01)，那么稱x為D的頂點(diǎn)。二、凸函數(shù)1.凸函數(shù)：設(shè)f : D RnR1，D是凸集，假設(shè)對(duì) X1,X2 D及 0, 1，都有f( X1 (1)X2)f(Xj (1 川區(qū))那么稱f(x)為凸集D上的凸函數(shù)；假設(shè)f( X1 (1 )X2)f(xj (1)f(X2)(01)那么稱f(x)為凸集D上的嚴(yán)格凸函數(shù)。類似

24、有凹函數(shù)的定義。2幾何意義：函數(shù)圖形上連接任意兩點(diǎn)的線段處處都在函數(shù)圖形 的上方。3性質(zhì)性質(zhì)1： f(x)為凸集D上的凸函數(shù)，k 0，那么kf(x)也為D上 的凸函數(shù)。性質(zhì)2：兩個(gè)凸函數(shù)的和仍是凸函數(shù)。(fi(x) f2(x)推論1：凸集D上有限個(gè)凸函數(shù)fi(x)的非負(fù)線性組合ki fi(x)kmfm(x), ki 0仍為D上的凸函數(shù)。性質(zhì)3：假設(shè)f(x)為凸集D上的凸函數(shù)，那么對(duì)R，f(x)的水平集D xf (x), x D是凸集。性質(zhì)4： f(x)為凸集D上的凹函數(shù)f(x)為凸集D上的凸函數(shù)。4. 凸函數(shù)的充分必要條件定理1 (一階條件)設(shè)f ：D RnR1可微，D是凸集，那么(1) f

25、(x)為凸函數(shù)對(duì)Xi,X2 D，恒有f(X2) f(xjf (XjT(X2-X1)(2) f (x)為嚴(yán)格凸函數(shù)對(duì)X1,X2 D，X1 X2恒有f(X2) f (X1)f (XjT(X2-X1)定理2 (二階條件)設(shè)f ： D RnR1具有二階連續(xù)偏導(dǎo)數(shù)，D為開凸集，那么(1)f (x)在D內(nèi)為凸函數(shù) 對(duì)x D，2f (x)是半正定的；(2)假設(shè)2f(x)正定，那么f(x)在D內(nèi)為嚴(yán)格凸函數(shù)。1特殊地，n元二次函數(shù)為f (x)-xTQx bTx C ( Q為對(duì)稱矩陣)；假設(shè)Q正定，那么f (x)稱為正定二次函數(shù)。性質(zhì)：正定二次函數(shù)是嚴(yán)格凸函數(shù)。(因?yàn)?f (x) Q)5. 凸函數(shù)的極值凸規(guī)劃問

26、題：非空凸集D上的凸函數(shù)的極小化問題。定理3設(shè)f :D Rn R1為凸集D上的凸函數(shù)，貝S(1) f (x)的任一局部極小點(diǎn)x*為全局極小點(diǎn)； " 、 * * *(2) 假設(shè)f (x)可微，且存在x D，使f(x )0，那么x為f (x)在D上的全局極小點(diǎn)；(3) 假設(shè)f(x)為嚴(yán)格凸函數(shù)，且全局極小點(diǎn)存在，那么必唯一。考慮如下特殊的凸規(guī)劃問題：1(1) 對(duì)于正定二次函數(shù)f (x) -xTQx bTx C，有* 1f (x) Qx b，得唯一駐點(diǎn)x Q b為唯一的全局極小點(diǎn)。(2) 考慮凸規(guī)劃問題：minf(x) , x Rn(1)Si(x) 0, i 1, ,m(2)st hj(x

27、) 0, j 1, ,l其中，S (x)為Rn上的凹函數(shù)，hj (x)為Rn上的線性函數(shù)，D x0(x)0, hj (x)0,i1, ,m;j 1,1為凸集，f:D Rn R1為D上的凸函數(shù)。注：線性函數(shù)既可視為凸函數(shù)，又可視為凹函數(shù)。13二次規(guī)劃:minf( x)xtQx bTx C2Ax ps.t.Cx d其中，X Rn , Am n , Cl n , Q半正定或正定。注：關(guān)于凸函數(shù)的極值的性質(zhì)即定理 3即是凸規(guī)劃問題的性 質(zhì)五下降迭代算法1. 下降迭代算法的步驟1選擇一個(gè)初始點(diǎn)Xo，令k： =02檢驗(yàn)xk是否最優(yōu)？假設(shè)是，那么停止迭代；假設(shè)不是，那么3 確定一個(gè)下降方向Pk :存在0，對(duì)

28、t 0,，使得f Xk tPkf Xk4 從點(diǎn)Xk出發(fā)，沿方向Pk進(jìn)行直線搜索一維搜索，即求 步長(zhǎng)tk使f Xk tkPkmin f Xk tPk5 計(jì)算 Xk 1 Xk tkPk，令 k： =k+1，轉(zhuǎn)22. 直線搜索及其性質(zhì)1簡(jiǎn)記z ls(x, p)f x t0pmin f x tpz x toP表示從點(diǎn)x出發(fā)，沿方向p進(jìn)行直線搜索，得到極小點(diǎn)z。(2)定理：設(shè)目標(biāo)函數(shù)f(x)具有一階連續(xù)偏導(dǎo)數(shù)，假設(shè) z ls(x, p)，那么f(z)Tp o證明：(反正法)設(shè) f (z)Tp 0，貝y1) f (z)T p 0，此時(shí) p是點(diǎn)z的下降方向；2) f (z)T p 0，此時(shí)p是點(diǎn)z的下降方向

29、；與z ls(x, p)矛盾。3收斂速度定義1 :設(shè)序列3訃是線性賦范空間Rn,|中的點(diǎn)列， x* Rn，假設(shè)lim xk x*0k11那么稱序列Xk收斂于x*，記為lim x x*。k定義 2 :設(shè)向量函數(shù) f (x)fi(X), f2(X), , fm(x) T ,x D Rn，假設(shè)當(dāng)x Xo 0時(shí)，總有f (x) f(x°) 0，那么稱 f (x)在點(diǎn)x0連續(xù)；假設(shè)f (x)在D內(nèi)每一點(diǎn)都連續(xù)，那么稱f (x)在D內(nèi) 連續(xù)。特別地，m=1時(shí)，f(x)為數(shù)量函數(shù)，那么I f(x) f(x°)|f (x) f(x。)定義3:設(shè)序列乂訃收斂于x* ,假設(shè)存在與k無關(guān)的數(shù)(1

30、)和(0)，使得當(dāng)k從某個(gè)ko( 0)開始，都有Xk X*那么稱序列Xk收斂的階為，或Xk為 階收斂。當(dāng) 1，且01時(shí)，稱線性收斂或一階收斂;當(dāng) 2時(shí)，稱二階收斂；當(dāng)12時(shí)，稱超線性收斂。4.計(jì)算終止準(zhǔn)那么計(jì)算終止準(zhǔn)那么根據(jù)相繼兩次迭代的結(jié)果Xk 1Xkll1，f (Xk 1)f (Xk)b.根據(jù)相繼兩次迭代的相對(duì)誤差Xk 1xkllf (Xk 1)f (Xk)llXkl13，f (Xk)1a.根據(jù)相繼兩次迭代的絕對(duì)誤差(不常用)24根據(jù)目標(biāo)函數(shù)梯度的模足夠小C.f (Xk)5為給定的足夠小的正數(shù)。以上準(zhǔn)那么統(tǒng)稱為Himmelblau計(jì)算終止準(zhǔn)那么，簡(jiǎn)稱H終止準(zhǔn)那么1.繁寫形式：minzc1x

31、1 c2x2cnxna11x1a12 x2a1n xnb1a21x1a22 x2a2nxnb2s.t.amn xnbamx1am2 x2x1,x2,xn 0其中，bi 0, i1,2,m否那么，等式兩端同乘以“2.縮寫形式：minzncjxjj1naij x j bi,i1,2, ,ms.t.j1xj0, j 1,2,n3.向量形式：minzCTX、線性規(guī)劃的標(biāo)準(zhǔn)型mnpj xj b-1。第二章線性規(guī)劃2.1數(shù)學(xué)模型s.t.j1X其中，C c1,c2,cnT， X x1,x2,xnT，b b1,b2, ,bmT ，pja1j,a2j , ,amj 。4. 矩陣形式： minzCTXAX s.t

32、. X其中，a11 a12a21amnp1,p2, ,am1 am2A :約束條件的m n系數(shù)矩陣，m 0 , n 0 ,pn般地， m n ；b ：限定向量，一般地， bi 0, i 1,2, ,m ；C :價(jià)值向量；X :決策向量， X 0 ；通常A, b , C為，X未知二、任一模型化為標(biāo)準(zhǔn)型1. 極大化目標(biāo)函數(shù): max z CTX令 z z ，那么問題轉(zhuǎn)化為 min z CT X2. 約束條件為不等式假設(shè)約束為“ 型，那么“左端 +松弛變量 =右端 如: ai1x1 ai2x2ainxn bi ，引入松弛變量 xnai1x1ai2x2ain xnxn i假設(shè)約束為“ 型，那么“左端

33、-剩余變量 =右端如: ai1x1ai2x2ainxnbi ，引入剩余變量 xn松弛變量 0)0 ，化為bi剩余變量 0)i 0 ，化為ai1x1ai2 x2ain xnxn ibi3. 假設(shè)存在無非負(fù)要求的變量 xk (稱為自由變量)令 xk xk xk ，其中 xk 0 ， xk 0 ， 代入目標(biāo)函數(shù)及約束條 件即可。4. 某變量 xj 有上、下界假設(shè) xj u j ，即 xj uj°，令 XjXj Uj，有 Xj0。用 Xj uj代替 xj 即可。假設(shè) xj t j 代替 xj 即可。例：，即 tj xj0，令 Xjt jXj ，有 Xj0 。用 t j Xj§ 2.

34、2線性規(guī)劃解的性質(zhì)、根本概念標(biāo)準(zhǔn)型LP:minzCTX1AXb2s tX03可行解容許解：滿足約束2、3的解。最優(yōu)解：滿足1的容許解?；涸O(shè)Am n的秩為m，假設(shè)B是A中的m m階可逆矩陣，稱B是線性規(guī)劃問題LP的一個(gè)基。假設(shè)基B是單位矩陣稱為標(biāo)準(zhǔn)基。基向量：基B中的一列Pi即為一個(gè)基向量。共m個(gè)非基向量：基B之外的一列Pj即為一個(gè)非基向量。共n m個(gè)基變量：與基向量 Pi相應(yīng)的變量K。共m個(gè)非基變量：與非基向量Pj相應(yīng)的變量Xj。共n m個(gè)根本解：令所有非基變量為0,求出的滿足約束2的解。根本容許解：滿足約束3的根本解。最優(yōu)根本容許解：滿足約束1的根本容許解。容許基：假設(shè)B是基，且存在關(guān)于B

35、的根本容許解，稱B是容許基。假設(shè)容許基B是單位矩陣稱為標(biāo)準(zhǔn)容許基。非容許基： 退化的根本解：假設(shè)根本解中有基變量為 0的根本解退化的根本容許解：退化的最優(yōu)根本容許解:二、線性規(guī)劃問題的根本定理定理1假設(shè)線性規(guī)劃問題存在容許域，那么其容許域是凸集也是 凸多面體有限個(gè)半空間的交集稱為凸多面體；有界的凸多面體稱 為凸多胞形。定理2線性規(guī)劃問題的根本容許解對(duì)應(yīng)于容許域的頂點(diǎn)。定理3假設(shè)線性規(guī)劃問題存在有限最優(yōu)解，那么其目標(biāo)函數(shù)最優(yōu)值 一定可以在容許域的頂點(diǎn)到達(dá)。2.3 單純形法一、單純形法原理單純形法的根本思路： 根據(jù)問題的標(biāo)準(zhǔn)型， 沉著許域的一個(gè)根本 容許解一個(gè)頂點(diǎn)開始，轉(zhuǎn)移到另一個(gè)根本容許解相鄰頂

36、點(diǎn) ， 并且使目標(biāo)函數(shù)值逐步下降； 當(dāng)目標(biāo)函數(shù)到達(dá)最小值時(shí)， 問題就得到 了最優(yōu)解。二、單純形法的步驟以“大 M 法為例數(shù)學(xué)描述例大 M 法： min z 4x1 3x2 8x3x1 x3 2s.t. x2 2x3 5xj 0 j 1,2,31. 構(gòu)造初始容許基初始容許基是一個(gè) m m 單位矩陣，它相應(yīng)的根本解是容許的， 即標(biāo)準(zhǔn)容許基。1o 引入附加變量，把數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。2o 假設(shè)約束條件中附加變量系數(shù)為“ -1，或原約束即為等式，那么 一般須引入人工變量。3o 目標(biāo)函數(shù)中，附加變量系數(shù)為 0，而人工變量系數(shù)為 M 很 大的正數(shù)。人工變量系數(shù)為大 M ：只要人工變量 >0，使前后約

37、束條件不等 價(jià)，但由于目標(biāo)函數(shù)的修改， 同時(shí)也使所求的目標(biāo)函數(shù)最小值是一個(gè)很大的數(shù)，也是對(duì)“篡改約束條件的一種懲罰，因此， M 叫做罰 因子，大 M 法也叫做罰函數(shù)法。假設(shè)對(duì)極大化問題，目標(biāo)函數(shù)中人工變量系數(shù)為-M)。得到如下標(biāo)準(zhǔn)型：min zcjXjj1X1a1,m 1Xm 1a1nXnX2a2,m 1Xm 1a2nXnXmam,m 1Xm 1amnXnXj0 (j 1,2,n),m) 表示基變量；Xj ( j mns.t.bm其中，Xi(i 1,2,1, ,n) 表示非基變b1b2量。2. 求出一個(gè)根本容許解1o 用非基變量表示基變量和目標(biāo)函數(shù)。用非基變量表示基變量，即有Xi bijnaX

38、ij jm1(i1, ,m)用非基變量表示目標(biāo)函數(shù)，即nzck Xkk1mmciXi i1ncjXjm1i1cibi(cjm1jmci aij )Xji1z0(cjzj )Xjj m 1n z0j Xjj m 1其中，zoch ,而j Cj Zj稱為非基變量Xj的檢驗(yàn)數(shù)。上式i1中，規(guī)定各基變量的檢驗(yàn)數(shù)為 0。mZjciaijc1a1jc2a2 jcmamji1c1,a1j,cmc1, ,cmpjamj假設(shè)干次迭代cB1,cBmpjCB pj其中， CB 是基變量的價(jià)值系數(shù)，隨基的改變而改變。2o求出一個(gè)根本容許解及相應(yīng)的目標(biāo)函數(shù)值。令非基變量 =0 即得初始根本容許解：xi bi (i 1, ,m)， xj 0 ( j m 1, ,n) 初始目標(biāo)函數(shù)值： Z Z03. 最優(yōu)性檢驗(yàn)1o檢驗(yàn)數(shù)j ：目標(biāo)函數(shù)式中，各非基變量的系數(shù)，即稱為各非 基變量的檢驗(yàn)數(shù)。2o 最優(yōu)解判別定理： 假設(shè)在極小化問題中， 對(duì)于某個(gè)根本容許解， 所有檢驗(yàn)數(shù) j 0 ，且人工變量為 0，那么該根本容許解是最優(yōu)解。3o 無窮多最優(yōu)解判別定理：假設(shè)在極小化問題中，對(duì)于某個(gè)根本 容許解，所有檢驗(yàn)數(shù) j 0 ，又存在某個(gè)非基變量的檢驗(yàn)數(shù)為 0， 且人工變量為 0，那么該線性規(guī)劃問題有無窮多最優(yōu)解。4o 無容許解判別定理：假設(shè)在極小化問題中，對(duì)于某個(gè)根本容許解，所有檢驗(yàn)數(shù)j 0，但人工