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

1、 pTx8，VxS且pT08。由80，及S的定義，我們有：pTx8+pTx，VxS，VxS。121122結(jié)果得證。1.4.無(wú)約束問(wèn)題的最優(yōu)性條件一、極小點(diǎn)的概念1局部極小點(diǎn)2嚴(yán)格局部極小點(diǎn)3全局(總體)極小點(diǎn)4嚴(yán)格全局(總體)極小點(diǎn)。注：在非線性規(guī)劃中，大多數(shù)算法都致力于求最優(yōu)化問(wèn)題的局部極小點(diǎn)，這是由于一般地求全局極小點(diǎn)極為困難，僅當(dāng)問(wèn)題為凸規(guī)劃時(shí)，局部極小為全局極小。二、最優(yōu)性條件定理1.47(階必要條件)若x是局部極小點(diǎn)，則Vf(x)，0。定理1.48(二階必要條件)若x是局部極小點(diǎn)，則Vf(x)，0，V2f(x)0。(半正定)定理1.49(二階充分條件)x是局部極小點(diǎn)的充分條件是：Vf

2、(x)，0，且V2f(x)正定。注：使Vf(x)，0的點(diǎn)x稱(chēng)為函數(shù)的穩(wěn)定點(diǎn)。穩(wěn)定點(diǎn)可以是極大點(diǎn)，也可是極小點(diǎn)，也可兩者均不是，此時(shí)稱(chēng)為鞍點(diǎn)。定理1.50若f(x):RnR是連續(xù)可微的凸函數(shù)，則x是總體極小點(diǎn)的充要條件是Vf(x)，0。證明：必要性由定理1.47，充分性則由f(x)f(x)+Vf(x)T(x-x)直接可得。1.5.最優(yōu)化算法的結(jié)構(gòu)一、算法結(jié)構(gòu)最優(yōu)化算法通常采用迭代形式，由算法產(chǎn)生一個(gè)有限或無(wú)限點(diǎn)列。一般地，需要證明迭代點(diǎn)列x的聚點(diǎn)(子序列的極限點(diǎn))為一局部極小點(diǎn)。算法的基本迭代格式為：kx，x+adk1kkk它包含兩個(gè)要素：步長(zhǎng)因子a與搜索方向d。在最優(yōu)化算法中，d通常是函數(shù)f在

3、x處的下降方kkkk向，即d滿足：kdTf(x)0，或f(x+,d)0及一個(gè)與迭代次數(shù)k無(wú)k關(guān)的常數(shù)q0，使得xx*limk+1qkx0時(shí)，稱(chēng)為線性收斂；當(dāng)1，0或，1，q0時(shí)，稱(chēng)超線性收斂；當(dāng),2時(shí)，稱(chēng)二階收斂。注：若一個(gè)算法應(yīng)用于正定二次函數(shù)時(shí)，具有有限終止性質(zhì)，則稱(chēng)該算法二次收斂。二次收斂與二階收斂是完全不同的概念，不存在孰強(qiáng)孰弱的簡(jiǎn)單關(guān)系。但大量數(shù)值計(jì)算結(jié)果表明：具有二次收斂性質(zhì)的算法，實(shí)際計(jì)算性能一般都較好，因而二次收斂也常作為一個(gè)好算法的標(biāo)志。三、關(guān)于常用算法的終止條件定理1.52若序列x超線性收斂到x*，那么kxxlimkik1.k,gxx*k證明：略此定理的意義在于：當(dāng)算法具有超線性收斂性質(zhì)時(shí)，可用x-x8替代x-x*作為k1kk算法停止準(zhǔn)則。事實(shí)上，在實(shí)際應(yīng)用中，即使不知道算法是