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

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