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

可知，，有再由，故有即由是中任一向量，所以有界，因而是有界閉凸集。定理1.34（Minkowski不等式）對，有，即：.證明：當(dāng)或?yàn)榱阆蛄繒r(shí)，結(jié)論顯然成立。當(dāng)時(shí)，也易證明。以下設(shè)，且?？紤]函數(shù)，由于，故嚴(yán)格凸。注意到由函數(shù)的凸性，于是有，因此，由此即得，即.三、一致凸函數(shù)定義1.35設(shè)是非空凸集上的函數(shù)，若存在一個(gè)常數(shù)，使得對任意的，及任意。均有，則稱在凸集上一致凸。由定義立即可知：一致凸嚴(yán)格凸凸。一致凸函數(shù)的判別定理定理1.36設(shè)是非空開凸集上連續(xù)可微函數(shù)，則在上一致凸的充要條件是存在常數(shù)，使得，證明：先證必要性。若一致凸，則從而因此（﹡）而將上式代入（﹡）即得：令，得。再證充分性。任取，令，。由是凸集，故，因而有：兩式分別乘和再相加，則有將代入即得結(jié)論：.定理1.37設(shè)是開凸集上連續(xù)可微函數(shù)，則在上一致凸的充要條件是：存在常數(shù)，使得，證明：參見徐成賢等著《近代優(yōu)化方法》P15。定理1.38設(shè)在開凸集上二階連續(xù)可微，則在上一致凸的充要條件是：存在常數(shù)，使得：，，.證明：充分性：，有其中，。由于是凸集，故。因此，。令，則。必要性：設(shè)在上一致凸。任取，且，則有.四、凸集的分離與支撐凸集的分離與支撐定理在研究約束最優(yōu)化問題的最優(yōu)性條件時(shí)具有基本的重要性，起著十分關(guān)鍵的作用。定理1.39設(shè)是非空閉凸集，，則存在唯一的點(diǎn)，它與的距離最短。進(jìn)一步，與距離最短的充要條件是：，證明：先證定理的第一部分存在性任取一點(diǎn)，則集合為一非空有界閉集，而是的連續(xù)函數(shù)，故它必在的某一點(diǎn)上取得最小值，此即為所求。注意到，而，必有。唯一性假定還有，滿足。由的凸性，則考慮由是中點(diǎn)到的最小距離，故上式必取等式。因而必有再由，得。若，則，得與矛盾。因而只能是，即，或，唯一性得證。再證定理第二部分若，都有，則即與有極小距離。反之，若，都有由于對充分小的，有因此另一方面，所以兩邊同除，并令，即得所要的結(jié)果。點(diǎn)與凸集的分離定理定理1.40設(shè)是非空閉凸集，，，則存在向量和實(shí)數(shù)，使得，，并且同時(shí)滿足即超平面嚴(yán)格分離點(diǎn)和閉凸集。證明：由于是閉凸集，。故定理1.39知，存在唯一的一點(diǎn)，使得，取，則，也即。再取，則，有。又故有定理證畢。定理1.41（Farkas引理）設(shè)，，則下面兩個(gè)等式與不等式系統(tǒng)有且僅有一個(gè)有解。①②證明：若②有解，則存在，使。下證①必?zé)o解。事實(shí)上，若滿足。那么，（由，）故方程組①無解。若②無解，記則是非空閉凸集，且，由上面凸集的分離定理，存在，和，使得，且，由于，故，又，由于可任意大,而為固定常數(shù)，故必有?？梢娤蛄繚M足，且因而是①的解，定理證畢。凸集與凸集的分離定理定義1.42設(shè)是非空集合，，（的邊界）。若或，則稱是在處的支撐超平面；若，則稱為在處的正常支撐超平面。定理1.43設(shè)是非空凸集，。那么，在存在一個(gè)支撐超平面。即存在非零向量，使得，這里表示的閉包。證明：由于（是的一個(gè)邊界點(diǎn)），故存在序列，每個(gè)均不屬于，且。由定理1.40可知，對每個(gè)，存在，且，使得，。由于有界，故存在收斂的子列，設(shè)其極限為（顯然有，故為非零向量）。對此子序列，當(dāng)時(shí)，有，。對每個(gè)固定，在上式中令得：，這便是所需結(jié)論。推論：設(shè)是非空凸集，若，則存在非零向量，使得：，。證明：⑴若，由定理1.40，存在超平面分離和。⑵若，由上面定理1.43即得。定義1.44設(shè)是非空凸集，若有，且，，則稱超平面分離和；若，則稱正常分離與；若，且，，則稱嚴(yán)格分離與；若，且，，（其中）則稱強(qiáng)分離與。由定義容易推出：強(qiáng)分離嚴(yán)格分離正常分離分離。定理1.45設(shè)是非空凸集，若，則存在超平面分離與，即存在非零向量，使得，，證明：設(shè)由是凸集，及（否則），再由前面推論，存在非零向量，使得：，。注意到，由此可得，，。定理1.46設(shè)和是閉凸集，且有界，若，則存在一個(gè)超平面強(qiáng)分離和，即存在非零向量和，使得證明：設(shè)，可證是閉的。事實(shí)上，設(shè)，且。由的定義知：，（，）由于是緊的，故存在收斂子列，使得。由于時(shí)，，因而有由，，進(jìn)而得，即，故為閉集。于是，存在非零向量和實(shí)數(shù)，使得：，且。由，及的定義，我們有：，，。結(jié)果得證。§1.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（一階必要條件）若是局部極小點(diǎn)，則。定理1.48（二階必要條件）若是局部極小點(diǎn)，則，。（半正定）定理1.49（二階充分條件）是局部極小點(diǎn)的充分條件是：，且正定。注：使的點(diǎn)稱為函數(shù)的穩(wěn)定點(diǎn)。穩(wěn)定點(diǎn)可以是極大點(diǎn)，也可是極小點(diǎn)，也可兩者均不是，此時(shí)稱為鞍點(diǎn)。定理1.50若是連續(xù)可微的凸函數(shù)，則是總體極小點(diǎn)的充要條件是。證明：必要性由定理1.47，充分性則由直接可得。§1.5.最優(yōu)化算法的結(jié)構(gòu)一、算法結(jié)構(gòu)最優(yōu)化算法通常采用迭代形式，由算法產(chǎn)生一個(gè)有限或無限點(diǎn)列。一般地，需要證明迭代點(diǎn)列的聚點(diǎn)（子序列的極限點(diǎn)）為一局部極小點(diǎn)。算法的基本迭代格式為：它包含兩個(gè)要素：步長因子與搜索方向。在最優(yōu)化算法中，通常是函數(shù)在處的下降方向，即滿足：，或?；窘Y(jié)構(gòu)給定初始點(diǎn)；(1)確定搜索方向；(2)確定步長因子，使目標(biāo)函數(shù)值有某種程度的下降；(3)令，若滿足某種終止條件，則迭代停止，得到近似最優(yōu)解；否則重復(fù)以上步驟。二、算法的收斂速度定義1.51假設(shè)算法產(chǎn)生的點(diǎn)列收斂于最優(yōu)解。若存在實(shí)數(shù)及一個(gè)與迭代次數(shù)無關(guān)的常數(shù)，使得則稱算法產(chǎn)生的迭代點(diǎn)列具有階收斂速度。特別地，(1)當(dāng)，時(shí)，稱為線性收斂；(2)當(dāng)，或，時(shí)，稱超線性收斂；(3)當(dāng)時(shí)，稱二階收斂。注：若一個(gè)算法應(yīng)用于正定二次函數(shù)時(shí)，具有有限終止性質(zhì)，則稱該算法二次收斂。二次收斂與二階收斂是完全不同的概念，不存在孰強(qiáng)孰弱的簡單關(guān)系。但大量數(shù)值計(jì)算結(jié)果表明：具有二次收斂性質(zhì)的算法，實(shí)際計(jì)算性