最優(yōu)化方法復(fù)習(xí)題

1、最優(yōu)化方法復(fù)習(xí)題一、 簡述題1、怎樣判斷一個(gè)函數(shù)是否為凸函數(shù).（例如: 判斷函數(shù)是否為凸函數(shù)）2、寫出幾種迭代的收斂條件.3、熟練掌握利用單純形表求解線性規(guī)劃問題的方法（包括大M法及二階段法）. 見書本61頁(利用單純形表求解);69頁例題 (利用大M法求解、二階段法求解); 4、簡述牛頓法和擬牛頓法的優(yōu)缺點(diǎn).簡述共軛梯度法的基本思想.寫出Goldstein、Wolfe非精確一維線性搜索的公式。5、敘述常用優(yōu)化算法的迭代公式（1）0.618法的迭代公式：（2）Fibonacci法的迭代公式：（3）Newton一維搜索法的迭代公式： （4）推導(dǎo)最速下降法用于問題的迭代公式：（5）Newton法的

2、迭代公式：（6）共軛方向法用于問題的迭代公式：二、計(jì)算題雙折線法練習(xí)題 課本135頁 例FR共軛梯度法例題：課本150頁 例二次規(guī)劃有效集：課本213頁例, 所有留過的課后習(xí)題.三、練習(xí)題： 1、設(shè)是對(duì)稱矩陣，求在任意點(diǎn)處的梯度和Hesse矩陣解 2、設(shè)，其中二階可導(dǎo)，試求解 3、證明：凸規(guī)劃的任意局部最優(yōu)解必是全局最優(yōu)解證明 用反證法設(shè)為凸規(guī)劃問題的局部最優(yōu)解，即存在的某個(gè)鄰域，使若不是全局最優(yōu)解，則存在，使由于為上的凸函數(shù)，因此，有當(dāng)充分接近1時(shí)，可使，于是，矛盾從而是全局最優(yōu)解4、已知線性規(guī)劃：（1）用單純形法求解該線性規(guī)劃問題；（2）寫出線性規(guī)劃的對(duì)偶問題；解 （1）引進(jìn)變量，將給定的

3、線性規(guī)劃問題化為標(biāo)準(zhǔn)形式：所給問題的最優(yōu)解為，最優(yōu)值為（2）所給問題的對(duì)偶問題為： 5、用0.618法求解 ，要求縮短后的區(qū)間長度不超過0.2，初始區(qū)間取解 第一次迭代：取確定最初試探點(diǎn)分別為，求目標(biāo)函數(shù)值：，比較目標(biāo)函數(shù)值：比較第二次迭代：第三次迭代：第四次迭代：第五次迭代：第六次迭代：第七次迭代：第八次迭代：第九次迭代：故6、用最速下降法求解 ,取,迭代兩次解，將寫成的形式，則第一次迭代：第二次迭代：7、用FR共軛梯度法求解 ，取，迭代兩次若給定判定是否還需進(jìn)行迭代計(jì)算解 ，再寫成，第一次迭代：，令，從出發(fā)，沿進(jìn)行一維搜索，即求的最優(yōu)解，得第一次迭代：，從出發(fā)，沿進(jìn)行一維搜索，即求的最優(yōu)解

4、，得此時(shí)得問題的最優(yōu)解為，無需再進(jìn)行迭代計(jì)算8、求解問題 （方法不限定）取初始點(diǎn).9、采用精確搜索的BFGS算法求解下面的無約束問題：解：取 第一步迭代：，令，求得；第二步迭代：，令，求得。故，由于，故為最優(yōu)解。10、用有效集法求解下面的二次規(guī)劃問題：解：取初始可行點(diǎn)求解等式約束子問題 得解和相應(yīng)的Lagrange乘子 轉(zhuǎn)入第二次迭代。求解等式約束子問題 得解 令 轉(zhuǎn)入第三次迭代。求解等式約束子問題 得解和相應(yīng)的Lagrange乘子 由于，故得所求二次規(guī)劃問題的最優(yōu)解為 ，相應(yīng)的Lagrange乘子為 最速下降法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：方法簡單，計(jì)算量較??；最速下降法為全局收斂，對(duì)初始點(diǎn)的要求很少。缺

5、點(diǎn)：最速下降法的收斂速度與變量的尺度關(guān)系很大，對(duì)有些例子，在極小點(diǎn)附近產(chǎn)生顯著的鋸齒現(xiàn)象，收斂十分緩慢；最速下降法的最速下降僅是一種局部性質(zhì)，即從局部來看目標(biāo)函數(shù)的值下降得最快，但從總體來看它可能走了許多彎路。牛頓法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：牛頓法的收斂速度快，為二階收斂；公式簡單，計(jì)算方便。缺點(diǎn)：牛頓法要求f(x)二階可微，迭代中需多次計(jì)算；牛頓法具有局部收斂性，對(duì)初始點(diǎn)的要求比較苛刻。共軛梯度法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：計(jì)算公式簡單，存儲(chǔ)量較小，對(duì)初始點(diǎn)要求很少，對(duì)二次函數(shù)具有二次終止性；收斂速度介于最速下降法和牛頓法之間，對(duì)高維（n 較大）的非線性函數(shù)具有較高的效率。對(duì)于二次函數(shù)具有二次終止性，一般情況下優(yōu)于共軛梯度法。缺點(diǎn)：共軛梯度法的收斂性依賴于精確的一維搜索，計(jì)算量較大；共軛梯度法的一些理論背景至今尚不清楚，如周期性的重新開始，初始搜索放心的選取，一維搜索的精確性等，對(duì)共軛梯度法執(zhí)行的影響仍有待進(jìn)一步研究。擬牛頓法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：擬牛頓法具有較快的收斂速度（是超線性的）；對(duì)于