無約束優(yōu)化方法

1、無約束優(yōu)化方法1可以利用極值定義，將上式變成求以下方程無約束優(yōu)化問題是：求n維設(shè)計(jì)變量使目標(biāo)函數(shù) ，而對(duì) 沒有任何限制條件。2 本章介紹的是數(shù)值方法。其中最常用的是搜索方法，即給定初始點(diǎn)和搜索方向，沿著該方向?qū)ふ易顑?yōu)點(diǎn)。搜索方向的構(gòu)成是關(guān)鍵。3無約束極小算法的粗框圖4 根據(jù)構(gòu)成搜索方向所使用的信息性質(zhì)的不同，無約束優(yōu)化方法可以分成兩類。一類是利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)的無約束優(yōu)化方法，另一類是指利用目標(biāo)函數(shù)值的無約束優(yōu)化方法。5最速下降法 最速下降法是以負(fù)梯度方向作為搜索方向，所以又稱梯度法。 根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得6相鄰兩個(gè)迭代點(diǎn)上的函數(shù)梯度方向互相垂直7求目

2、標(biāo)函數(shù) 的極小點(diǎn)。解 取初始值則初始點(diǎn)處函數(shù)值及梯度分別為沿負(fù)梯度方向進(jìn)行一維搜索，有8為一維搜索最佳步長(zhǎng)，應(yīng)滿足極值必要條件從而算出一維搜索最佳步長(zhǎng)及第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值9經(jīng)過10次迭代，得到最優(yōu)值10若將上例的目標(biāo)函數(shù)引入變換其等值線就由一族橢圓變成一族同心圓，仍從 即 開始尋優(yōu)此時(shí)有11沿負(fù)梯度 方向進(jìn)行一維搜索，有為一維搜索最佳步長(zhǎng)，可由極值條件算得12得到第一次迭代的結(jié)果就是最優(yōu)解 最速下降法的收斂速度與變量的尺度關(guān)系很大，下面是最速下降收斂速度的估計(jì)式式中 的海賽矩陣最大特征值上界； 其最小特征值下屆。13一、特征值與特征向量的定義定義2.1 設(shè)A為復(fù)數(shù)域上的n階矩陣，若存

3、在復(fù)數(shù) 和非零n維列向量X使得 則稱數(shù) 為A的一個(gè)特征值，X為A的屬于（或?qū)?yīng)于）特征值 的特征向量。由（2-1）式得由此可見，特征值 是使齊次方程組有非零解 的 的值。方程組（2-3）有非零解的充要條件是14 對(duì)于等值線為橢圓的二次型函數(shù) ，其海賽矩陣兩個(gè)特征值分別為 。因此可見等值線為橢圓的長(zhǎng)短軸相差越大，收斂就越慢。 兩個(gè)特征值相等 ，因此代入（4-4），有得即經(jīng)過一次迭代便可到達(dá)極值點(diǎn)。1516 最速下降法是一個(gè)求解極值問題的古老算法，早在1847年就已由柯西（Cauchy）提出。此法直觀、簡(jiǎn)單。由于它采用了函數(shù)的負(fù)梯度方向作為下一步的搜索方向，所以收斂速度較慢，越是接近極值點(diǎn)收斂越慢

4、，這就是它的主要缺點(diǎn)。應(yīng)用最速下降法可以使頭幾次迭代的收斂速度很快，所以它可與其他方法配合使用。17牛頓型方法一維情況下牛頓迭代公式多維情況下牛頓迭代公式根據(jù)極值的必要條件，得：18 對(duì)二次函數(shù)來說，上述的泰勒展開式不是近似的，而是精確的。海森矩陣是一個(gè)常數(shù)陣。無論從任何點(diǎn)出發(fā)，只需一步就可找到極小點(diǎn)。 二次收斂的概念：如果某一種迭代方法能夠使二次型函數(shù)在有限次迭代內(nèi)達(dá)到極小點(diǎn)，則稱此迭代方法是二次收斂的。 從牛頓法迭代公式的推演中可以看到，迭代點(diǎn)的位置是按照極值條件去訂的，其中并未含有沿下降方向搜索的概念。因此對(duì)于非二次函數(shù)，如果采用上述牛頓法迭代公式，有時(shí)會(huì)使函數(shù)值上升，為了解決這個(gè)問題，

5、提出“阻尼牛頓法”19其中： 為沿牛頓方向進(jìn)行一維搜索的最佳步長(zhǎng)，可稱為阻尼因子。可通過如下極小化過程求得 這樣，原來的牛頓法就相當(dāng)于阻尼牛頓法的步長(zhǎng)因子 取成固定值1的情況。由于阻尼牛頓法每次迭代都在牛頓方向上進(jìn)行一維搜索，這就避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法二次收斂的特性，而對(duì)初始點(diǎn)的選取并沒有苛刻的要求。20阻尼牛頓法的計(jì)算步驟如下：1）給定初始點(diǎn) ，收斂精度 ，置 。2）計(jì)算 和 。3）求 ，其中 為沿 進(jìn)行一維搜索的最佳步長(zhǎng)。4）檢查收斂精度。若 則 ，停機(jī)；否則，置 ，返回到2繼續(xù)進(jìn)行搜索。2122 牛頓法和阻尼牛頓法統(tǒng)稱牛頓型方法。 這類方法的主要缺點(diǎn)是每次迭代都要

6、計(jì)算函數(shù)的二階導(dǎo)數(shù)矩陣，并對(duì)該矩陣求逆，當(dāng)維數(shù)高時(shí)工作量更大。 針對(duì)上述的梯度法收斂速度慢，提出收斂速度更快的共軛梯度。 針對(duì)牛頓法的缺點(diǎn)提出了變尺度法。23共軛方向及共軛方向法一、共軛方向的概念 我們先以二次函數(shù)為例介紹共軛方向的有關(guān)算法，然后推廣到一般的目標(biāo)函數(shù)中去。共軛方向的概念是在研究二次函數(shù)（G為對(duì)稱正定矩陣）時(shí)引出的。定義 設(shè)G為nn對(duì)稱正定矩陣，若n維空間中有m個(gè)非零向量 滿足（4-11）則稱 對(duì)G共軛，或稱是G的共軛方向。24 即向量 互相正交。由此可見，共軛概念是正交概念的推廣，正交是共軛的特例。性質(zhì)1 若非零向量系 是對(duì)G共軛的，則這m個(gè)向量是線性無關(guān)的。性質(zhì)3 從任意初始

7、點(diǎn) 出發(fā)，順次沿n個(gè)G的共軛方向 進(jìn)行一維搜索，最多經(jīng)過n次迭代可以找到由式（4-8）所表示的二次函數(shù) 極小點(diǎn) 。此性質(zhì)表明這種迭代方法具有二次收斂性。當(dāng)G=I（單位矩陣）時(shí)，式（4-11）變成性質(zhì)2 在n為空間中互相共軛的非零向量的個(gè)數(shù)不超過n。25 為了避免搜索鋸齒的出現(xiàn)，我們?nèi)∠乱淮蔚姆较蛑敝笜O小點(diǎn)。方向上的最佳步長(zhǎng)。那么這樣的 方向應(yīng)該滿足什么條件？將等式兩邊同是左乘 ，又由于 和 對(duì)G是共軛方向。26共軛方向法27 共軛方向法程序框圖如下圖所示。提供共軛向量系的方法有許多種，從而形成各種具體的共軛方向法，如共軛梯度法，鮑威爾（Powell）法等。這些方法將在下面幾節(jié)中予以討論。這里首先介紹格拉姆斯密特（Gram-Schmidt）向量系共軛化方法，它是格拉姆斯密特向量系正交化方法的推廣。28293031 上述算法是針對(duì)二次函數(shù)的，一般也可以用于非二次函數(shù)。為了避免海森矩陣計(jì)算，可以采用更加有效的構(gòu)建共軛向量的方法。32共軛梯度法 共軛梯度法是共軛向量法的一種，因?yàn)樵谠摲椒ㄖ忻總€(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度構(gòu)造出來的，稱共軛梯度法。 首先考慮共軛方向與梯度的關(guān)系。33343536373839 沿著這些共軛方向一直搜索下去，直到最后迭代點(diǎn)處梯度的模小于給