2011-2012最優(yōu)化理論與方法試題答案 李宗平教授出題

2011-2012第一學(xué)期期末考試最優(yōu)化理論與方法試題答案答案：非線性規(guī)劃極值問題的特點(diǎn)：（1）非線性規(guī)劃的極值有可能在邊界上取得，也可能在可行域的任一點(diǎn)處取得。即極值問題可能在可行域內(nèi)。（2）目標(biāo)函數(shù)如果是凸函數(shù)，定義域?yàn)橥挂?guī)劃時(shí)，它們的任一點(diǎn)局部極值點(diǎn)極為全局極值點(diǎn)。（3）非線性凸規(guī)劃問題的極值點(diǎn)存在的充要條件是庫(kù)恩塔克條件（凸函數(shù)極值點(diǎn)處的梯度向量為零）。凸規(guī)劃的定義：（1）目標(biāo)函數(shù)為凸函數(shù)（2）約束條件圖形特征表現(xiàn)為凹函數(shù)。凸規(guī)劃的可行域?yàn)橥辜?，任意一極小點(diǎn)都為全局極小點(diǎn)，且極小點(diǎn)的合集為一凸集。證明：任意一個(gè)極小點(diǎn)都為全局極小點(diǎn)。假設(shè)X*為凸規(guī)劃問題的一個(gè)局部極小點(diǎn)，則對(duì)于X*的一個(gè)充分小的鄰域N（X*）內(nèi)任一點(diǎn)X（X*）都有f（X）f（X*）。設(shè)Y是凸規(guī)劃可行域上的一個(gè)局部極小點(diǎn)，入為任意小的正數(shù)，那么：入*X*+（1-入）*YN,（X*）,則根據(jù)上面的敘述有：f（入*X*+（1-入）*Y）f（X*）。又f（X）為凸函數(shù)，根據(jù)凸函數(shù)的性質(zhì)有：f（入*X*+（1-入）*Y）入*f（X）+（1-入）*f（Y）???f（Y）Nf（X*）,即任意一個(gè)極小值點(diǎn)為全局極小點(diǎn)。證明：凸規(guī)劃極小值點(diǎn)的合集是一個(gè)凸集。根據(jù)凸函數(shù)的性質(zhì)3,小于某一個(gè)熟知的凸函數(shù)點(diǎn)的合集為一個(gè)凸集，即椿=，椿為凸集，故凸規(guī)劃極小點(diǎn)的合集是一個(gè)凸集。迭代算法：為了求f（X）的最優(yōu)解，首先給出一個(gè)初試估計(jì)（），如果按照某一算法得到（），并使（）比（）更優(yōu)（例如：對(duì)于最小值問題而言，有f（（））f（（））），再按照該算法得到比（）更優(yōu)的點(diǎn)（），?…以此類推，可得到一個(gè)解的數(shù)列（），若數(shù)列（）末尾有極限（），即()(),那么一般認(rèn)為數(shù)列()收斂于解（）。常用的迭代終止準(zhǔn)則：（1）相繼兩次迭代的絕對(duì)誤差：（）()￡；()()￡（2）相繼兩次迭代的相對(duì)誤差：一（~）(^￡；■()()￡()()（3）目標(biāo)函數(shù)梯度模的足夠?。海ǎ?其中￡，￡，￡，￡，￡0.斐波那契算法：一種對(duì)稱地把區(qū)間縮短的方法，它以最少的次數(shù)把區(qū)間縮短為所要求的長(zhǎng)度（斐波那契長(zhǎng)度滿足），但每次的縮短率不同。黃金分割法又稱0.618法，它是一種等速對(duì)稱分割法，采用固定的縮短率0.618和0.382處，同時(shí)便于縮短次數(shù)進(jìn)行計(jì)算。例如，把區(qū)間（）經(jīng)過n次縮短為單位區(qū)間，可

由來確定。區(qū)別：黃金分割法是等速分割算法，而斐波那契算法是不等速分割算法。+是函數(shù)f(X)定義域的R中的一個(gè)可行點(diǎn)，D是函數(shù)在點(diǎn)處的任一可行方向，是該點(diǎn)起作用的的約束，回答下列問題并證明：當(dāng)D是處可行的下降方向時(shí)，D與和之間有甚關(guān)系？若是局部極小點(diǎn)，D與和之間有甚關(guān)系？解：(1)D為處可行的下降方向，有證明：取為充分小的正數(shù)，則+AR,且滿足(A)，對(duì)(X)在處進(jìn)行泰勒展開：(A)=()+AD+()，當(dāng)A0時(shí)，有：=0，A當(dāng)D時(shí)，(A)成立，就能證明D為下降方向，同樣(成立，就能證明D為下降方向，同樣對(duì)于目標(biāo)函數(shù)f(X)來說，只要f(入)對(duì)于f(X)在處泰勒展開，得到：(入)=()+入D+(),d=0d=0當(dāng)()D0時(shí)，(入)(),D為可行方向。(2)若是局部極小點(diǎn)，則不可能找出滿足以下條件的的可行方向D來滿足:證明：反證法：假設(shè)在點(diǎn)處存在一個(gè)可行方向D同時(shí)滿足上述條件，則，同(1)所述過程，D為可行下降方向，這與題目條件是局部極小點(diǎn)相矛盾。所以，D不能同時(shí)滿足6.對(duì)于無約束極值問題X+c,式中A為n的對(duì)稱矩陣，X，B,c為常數(shù)。設(shè)向量，i=0,1,2,...,n-1,為A共軛，則從任一點(diǎn)出發(fā)，相繼以TOC\o"1-5"\h\z6.對(duì)于無約束極值問題X+c,式中A為n的對(duì)稱矩陣，X，B,c為解：f(X)=AX+B經(jīng)過n次搜索后，得到的解分別是，，…，f()=A+B;f()=A+B=A(入)+B=f()+入設(shè)f()，對(duì)于k=0,1,2,..,n-1,有：f()=f()+入=f()+入入入在經(jīng)過一維搜索確定最佳步長(zhǎng)A時(shí)，有:=0因此，對(duì)于k=0,1,2,?…n-1時(shí)，有：()f()=()f(因此，對(duì)于k=0,1,2,?…n-1時(shí)，有：()f()=()f()+入()=0即：f()為n個(gè)線性無關(guān)的向量為無約束相關(guān)極值問題的極小點(diǎn)到的為極小點(diǎn)。7.用梯度法求f(X)=解：初始估計(jì)即經(jīng)過n次以的極小點(diǎn)，正交，則只有f()=0,所以，為方向的算法得已知=0.1故需要進(jìn)行下一次的迭代得到其中故需要進(jìn)行下一次的迭代得到其中入VH(X)=此時(shí)，檢驗(yàn)終止準(zhǔn)則：=0迭代終止。此時(shí)，檢驗(yàn)終止準(zhǔn)則：=0迭代終止。f(X)為嚴(yán)格凸函數(shù)-4又?「￡(X)的海塞矩陣H(X)是正定時(shí)...=是的全局極小點(diǎn)，且8.給出二次規(guī)劃要求：(1)庫(kù)恩一塔克條件求最優(yōu)解(2)寫出等價(jià)的線性規(guī)劃問題并化為標(biāo)準(zhǔn)形f(X)為嚴(yán)格凸函數(shù)-4注意本題運(yùn)用庫(kù)恩-塔克條件解題時(shí)應(yīng)該引入4個(gè)拉格朗日乘