最優(yōu)化算法期末復(fù)習(xí).doc

碩士學(xué)位論文一、無約束優(yōu)化問題設(shè)是連續(xù)可微函數(shù),考察如下無約束優(yōu)化問題1:， (1)我們稱為問題(1)的目標(biāo)函數(shù)記為在處的梯度,若點(diǎn)滿足我們稱之為函數(shù)的駐點(diǎn),或穩(wěn)定點(diǎn)由最優(yōu)解的條件可知,問題(1.1)的解都是穩(wěn)定點(diǎn)二、迭代法的基本格式求解(1)常用迭代法,其基本思想是：給定一個初始點(diǎn),按照某一迭代規(guī)則產(chǎn)生一個點(diǎn)列,且單調(diào)遞減,使得當(dāng)是有窮點(diǎn)列時,其最后一個點(diǎn)是問題的最優(yōu)解當(dāng)是無窮點(diǎn)列時,它有極限點(diǎn),且其極限點(diǎn)是問題的最優(yōu)解記是第次迭代時的迭代點(diǎn),是第次迭代時的迭代方向, 是第次的迭代步長,則有基本的迭代公式:其中是在處的一個下降方向,滿足,稱為步長,通常用線性搜索得到常用的線性搜索方式如精確線性搜索2 ,即是下面的一維最優(yōu)化問題的解:三、常用的線搜索:(1)Armijo線性搜索 ：給定 ,求,滿足條件:. (2)(2)Wolfe線性搜索：求滿足條件:, (3). (4)其中,第一個不等式保證充分下降,第二個不等式防止步長過小.(3)強(qiáng)Wolfe線性搜索求滿足條件:, (5). (6)其中.(3)推廣的Wolfe線性搜索 ：求滿足條件:, (7). (8)其中,當(dāng)時,推廣的Wolfe線性搜索就是強(qiáng)Wolfe線性搜索.(4)Goldstein線性搜索2：求滿足條件:, (9)其中: .四、常用的算法最速下降法:設(shè)二次連續(xù)可微,且對任意的,則迭代方向:采用精確線性搜索確定步長。牛頓法：設(shè)二次連續(xù)可微,且對任意的,正定,則迭代方向:,是函數(shù)在處的下降方向,該方向稱為Newton方向它是在處的二次近似的最小值點(diǎn)或等價地, 是下面關(guān)于的線性方程組的解: (10)擬牛頓法:擬牛頓法的基本思想是在Newton法的子問題(1.11)中用的某個近似矩陣取代即在某種意義下,使相應(yīng)的算法產(chǎn)生的方向是Newton方向的近似此外,對所有的對稱正定,且容易計算. 設(shè)二次連續(xù)可微,利用多元函數(shù)數(shù)Taylor展開得如下近似:,因此的一種合理的取法是:用取代時,上面的近似等式成立,即滿足方程, （11）其中,.若令則擬牛頓方程(11)可以等價地寫成,注意到,擬Newton方向是Newton方向在某種意義上的一個近似BFGS算法被認(rèn)為是目前最好的一種算法之一,得到了極為廣泛的應(yīng)用，其修正公式為：. （12） BFGS算法的步驟：步0: 給定常數(shù)，初始對稱下定陣,選取初始點(diǎn)，置,步1：如果,終止;步2: 解線性方程組：;步3: 由線搜索確定步長;步4: 令，若，則停止；否則，按(12)確定，步5: 置,轉(zhuǎn)步2.如果步4中采用Armijo型線性搜索，則采用如下修正公式：共軛梯度法共軛梯度法的格式為: (13)其中,方向由下式確定: (14)其中,參數(shù)的選取滿足共軛性,即當(dāng)目標(biāo)函數(shù)為二次函數(shù)時,應(yīng)使得搜索方向與關(guān)于的Hessian陣共軛(1.14)中參數(shù)的不同選取方式對應(yīng)于不同的共軛梯度法,著名的共軛梯度法包括:FR算法、PRP算法、HS算法、共軛下降法（CD算法11）和DY算法12,分別由Fletcher-Reever、Polak-Ribiere-Polyak、Hestenes-Stiefel、Fletcher以及Dai-Yuan給出,這些算法中的定義如下4：其中,表示歐氏范數(shù) 其中：FR方法在精確線搜索下收斂，DY方法在Wolfe 線搜索下收斂，CD算法在強(qiáng)Wolfe 線搜索下下降。Hager和Zhang提出了一種新的共軛梯度法,這里我們稱為HZ方法，其中的計算方法如下: (15)對于上述方法,Hager和Zhang證明了的充分下降條件：. (16)張麗等人提出了一種保守的HZ方法：設(shè)為當(dāng)前迭代點(diǎn)按下式定義: (17)其中由(15)定義, ,和是兩個常數(shù)該算法在Armijo線搜索下全局收斂。算法4.1(MHZ算法)步0: