第三章無約束最優(yōu)化的梯度方法

1、第三章 無約束最優(yōu)化的梯度方法1.最速下降法假定我們已經(jīng)迭代了次，獲得了第個(gè)迭代點(diǎn)。從出發(fā)，顯然應(yīng)沿下降方向進(jìn)行，由于負(fù)梯度方向是最速下降方向，因此沿負(fù)梯度方向應(yīng)該是有利的。因此，取搜索方向。此時(shí)有：如將該方法應(yīng)用于二次函數(shù)，則可求出的顯式表達(dá)式。2.Newton法適用條件：如果目標(biāo)函數(shù)在上具有連續(xù)的二階偏導(dǎo)數(shù)，其Hesse矩陣正定?；鞠敕ǎ嚎紤]從到的迭代過程。在點(diǎn)處用二次函數(shù)來逼近，即：3.共軛方向法與共軛梯度法 1) 共軛方向法定義1:設(shè)是對稱正定矩陣。若維空間中非零向量系滿足， ,則稱是共軛的，或稱的方向是共軛方向。定理1:若非零向量系是共軛的，則這個(gè)向量線性無關(guān)。推論：在維空間中，互

2、相共軛的非零向量的向量個(gè)數(shù)不超過。定義2:設(shè)是線性無關(guān)的向量系，是任意實(shí)數(shù)。對于任意指定的，稱形式為的向量集合稱為由點(diǎn)和向量系所生成的線性流形，記為。定理2:假設(shè)：為對稱正定矩陣非零向量是共軛向量系；對二次目標(biāo)函數(shù)順次進(jìn)行如下次直線搜索：，其中是任意選定的初始點(diǎn)。則,是二次函數(shù)在線性流形上的極小點(diǎn)。證明：前面已經(jīng)證明由條件可知上式左乘后再在兩邊加上，得：即：由上式有，將所得等式兩邊左乘，有證明:按條件，則存在一組數(shù)使得同樣，對于任意上面兩式相減得由結(jié)論可知由于是正定的，因此是在線性流行上的極小點(diǎn)。當(dāng)時(shí)，線性流行就是整個(gè)維空間了，因此此時(shí)就是中的極小點(diǎn)。共軛方向法：已知：具有正定矩陣的二次目標(biāo)函

3、數(shù)和終止限。選定初始點(diǎn)和具有下降方向的向量；置。作直線搜索。判別是否滿足：若滿足，停機(jī)。提供共軛方向，使得，k=k+1二次函數(shù)的直線搜索：共軛向量系的構(gòu)造方法：先選定個(gè)線性無關(guān)的向量系，令設(shè)已求得共軛向量，現(xiàn)在來求令為使與共軛，應(yīng)有：，由此解得：于是共軛方向法的適用范圍：可用于非二次函數(shù)，首先通過Taylor公式用二次函數(shù)來逼近非二次函數(shù)。其次，可用來構(gòu)造共軛向量系，這要求充分地靠近。2) 共軛梯度法初始共軛向量恰好取為初始點(diǎn)處的負(fù)梯度，以下各共軛方向由第迭代點(diǎn)處的負(fù)梯度與已得到的共軛向量的線性組合來確定。因?yàn)樵摲椒恳粋€(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度構(gòu)造出來的，所以稱為共軛梯度法。設(shè)已求

4、得共軛向量，現(xiàn)在來求由，知和是線性無關(guān)的，取考慮與共軛，需滿足：于是有：現(xiàn)在證明除與共軛外，還與共軛。對依次計(jì)算由于是共軛向量，因此，因?yàn)橛忠驗(yàn)?從共軛向量系構(gòu)建方法可以看出，迭代點(diǎn)處的梯度是共軛向量系的線性組合。，因此有：，,從而證明了與共軛。共軛梯度法在非二次函數(shù)中的應(yīng)用：為了把共軛梯度法應(yīng)用在非二次函數(shù)中，有必要消去表達(dá)式中的。由于因?yàn)?，根?jù)表達(dá)式的不同，可得到四種共軛梯度算法。最常采用的是第二種表達(dá)方式。4.變尺度法1)基本想法考慮Newton迭代公式，變尺度法就是要消除這個(gè)迭代公式中的Hesse逆矩陣，為此擬采用某種近似矩陣來替換它，即構(gòu)造一個(gè)矩陣序列去逼近。因此，迭代公式為其中可通

5、過從出發(fā)沿作直線搜索來確定。為使確實(shí)與近似并具有容易計(jì)算的特點(diǎn)，對附加下列條件。要求對稱正定，保證迭代公式具有下降性質(zhì)。如對稱正定，則，保證迭代公式具有下降性質(zhì)。要求之間的迭代具有簡單的形式。，其中稱為校正矩陣，上式稱為校正公式。必須滿足擬Newton條件對于二次函數(shù)而言,有:上面兩式相減有:如的逆存在,則有成立,表明能很好近似。如記，于是擬Newton條件可寫為：擬牛頓法算法：已知：目標(biāo)函數(shù)及其梯度，終止準(zhǔn)則。選定初始點(diǎn)；計(jì)算，選定初始矩陣。計(jì)算搜索方向。作直線搜索。如滿足終止準(zhǔn)則，停機(jī)。計(jì)算。，轉(zhuǎn)。2)校正公式(1)對稱秩1算法(SR1法)校正公式取為其中是維待定非零向量，是待定常數(shù)，由于校正公式必須滿足擬牛頓條件，于是有：。取，于是校正公式為：對稱秩1算法的性質(zhì)：性質(zhì)1:設(shè)將SR1法施用于具有對稱正定矩陣的二次函數(shù)，如果初始矩陣是對稱的。迭代點(diǎn)是互異的。當(dāng)時(shí)，那么有：()此算法所生成的搜索方向是互相共軛的。()對，性質(zhì)2:若性質(zhì)1的條件都滿足，并且經(jīng)過次迭代才求到極小點(diǎn)，則。(2)DFP算法考慮如下形式的校正公式由于校正公式必須滿足擬牛頓條件，于是有：取，再令，于是有：，校正公式為：DFP算法性質(zhì)：性質(zhì)1:設(shè)將DFP法施用于具有對稱正定矩陣的二次函數(shù)，如果初始矩陣是對稱的。迭代點(diǎn)是互異的。那么