附錄5：《最優(yōu)化方法》復(fù)習(xí)題

1、附錄5 最優(yōu)化方法復(fù)習(xí)題1、設(shè)是對稱矩陣，求在任意點處的梯度和Hesse矩陣解 2、設(shè)，其中二階可導(dǎo)，試求解 3、設(shè)方向是函數(shù)在點處的下降方向，令，其中為單位矩陣，證明方向也是函數(shù)在點處的下降方向證明由于方向是函數(shù)在點處的下降方向，因此，從而，所以，方向是函數(shù)在點處的下降方向4、是凸集的充分必要條件是的一切凸組合都屬于證明充分性顯然下證必要性設(shè)是凸集，對用歸納法證明當(dāng)時，由凸集的定義知結(jié)論成立，下面考慮時的情形令，其中，且不妨設(shè)（不然，結(jié)論成立），記，有，又，則由歸納假設(shè)知，而，且是凸集，故5、設(shè)為非空開凸集，在上可微，證明：為上的凸函數(shù)的充要條件是證明必要性設(shè)是上的凸函數(shù)，則及，有，于是 ，

2、因為開集，在上可微，故令，得，即充分性若有，則，取，從而，將上述兩式分別乘以和后，相加得，所以為凸函數(shù)6、證明：凸規(guī)劃的任意局部最優(yōu)解必是全局最優(yōu)解證明 用反證法設(shè)為凸規(guī)劃問題的局部最優(yōu)解，即存在的某個鄰域，使若不是全局最優(yōu)解，則存在，使由于為上的凸函數(shù)，因此，有當(dāng)充分接近1時，可使，于是，矛盾從而是全局最優(yōu)解7、設(shè)為非空凸集，是具有一階連續(xù)偏導(dǎo)數(shù)的凸函數(shù)，證明：是問題的最優(yōu)解的充要條件是：證明 必要性若為問題的最優(yōu)解反設(shè)存在，使得，則是函數(shù)在點處的下降方向，這與為問題的最優(yōu)解矛盾故充分性若反設(shè)存在，使得，因為凸集，在上可微，故令，得，這與已知條件矛盾，故是問題的最優(yōu)解8、設(shè)函數(shù)具有二階連續(xù)偏

3、導(dǎo)數(shù)，是的極小點的第次近似，利用在點處的二階Taylor展開式推導(dǎo)Newton法的迭代公式為證明由于具有二階連續(xù)偏導(dǎo)數(shù)，故且是對稱矩陣，因此是二次函數(shù)為求的極小點，可令，即，若正定，則上式解出的的平穩(wěn)點就是的極小點，以它作為的極小點的第次近似，記為，即，這就得到了Newton法的迭代公式.9、敘述常用優(yōu)化算法的迭代公式（1）0.618法的迭代公式：（2）Fibonacci法的迭代公式：（3）Newton一維搜索法的迭代公式： （4）最速下降法用于問題的迭代公式：（5）Newton法的迭代公式：（6）共軛方向法用于問題的迭代公式：10、已知線性規(guī)劃：（1）用單純形法求解該線性規(guī)劃問題的最優(yōu)解和最

4、優(yōu)值；（2）寫出線性規(guī)劃的對偶問題；（3）求解對偶問題的最優(yōu)解和最優(yōu)值解 （1）引進變量，將給定的線性規(guī)劃問題化為標(biāo)準(zhǔn)形式：311100601-220101011*-100120-21-1000020210-1403000125011-100120-30000-1-20所給問題的最優(yōu)解為，最優(yōu)值為（2）所給問題的對偶問題為： （1）（3）將上述問題化成如下等價問題：引進變量，將上述問題化為標(biāo)準(zhǔn)形式： （2）-3-1-11002-12-1*010-1-1-210011-60-10-200000-2-301-1031-210101-2000110-40-5000-20020問題（2）的最優(yōu)解為，最

5、優(yōu)值為（最小值）問題（1）的最優(yōu)解為，最優(yōu)值為（最大值）11、用0.618法求解 ，要求縮短后的區(qū)間長度不超過0.2，初始區(qū)間取解 第一次迭代：取確定最初試探點分別為，求目標(biāo)函數(shù)值：，比較目標(biāo)函數(shù)值：比較第二次迭代：第三次迭代：第四次迭代：第五次迭代：第六次迭代：第七次迭代：第八次迭代：第九次迭代：故12、用最速下降法求解 ，取，迭代兩次解，將寫成的形式，則第一次迭代：第二次迭代：13、用FR共軛梯度法求解 ，取，迭代兩次若給定判定是否還需進行迭代計算解 ，再寫成，第一次迭代：，令，從出發(fā)，沿進行一維搜索，即求的最優(yōu)解，得第一次迭代：，從出發(fā)，沿進行一維搜索，即求的最優(yōu)解，得此時得問題的最優(yōu)解

6、為，無需再進行迭代計算14、用坐標(biāo)輪換法求解 ，取，迭代一步解從點出發(fā)，沿進行一維搜索，即求的最優(yōu)解，得再從點出發(fā)，沿進行一維搜索，即求的最優(yōu)解，得15、用Powell法求解，取，初始搜索方向組，給定允許誤差（迭代兩次）解 第一次迭代：令，從點出發(fā)沿進行一維搜索，易得；接著從點出發(fā)沿進行一維搜索，得由此有加速方向 因為，所以要確定調(diào)整方向由于 ，按（8.4.17）式有，因此，并且又因，故（8.4.18）式不成立于是，不調(diào)整搜索方向組，并令第二次迭代：取，從點出發(fā)沿作一維搜索，得接著從點出發(fā)沿方向作一維搜索，得由此有加速方向因為，所以要確定調(diào)整方向因，故按（8.4.17）式易知，并且由于，因此（8.4.18）式成立。于是，從點出發(fā)沿作一維搜索，得。同時，以替換，即下一次迭代的搜索方向組取為16、用外罰函數(shù)法在直線上求一點，使得到原點的距離近似最短，取解 令，問題可歸為求解如下最優(yōu)化問題 引入罰函數(shù) 則原約束最優(yōu)化問題相應(yīng)的一系列無約束最優(yōu)化問題為：，其中解上述無約束問題，得，同時依次對用上述公式計算和，結(jié)果如下表所示10.521.25002131.11113258.00004494.938358172.7682616331.4692732657.57408641293.845991282571.93