第6章 無約束問題的優(yōu)化方法

1、72第6章無約束問題的優(yōu)化方法無約束問題的優(yōu)化方法6.1最速下降法和牛頓法最速下降法和牛頓法6.1.1最速下降法的基本原理、計(jì)算步驟和特點(diǎn)最速下降法的基本原理、計(jì)算步驟和特點(diǎn)基本原理：考慮無約束問題nRxxf?)(min從某一點(diǎn)出發(fā)，選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向，可以盡快達(dá)到極小點(diǎn)1847年法國(guó)數(shù)學(xué)家Cauchy提出了最速下降法后來，Curry等人作了進(jìn)一步研究最速下降方向是目標(biāo)函數(shù)的負(fù)梯度方向：)(xfd???最速下降法的迭代公式

2、：)()()1(kkkkdxx????取為在點(diǎn)處的最速下降方向：)(kd)(kx)()()(kkxfd???為進(jìn)行一維搜索的步長(zhǎng)，滿足：k?)(min)()()(0)()(kkkkkdxfdxf???????計(jì)算步驟：(l)給定初點(diǎn)，允許誤差，置.nRx?)1(0??1?k(2)計(jì)算搜索方向.)()()(kkxfd???(3)若，則停止計(jì)算；否則，從出發(fā)，沿進(jìn)行一維搜索，求，使??)(kd)(kx)(kdk?)(min)()()(0)(

3、)(kkkkkdxfdxf???????(4)令置，轉(zhuǎn)步驟（2）.)()()1(kkkkdxx????1:??kk例1解問題22212)(minxxxf??初點(diǎn)，.（最優(yōu)解）Tx)11()1(?101??Tx)00(?第1次迭代：目標(biāo)函數(shù)在點(diǎn)處的梯度x????????2124)(xxxf令搜索方向????????????24)()1()1(xfd74定理1:設(shè)存在連續(xù)二階偏導(dǎo)數(shù)，是局部極小點(diǎn)，Hesse矩陣的最小)(xfx)(2xf?特

4、征值，最大特征值為，算法產(chǎn)生的序列收斂于點(diǎn)，則目標(biāo)函數(shù)值的序列0?aA)(kxx以不大于的收斂比線性地收斂于.)()(kxf2????????aAaA)(xf最速下降法存在鋸齒現(xiàn)象：從局部看，最速下降方向確是函數(shù)值下降最快的方向從全局看，由于鋸齒現(xiàn)象的影響，即使向著極小點(diǎn)移近不太大的距離，也要經(jīng)歷不小的彎路，使收斂速率大為減慢注1：最速下降法并不是收斂最快的方法，從全局看，它的收斂是比較慢的注2：最速下降法一般適用于計(jì)算過程的前期迭代或

5、作為間插步驟當(dāng)接近極小點(diǎn)時(shí)，使用最速下降法達(dá)到迭代終止，這樣做并不有利6.1.2牛頓法的基本原理、計(jì)算步驟和特點(diǎn)牛頓法的基本原理、計(jì)算步驟和特點(diǎn)1.牛頓法在點(diǎn)的二階Tayl展開為)(xf)(kx))(()(21)()()()()()()(2)()()()(kkTkkTkkxxxfxxxxxfxfxxf??????????求的平穩(wěn)點(diǎn)，令即)(x?0)(?x?(1)0))(()()()(2)(?????kkkxxxfxf設(shè)可逆，得到牛頓法的