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

#由定義容易推出：強(qiáng)分離n嚴(yán)格分離n正常分離n分離。定理1.45設(shè)S,SuRn是非空凸集，若SCIS=0，則存在超平面分離S與S，即存在非零向121212量pGRn，使得pTX<pTX，VxGS，VxGS121122證明：設(shè)S=S-S=lx-xxGS,xGS證明：設(shè)12121122由S是凸集，及0電S（否則SJS2皿），再由前面推論，存在非零向量pGRn，使得:pTx<pT0=0，VxGSo注意到S-SuS，由此可得12pTx<pTx，VxGS，VxGSo121122定理］?46設(shè)S1和S2是閉凸集，且S1有界，若SfS2=0，則存在一個(gè)超平面強(qiáng)分離S1和S2,即存在非零向量p和8>0，使得inf8+inf8+sup證明：設(shè)S=S-S，可證S是閉的。事實(shí)上，設(shè){x}uS，且xTx。由S的定義知:12kkx=y-z，(yGS，zGS)kkkk1k2由于S是緊的，故存在收斂子列{y}，使得yTyGS。1kkGKk1由于kgK時(shí)，yty，y-ztxkkk因而有zTy-x=zGSk2由yGS，zGS，進(jìn)而得12x=y-zGS-S=S，12即xgS，故S為閉集。于是，存在非零向量p和實(shí)數(shù)8，使得:pTx>8，VxGS且pT0<8o由8>0，及S的定義，我們有：pTx>8+pTx，VxGS，VxGSo121122結(jié)果得證?！?.4.無約束問題的最優(yōu)性條件一、極小點(diǎn)的概念1．局部極小點(diǎn)2．嚴(yán)格局部極小點(diǎn)3．全局(總體)極小點(diǎn)4．嚴(yán)格全局(總體)極小點(diǎn)。注：在非線性規(guī)劃中，大多數(shù)算法都致力于求最優(yōu)化問題的局部極小點(diǎn)，這是由于一般地求全局極小點(diǎn)極為困難，僅當(dāng)問題為凸規(guī)劃時(shí)，局部極小為全局極小。二、最優(yōu)性條件定理1.47(—階必要條件)若x*是局部極小點(diǎn)，則Yf(x*)二0。定理1.48(二階必要條件)若x*是局部極小點(diǎn)，則Y(x*)二0，V2f(x*)>0。(半正定)定理1.49(二階充分條件)x*是局部極小點(diǎn)的充分條件是：Vf(x*)二0，且V2f(x*)正定。注：使Vf(x)=0的點(diǎn)x稱為函數(shù)的穩(wěn)定點(diǎn)。穩(wěn)定點(diǎn)可以是極大點(diǎn)，也可是極小點(diǎn)，也可兩者均不是，此時(shí)稱為鞍點(diǎn)。定理1.50若f(x):RnTR是連續(xù)可微的凸函數(shù)，則x*是總體極小點(diǎn)的充要條件是Vf(x*)二0。證明：必要性由定理1.47，充分性則由f(x)>f(x*)+Vf(x*)T(x—x*)直接可得?！?.5.最優(yōu)化算法的結(jié)構(gòu)一、算法結(jié)構(gòu)最優(yōu)化算法通常采用迭代形式，由算法產(chǎn)生一個(gè)有限或無限點(diǎn)列。一般地，需要證明迭代點(diǎn)列{x」的聚點(diǎn)(子序列的極限點(diǎn))為一局部極小點(diǎn)。算法的基本迭代格式為：kx=x+adk+1kkk它包含兩個(gè)要素：步長(zhǎng)因子Q與搜索方向d。在最優(yōu)化算法中，d通常是函數(shù)f在x處的下降方kkkk

向，即d滿足：kdTVf(x)<0，或f(x+ad)<f(x)。kkkkkk基本結(jié)構(gòu)給定初始點(diǎn)x；0確定搜索方向d；k確定步長(zhǎng)因子a，使目標(biāo)函數(shù)值有某種程度的下降；k令x二x+ad，若x滿足某種終止條件，則迭代停止，得到近似最優(yōu)解x；否則重復(fù)k+1kkkk+1k+1以上步驟。二、算法的收斂速度定義1.51假設(shè)算法產(chǎn)生的點(diǎn)列｛x｝收斂于最優(yōu)解x*。若存在實(shí)數(shù)a>0及一個(gè)與迭代次數(shù)k無k關(guān)的常數(shù)q>0，使得limkfgalimkfga|x-x*則稱算法產(chǎn)生的迭代點(diǎn)列｛xk｝具有a階收斂速度。特別地,當(dāng)a=1，q>0時(shí)，稱為線性收斂；當(dāng)1<aV2，q>0或a=1，q=0時(shí)，稱超線性收斂；當(dāng)a=2時(shí)，稱二階收斂。注：若一個(gè)算法應(yīng)用于正定二次函數(shù)時(shí)，具有有限終止性質(zhì)，則稱該算法二次收斂。二次收斂與二階收斂是完全不同的概念，不存在孰強(qiáng)孰弱的簡(jiǎn)單關(guān)系。但大量數(shù)值計(jì)算結(jié)果表明：具有二次收斂性質(zhì)的算法，實(shí)際計(jì)算性能一般都較好，因而二次收斂也常作為一個(gè)好算法的標(biāo)志。三、關(guān)于常用算法的終止條件定理1.52若序列｛x｝超線性收斂到x*，那么klim|x一x*證明：略此定理的意義在于：當(dāng)算法具有超線性收斂性質(zhì)時(shí)，可用卜-X||<e替代|lx-x^l<￡作為k+1kk算法停止準(zhǔn)則。事實(shí)