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

1、第一章最優(yōu)化問題與數(shù)學(xué)預(yù)備知識最優(yōu)化分支：線性規(guī)劃，整數(shù)規(guī)劃，幾何規(guī)劃，非線性規(guī)劃，動(dòng) 態(tài)規(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維空間上的可微函數(shù)。解法求極值點(diǎn)：求駐點(diǎn)，即滿足彳

2、治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ù)合同規(guī)定，產(chǎn)品Aj的量不少于dj，再 設(shè)Aj

3、的單價(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 為簡便起見， 假設(shè)生產(chǎn)同一種產(chǎn)品，第i個(gè)工廠的建設(shè)費(fèi)用fj 1,2, ,m。又 有n個(gè)零售商店銷售這種產(chǎn)品，對這種產(chǎn)品的需求量分別為 bb2 ,bn，從第i個(gè)工廠運(yùn)送一個(gè)單位產(chǎn)品到第j個(gè)零售商店的運(yùn) 費(fèi)為q。試

4、決定應(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ī)劃問題通常可用分枝定界法或割平面法來求解。例3 投資方案問題假設(shè)某一個(gè)生產(chǎn)部門在一段時(shí)間內(nèi)可用于 投資的總金額為a億元，可供選擇的工程總共有n個(gè)，分別記為1, 2,

5、n。并且對第j個(gè)工程的投資總數(shù)為aj億元，而收益額總數(shù) 為Cj億元。問如何使用資金a億元，才能使單位投資獲得的收益最大。非線性規(guī)劃問題1,對第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)與存儲問題。例4 (多參數(shù)曲線擬合問題)熱敏電阻R依賴于溫度T的函數(shù)關(guān)系為X2R x1eT X3 *其中，Xi，x2,X3是待定的參數(shù)，

6、通過實(shí)驗(yàn)測得 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é)模型：測量點(diǎn)(Ti,Ri)與曲線R(T)對應(yīng)的點(diǎn)產(chǎn)生“偏差 即15亠S Rj X1eTi X32i 1得如下無約束最優(yōu)化問題：15X2min f(x) R X,eT X32i 1通常采用最小二乘法。§ 1.2最優(yōu)化問題的數(shù)

7、學(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) (min f (x)或 maxf (x) ,(1)S(x) 0, i 1, ,

8、m(2)S.t. h(x) 0, j 1, ,l(3)其中，X X1,X2, ,XnT , f (x)稱為目標(biāo)函數(shù)；Si(x) , hj(x)稱為約束函數(shù)；滿足約束條件(2), ( 3)的點(diǎn)稱為容許解或容許點(diǎn)(或可行解)；容許解的全體稱為容許域(或可行域)，記為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ī)劃；假設(shè)變量只取0， 1

9、，稱為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:凸多邊形OABC2. 作出一條目標(biāo)函數(shù)的等值線：設(shè) 2X1 3X2 6，作該直線即 為一條目標(biāo)函數(shù)的等值線，并確定在可行域內(nèi)，這條等值線向哪個(gè)方 向平移可使z值增大。3. 平移目標(biāo)函數(shù)等值線，做圖求解最優(yōu)點(diǎn)，再算

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

11、； 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ù)一、 n維向量空間Rn1.向量的內(nèi)積：設(shè)xx1,x2, ,XnT, y%小，ynT,那么內(nèi)積為Tx yxX22Xnynni 12.向量的范數(shù)或長度或模：設(shè)x Rn，假設(shè)實(shí)數(shù)x具有以下性質(zhì)：1|x|0,當(dāng)且僅當(dāng)x 0時(shí)|0 ； I x| I x, R ；3 IIx y ix |y, x, y Rn.那么稱I|x|為Rn上的向量的范數(shù)，簡記為III。規(guī)定了向量范數(shù)的線性空間Rn稱為線性賦范空間，記為R n ,| |.

12、3. 常見的向量范數(shù)1n"p向量的Lp范數(shù)：|x|pxi， 1 pi 1三個(gè)重要的向量范數(shù)：|x|L , |x|2，I x|注：假設(shè)無特殊說明，本書中的IIII指的是IIx|2。4. x,y間的距離：x y5. x與y正交：xTy 0假設(shè)非零向量組x，xk的向量兩兩正交，稱它們是正交向量組6. 標(biāo)準(zhǔn)正交基：e，en是n個(gè)正交的單位向量，即eiTe1, i j0, i j二、特征值和特征向量定義：設(shè)A為n階方陣，存在數(shù) 和非零向量x，使Ax x，那么稱 為矩陣A的特征值，非零向量x為矩陣A屬于特征值 的特 征向量。三、正定矩陣定義：設(shè)A為n階實(shí)對稱方陣，假設(shè)對任意非零向量x，均有xT

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

14、f(Xo) |T p 0pll2其中，0|p|是| p的高階無窮小。定理1：可微的必要條件假設(shè)函數(shù)f x在點(diǎn)X。處可微，那么f x在該點(diǎn)關(guān)于各個(gè)變量的偏導(dǎo)數(shù)存在，且T|f (Xo) f (Xo)f (Xo)XnfffX1 X22.梯度1概念梯度：令f(x)f(x), f(x),Tf(x)X1x2Xn那么稱f x為n元函數(shù)fx在X處的梯度或記為gradfx。又稱為fx關(guān)于X的一階導(dǎo)數(shù)。注：式(2)等價(jià)于f(x° p) f(x°)f(x°)Tp 0 | p(3)等值面：在三維和三維以上的空間中，使目標(biāo)函數(shù)取同一數(shù)值的點(diǎn)集x f (x) r,r R稱為等值面(曲面)。方

15、向?qū)?shù)：設(shè)f ：RnR1在點(diǎn)xo處可微，向量p 0 Rn，e是P方向上的單位向量，那么極限lim f(x° te) f(x°)t 0稱為函數(shù)f(x)在點(diǎn)x0處沿p方向的方向?qū)?shù)，記作f(x0)方向?qū)?shù)的幾何解釋：方向?qū)?shù)表示函數(shù)f(x)在點(diǎn)x0處P沿方向的p的變化率。函數(shù)的下降(上升)方向：設(shè)f :RnR1是連續(xù)函數(shù)，點(diǎn)x0Rn， p 0Rn為一方向，假設(shè)存在0，對于 t (0,)，都有f(X。tp)f(x°)( f(x°tp)f (X°)那么稱p方向是函數(shù)f (x)在點(diǎn)X。處的下降(上升)方向;f (x0)結(jié)論1：假設(shè)方向?qū)?shù) p0，那么方向

16、p是f (x)在點(diǎn)Xo處的f (x0) c下降方向；假設(shè)方向?qū)?shù) p 0，那么方向p是f (x)在點(diǎn)Xo處的上升方向;(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ù)梯度方

17、向是函數(shù)值下降最快的方向，稱為最速下降方向。(3)幾種特殊函數(shù)的梯度公式(1)C 0，C為常數(shù)；(2)(bTx)b，其中bbib, ,bn T ；(3)(xTx)2x ；(4)假設(shè)Q是對稱方陣，那么(xtQx) 2Qx3.泰勒(Taylor)公式與Hesse矩陣性質(zhì)1：設(shè)f (x): Rnf(xR具有一階連續(xù)偏導(dǎo)數(shù)，那么p) f(x) f( )Tp(*)其中，x p (01)，即介于x與x p之間。性質(zhì)2:設(shè)f (x): RnR具有二階連續(xù)偏導(dǎo)數(shù)，那么f(x p)f(x)f(x)Tp1 T 2 f-p f( )p2(* )其中2f(x)2f(x)2f(x)X：x1 x2X1 Xn2f(x)2f

18、(x)2f(x)2f(x)x2 x1X；X2 Xn2f(x)2f(x)2f(x)Xn人Xn X22Xn為函數(shù)f (x)關(guān)于x的二階導(dǎo)數(shù),稱為f (x)的海色(HessH矩陣。2f(x)2f (x)結(jié)論1:當(dāng)f (x)C2時(shí)，,i,j 1,n (即xi xjXj Xi海色矩陣對稱)。注 1:1)設(shè)向量函數(shù) g(x) gi(x), g2(x), gm(X)T 時(shí),gOg2(x)gm(x)X1X1X1gOg2(x)gm(x)X2X2X2gOg2(x)gm(x)XnXnXng(x)稱為向量函數(shù)g(x)在點(diǎn)x處的導(dǎo)數(shù)(梯度)。2)向量函數(shù)g(x) 9(x), g2(x), ,gm(x)T在點(diǎn)x°

19、;處可微是指所有分量都在點(diǎn)xo處可微。關(guān)于向量函數(shù)常見的梯度:(1)COn, CRn ；(2)(X)In , X Rn ；(3)(Ax)AT, A Rm n(4)設(shè)f (Xo tp)，其中 f : RnR1 ,: R1 R1,那么(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，對 x N(x*, ) D 都有 f(X) f(X*)，那么稱 x*為 f(X) 在D上的(非嚴(yán)格)局部極小點(diǎn)；假設(shè)f (

20、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，對于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)。性質(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)。二

21、、極值的條件定理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 (二階必要條件)設(shè)f ： D RnR1具有二階連續(xù)偏導(dǎo)數(shù)，假設(shè)X是D的內(nèi)點(diǎn)且為f (x)的局部極小點(diǎn)，那么2 f(X )是半正定 的，即對 p Rn恒有PT 2f(X*)P 0例定理3(二階充分條件)設(shè)f ： D RnR1具有二階連續(xù)偏導(dǎo)數(shù)，*a*x為D的內(nèi)點(diǎn)，且f (x )0，假設(shè) f (x )正定，貝S x為f (x)的嚴(yán)格局部極小點(diǎn)。(四) 凸函數(shù)與凸規(guī)劃一、凸集1. 凸集的定義：一個(gè)n維向量空間的點(diǎn)集D中任意兩點(diǎn)的連線 仍屬于這個(gè)集合，

22、即對各公？ D，有為(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，那么集合H x Tx b, x Rn稱為Rn中的超平面，稱為該超平面的法向量，即H : a/ a?X2anXn b ；(是凸集)半空間：集合x Tx b, x Rn稱為Rn中的一個(gè)半空間。超球：x r。4. 凸組合：設(shè)Xi，X2， ,X1為Rn中的|個(gè)點(diǎn)，假設(shè)存在ai，a2， ,qi且°

23、 q 1, ai 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 (°1)，那么稱x為D的頂點(diǎn)。二、凸函數(shù)1.凸函數(shù)：設(shè)f : DRnR1，D是凸集，假設(shè)對 ,X2 D及 °, 1，都有f( X1 (1)X2)f(N)(1)f(X2)那么稱f (X)為凸集D上的凸函數(shù)；假設(shè)f( X1 (1)X2)f(X1)(1)f(X2)(°1)那么稱f(x)為凸集D上的嚴(yán)格凸函

24、數(shù)。類似有凹函數(shù)的定義。2幾何意義：函數(shù)圖形上連接任意兩點(diǎn)的線段處處都在函數(shù)圖形 的上方。3性質(zhì)性質(zhì)1： f (x)為凸集D上的凸函數(shù)，k °，那么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ù)，那么對R，f(x)的水平集D xf (x), x D是凸集。性質(zhì)4： f(x)為凸集D上的凹函數(shù)f(x)為凸集D上的凸函數(shù)。4. 凸函數(shù)的充分必要條件定理1 (一階條件)設(shè)f ：D Rn R1可微，D是

25、凸集，那么(1) f (x)為凸函數(shù)對Xi,X2 D，恒有f(X2) f(Xi)f (Xi)T(X2-Xi)(2) f (X)為嚴(yán)格凸函數(shù)對Xi,X2 D，Xi X2恒有f(X2) f (Xi)f (Xi)T(X2-Xi)定理2 (二階條件)設(shè)f ： D RnR1具有二階連續(xù)偏導(dǎo)數(shù)，D為開凸集，那么(1) f (x)在D內(nèi)為凸函數(shù) 對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為對稱矩陣)；假設(shè)Q正定，那么f(x)稱為正定二次函數(shù)。性質(zhì)：正定二次函數(shù)是嚴(yán)格凸函數(shù)。(因?yàn)?f(x)

26、 Q )5. 凸函數(shù)的極值定理3設(shè)f : D Rn R1為凸集D上的凸函數(shù)，貝S(1) f (x)的任一局部極小點(diǎn)x*為全局極小點(diǎn)；(2) 假設(shè)f(x)具有二階連續(xù)偏導(dǎo)數(shù)，且存在x* D，使f (x )0，那么x為f (x)在D上的全局極小點(diǎn)；(3) 假設(shè)f(x)為嚴(yán)格凸函數(shù)，且全局極小點(diǎn)存在，那么必唯一。特殊：對于正定二次函數(shù)f(X) Qx Jx C,有*4f (x) Qx b，得唯一駐點(diǎn)x Q b為唯一的全局極小點(diǎn)。6. 凸規(guī)劃問題：非空凸集D上的凸函數(shù)的極小化問題?？紤]凸規(guī)劃問題：minf(x) , x Rn(1)Si(x)0, i1,mst hj(x)0, j1,l其中，S (x)為R

27、n上的凹函數(shù)，hj (x)為Rn上的線性函數(shù),D xSi(x) 0, hj (x) 0,i 1, ,m;j 1, ,1為凸集, f : D Rn R1為D上的凸函數(shù)。注：線性函數(shù)既可視為凸函數(shù)，又可視為凹函數(shù)。二次規(guī)劃：1minf (x)xTQx bTx CAx ps.t. Cx d其中，x Rn , Am n , Cl n , Q半正定或正定(五) 下降迭代算法1. 下降迭代算法的步驟(1) 選擇一個(gè)初始點(diǎn)X。，令k： =0(2) 檢驗(yàn)xk是否最優(yōu)？假設(shè)是，那么停止迭代；假設(shè)不是，那么(3) 確定一個(gè)下降方向Pk :存在0，對t (0,)，使得f Xk tPkf Xk(4) 從點(diǎn)xk出發(fā)，沿

28、方向Pk進(jìn)行直線搜索(一維搜索)，即求 步長tk使f Xk tkPkmin f Xk tPk(5) 計(jì)算 Xk i Xk tk Pk，令 k： =k+1，轉(zhuǎn)(2)2. 直線搜索及其性質(zhì)(1) 簡記z ls(x, P)f x t0 pmin f x tPz x t°p表示從點(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 0證明：(反正法)設(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的下降方向；與z ls(x, P)

29、矛盾。3收斂速度中的點(diǎn)列,定義1 :設(shè)序列3訃是線性賦范空間Rx*Rn，假設(shè)lim Xuk你那么稱序列Xk收斂于x*，記為lim Xkx*。k定義 2 :設(shè)向量函數(shù) f(x)fi(x), f2(x), fm(X)T，0，那么稱x DRn，假設(shè)當(dāng) x Xo0 時(shí)，總有 f (x)f (Xo) f(X)在點(diǎn)Xo連續(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 (Xo) f (x) f (Xo)定義3:設(shè)序列Xk收斂于X*，假設(shè)存在與k無關(guān)的數(shù)(1)和(0)，使得當(dāng)k從某個(gè)ko( 0)開始，都有xkXk 1那么稱序列xk收斂

30、的階為，或xk為 階收斂。當(dāng) 1，且O 1時(shí)，稱線性收斂或一階收斂；當(dāng) 2時(shí)，稱二階收斂；當(dāng)12時(shí)，稱超線性收斂。4.計(jì)算終止準(zhǔn)那么計(jì)算終止準(zhǔn)那么根據(jù)相繼兩次迭代的結(jié)果a. 根據(jù)相繼兩次迭代的絕對誤差(不常用)Xk 1Xk1 , f (Xk 1) f (Xk)b. 根據(jù)相繼兩次迭代的相對誤差Xk1Xk|f (Xk 1)f (Xk)閱13，f (Xk)14c. 根據(jù)目標(biāo)函數(shù)梯度的模足夠小II f (Xk)5H終止準(zhǔn)那么1, 2 , 3 , 4, 5為給定的足夠小的正數(shù)。以上準(zhǔn)那么統(tǒng)稱為Himmelblau計(jì)算終止準(zhǔn)那么，簡稱第二章線性規(guī)劃2.1數(shù)學(xué)模型1.繁寫形式：minzc1x1 c2x2cn

31、xna11x1a12 x2a1n xnb1a21x1a22 x2a2nxnb2s.t.nbamx1am2 x2amn xx1,x2,xn0其中，bi 0, i1,2,m否那么，等式兩端同乘以“2.縮寫形式：minzncjxjj1naijxjbi,i1,2,ms.t.j1xj0,j1,2,n3.向量形式：minzCTXnpjxjbs.t.j1X0其中，C c1,c2,cT，Xx1,x2,xnT，b、線性規(guī)劃的標(biāo)準(zhǔn)型mb1,b2, ,bmT ，-1。pj a1j,a2j , ,amj 。4. 矩陣形式： minz CTXs.t.AX其中，a11a21a1na2np1,p2, , pnam1am2a

32、mnA ：約束條件的 m n 系數(shù)矩陣，m 0，n 0 ，一般地， m n ；b ：限定向量，一般地，bi 0,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è)約束為“ 型，那么“左端 +松弛變量 =右端松弛變量 0如： ai1x1ai2x2ainxnbi ，引入松弛變量 xn i 0，化為ai1x1ai2x2ain xnxn ibi假設(shè)約束為“ 型，那么“左端 -剩余變量 =右端剩余變量 0如： ai1x1ai2

33、x2ainxnbi ，引入剩余變量 xn i 0，化為ai1x1 ai2 x2ain xn xn i bi3. 假設(shè)存在無非負(fù)要求的變量 xk 稱為自由變量令 xk xkxk ，其中 xk 0 ， xk 0 ，代入目標(biāo)函數(shù)及約束條件即可。4. 某變量 xj 有上、下界假設(shè) xj uj ，即 xj uj0，令 XjXjuj ，有 Xj0 。用 Xj uj代替 xj 即可。假設(shè) xj t j 代替 xj 即可。例：，即 tj xj0，令 xjtjXj ，有 Xj0 。用 t j Xj§ 2.2線性規(guī)劃解的性質(zhì)、根本概念標(biāo)準(zhǔn)型LP:minzCTX1AX b2s tX03可行解容許解：滿足約

34、束2、3的解。最優(yōu)解：滿足1的容許解。基：設(shè)Am n的秩為m，假設(shè)B是A中的m m階可逆矩陣，稱B是線性規(guī)劃問題LP的一個(gè)基?；蛄浚夯鵅中的一列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è)根本解中有基變量為 0的根本解。退化的根本容許解：退化的最優(yōu)根本容許解：、線性規(guī)劃問題的根本定理定理 1 假設(shè)線性規(guī)劃問題存在容許域，那么其

35、容許域是凸集。定理 2 線性規(guī)劃問題的根本容許解對應(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è)根本容許解頂點(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)

36、的根本解是容許的。1o 引入附加變量，把數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。2o 假設(shè)約束條件中附加變量系數(shù)為“ -1，或原約束即為等式，那么 一般須引入人工變量。3o 目標(biāo)函數(shù)中，附加變量系數(shù)為 0，而人工變量系數(shù)為 M 很 大的正數(shù)。人工變量系數(shù)為大 M ：只要人工變量 >0，使前后約束條件不等 價(jià)，但由于目標(biāo)函數(shù)的修改， 同時(shí)也使所求的目標(biāo)函數(shù)最小值是一個(gè) 很大的數(shù)，也是對“篡改約束條件的一種懲罰，因此， M 叫做罰因子，大 M 法也叫做罰函數(shù)法。假設(shè)對極大化問題，目標(biāo)函數(shù)中人工變量系數(shù)為( -M )得到如下標(biāo)準(zhǔn)型：nmin zcj xja1nxnb1a2nxnb2j1x1 a1,m 1xm 1x

37、2 a2,m 1xm 1s.t.xm am,m 1xm 1amnxnbmxj 0 (j 1,2, ,n)其中，Xj(i 1,2,m)表示基變量；Xj(j m 1,n) 表示非基變2. 求出一個(gè)根本容許解1o 用非基變量表示基變量和目標(biāo)函數(shù)。用非基變量表示基變量，即有nXi biaij Xj (ij m 1用非基變量表示目標(biāo)函數(shù)，即1, ,m)mnciXicjXj1j m 1nzck Xkk1nm(cjci aij )Xjj m 1 i 1cibii1nz0(cjzj )Xjz0j m 1jXjj 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)的目