最優(yōu)化理論與方法第一章

最優(yōu)成像科學(xué)與圖主樓C2-自動(dòng)化學(xué)與參最優(yōu)化理論與參考數(shù)值最優(yōu)化NumericalOptimization(美特(Nocedal.J.)等最優(yōu)化理論與方 最優(yōu)化計(jì)算原理與算法程序設(shè)計(jì)粟塔山第一自動(dòng)化學(xué)最優(yōu)化理論和方法是近幾十多年來發(fā)展十分迅在數(shù)學(xué)上最優(yōu)化問題的研究已經(jīng)有很多年的歷第一本概自動(dòng)化學(xué)最優(yōu)化方法研究在一定限制條件下,選擇某種最優(yōu)方案達(dá)到最優(yōu)目標(biāo)的方最優(yōu)化理論最優(yōu)化方法的理模型與給定一個(gè)D(稱為可行集),和該集合上定義的實(shí)值函數(shù)f(x),需計(jì)算函數(shù)在可行集上的極值。minf

maxf(x)模型分類：按可行集性質(zhì)可行集中的元素是有限 “組合優(yōu)化 “動(dòng)態(tài)規(guī)可行集是無窮行集目標(biāo)函數(shù)為定積分)“最優(yōu)控制”本課程討論線性規(guī)劃與非線性規(guī)劃本課程主要第一第二章線性規(guī)劃的基本純形方法第四章對偶原理第五優(yōu)性條件化算法的結(jié)構(gòu)與一維搜索第七章一維搜索第八章使用導(dǎo)數(shù)的最第九約束最優(yōu)化的直接方法第十章可行方向法第十一罰函數(shù)法第十二章二次規(guī)劃經(jīng)典極值①無約束極值問②有約束極值問1、無約束極值問題的數(shù)學(xué)minf(x)x2、約束條件下極值問題的數(shù)學(xué)s.t.gi(x)0,ihj(x)0,j極大值問題可以轉(zhuǎn)化為極小值問題來進(jìn)行求 解決優(yōu)化問題的一般方法④編寫程序，利用計(jì)算機(jī)求問：應(yīng)如何安排制作計(jì)劃才能獲得最大收一、問題前期分二、模型假變量假x2千克，可獲f元。 總收益可表示為：f10x15x2受一級黃豆數(shù)量限制0.3x10.4x2受二級黃豆數(shù)量限制0.5x10.2x2綜上分析，得到該問題的數(shù)學(xué)maxf10x1s.t0.3x10.4x290.5x10.2x28x1,x20 各產(chǎn)地的產(chǎn)量是a1,a2,…,am;有n個(gè)銷地B1,B2,…,Bn.假定從產(chǎn)地Ai(i=1,2,…,m)到銷地 如 問題的總產(chǎn)量等于總銷量， aibj j1

j x i1,2,, j xij

i1,2,,j

梯度、Hesse陣Taylor展自動(dòng)化學(xué)梯

f f

f xn單位向量,可微函數(shù)(x)在x處沿方向h的flimf(xh)f(x) f(x)Th

f

cos(f(x),f f f(x)hf f(x)hf f(x)hf f(x)hf f(x)hf(x)f(x)Thf(x)f(x)Thf(x)f(x)Th ,則(x)與h的夾角為鈍角此時(shí)沿h的方向，(xf(x)hff(x) f

時(shí)，h取向(x是(xx處的最速上升方向，而負(fù)梯度方向-(x是(xx處的最速下降方向?？梢娞荻瘸Ｒ姾瘮?shù)(bTx)(xTx)ATA(xTAx)2AxATA,f(x)1xTAxbTxcf(x)Ax22 2

2 2

x1x2

x1x 2 2f(X)

x2x

2x2

x2xn 2xnx

2xnx

2 nx nf(X)1x31x32x2 求f2極值定義1minfx)fx*

x*

x*DxD有fx)fx*稱x*是全局極小值點(diǎn)。f(f(x)f(x* xD,x稱x*是嚴(yán)格全局極小點(diǎn)定義2:x*D，存在x*的鄰域

稱x*為局部嚴(yán)格l.opt 嚴(yán)格g.opt l.opt多元函數(shù)的Taylor展設(shè)f(x):Rn R，若f(x)在點(diǎn)x0處二階可導(dǎo)。則在x0的鄰域內(nèi)二階Taylor展式：f(x)f(x0)f(x0)T(xx021(xx0)TH(x)(xx0)+(xx022f(x)f(x0)f(x0)T(xx0)1(xx0)TH()(xx02其中=x0+(xx00自動(dòng)化學(xué)[x1,x2]xx1(1)x2,0x x 0oS

x(1),

)

SS{x注

)x(2)=x(2)

(x(1)x(2))x(1)x(2)的線凸 非凸 非凸例1:證明:集合S={x∣Ax=b}是凸集。其中，A為m 例2：令A(yù)+B={a+b| A, R},試證：若A,B為凸集， 數(shù)，則A+B與A為凸集.x1y1AB,x1A,y1B,x2y2AB,x2A,y2B,(0,1欲證AB為凸(x1y1)AB為凸集(x1y1)

y2)Ay2例3：超平面H{xpTx}為凸集，其中p為n空間都是凸集:正的閉半空間HxpTx}負(fù)的閉半空間H{xpTx}正的開半空間xpTx}負(fù)的開半空間-xpTx}實(shí)3中，滿足三元一次方程ax+by+cz=d的點(diǎn)廣之，nnH{xpTx}的點(diǎn)(x1,x2,...,xn)的全體H就叫空間的一張超定義3：設(shè)x(1),x(2),…, j≥ j=1,那么 jx(j)為x(1),x(2),…x(m)j j=凸組定理 Rn是凸集D中任意有限個(gè)（m個(gè)）的凸組合仍在D由凸集定義定理2：任意多個(gè)凸集的交仍為定義4:包含任意集合XRn的所有凸集之交稱為n定義5：設(shè)X={x(0,x(1x(2x(n)}為Rnn+1個(gè)點(diǎn)組成的集合,x(1)-x(0x(2x(0x(nx(0線性無關(guān)則稱X的凸包C0(X)為單純形，x(1x(2x(n)為單純形的頂點(diǎn)二、凸函 定義6:設(shè)集合 Rn為凸集，函數(shù)f: x(1),

D 01，均)x(2)) 若上面不等式以嚴(yán)格不等式成立，則稱f(x)D上的嚴(yán)格凸函數(shù)當(dāng)f(x為凸函數(shù)（嚴(yán)格凸函數(shù)）時(shí)，則f(x為凹 嚴(yán)格凹嚴(yán)格凸函 嚴(yán)格凹定理3設(shè)f:D可微,則

R1,D是非空開凸集,f(x)在Df(x)在Df(x2)f(x1)f(x1)T(x2x1),x1,x2f(x)在D上為嚴(yán)格凸函數(shù)f(x2)f(x1)f(x1)T(x2x1),x1,x2f(x)在Dx1,x2f(x1(x2x1)) ff(x2)(1)ff(x1)(f(x2)f

f(x x))f(

f(x2)f(x1)其中f(x1(x2x1)) f(x1)f(x1)Tx1)(x2x1

f(x1(x2x1))f lim

f(x1)Tx1)

x2

xxf(x1)Tx1) f(x2)f(x1)f(x2)f(x1)f(x1)T(x2f(x2)f(x1)f(x1)T(x2x1),x1,x2 fx1f(Yf(Y)Tx1Y取x1Yfx2f(Yf(Y)Tx2Y取x2Y代入 f(x1)(1)f(x2)(Y)f(Y)T(x1Y(1)f(Y)f(Y)T(x2Yf(x)為凸函數(shù)定理4:設(shè)f: R1,D是非空開凸集,f(x)D上二階可微,f(x)在D上為凸函 2f(x)是半正定矩是正定矩注意

(x)正定是f(x)為嚴(yán)格凸函數(shù)的條件而非必要例2:f(x)=x4, 例3證f(x)x23x29x22x 是凸函

6x2

2x1定義7:對于(MP)minf(x) g(x) i1 f(x-gi(xi=1~m都是凸函數(shù)(MP)例