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

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