使用導(dǎo)數(shù)的最優(yōu)化方法

第10章使用導(dǎo)數(shù)的最優(yōu)化方法無(wú)約束最優(yōu)化問(wèn)題2.最速下降法4.共軛梯度法5.擬牛頓法3.牛頓法現(xiàn)在是1頁(yè)\一共有74頁(yè)\編輯于星期三一.無(wú)約束最優(yōu)化問(wèn)題

無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題的求解方法分為解析法和直接法兩類(lèi)。解析法需要計(jì)算函數(shù)的梯度，利用函數(shù)的解析性質(zhì)構(gòu)造迭代公式使之收斂到最優(yōu)解。本節(jié)介紹最速下降法、共軛梯度法、牛頓法、變尺度法等解析方法

直接法僅通過(guò)比較目標(biāo)函數(shù)值的大小來(lái)移動(dòng)迭代點(diǎn)。下一章主要介紹模式搜索法等直接方法?，F(xiàn)在是2頁(yè)\一共有74頁(yè)\編輯于星期三

無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題的求解方法分為解析法和直接法兩類(lèi)。

一般來(lái)說(shuō)，無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題的求解是通過(guò)一系列一維搜索來(lái)實(shí)現(xiàn)。因此，如何選擇搜索方向是解無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題的核心問(wèn)題，搜索方向的不同選擇，形成不同的求解方法。本章主要介紹解析法;另一類(lèi)只用到目標(biāo)函數(shù)值,不必計(jì)算導(dǎo)數(shù),通常稱(chēng)為直接方法,放在第11章討論.現(xiàn)在是3頁(yè)\一共有74頁(yè)\編輯于星期三本章考慮如下的下降算法：主要介紹最速下降法、牛頓法，共軛梯度法，擬牛頓法等現(xiàn)在是4頁(yè)\一共有74頁(yè)\編輯于星期三10.1最速下降法10.1.1最速下降方向

考慮無(wú)約束問(wèn)題(6.1.2)其中函數(shù)具有一階連續(xù)偏導(dǎo)數(shù).

人們?cè)谔幚磉@類(lèi)問(wèn)題時(shí),總希望從某一點(diǎn)出發(fā),選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向,以利于盡快達(dá)到極小點(diǎn).正是基于這樣一種愿望,早在1847年法國(guó)著名數(shù)學(xué)家Cauchy提出了最速下降法.后來(lái),Curry等人作了進(jìn)一步的研究.現(xiàn)在最速下降法已經(jīng)成為眾所周知的一種最基本的算法,它對(duì)其他算法的研究也很有啟發(fā)作用,因此在最優(yōu)化方法中占有重要地位.下面我們先來(lái)討論怎樣選擇最速下降方向.

現(xiàn)在是5頁(yè)\一共有74頁(yè)\編輯于星期三人們?cè)谔幚磉@類(lèi)問(wèn)題時(shí),總希望從某一點(diǎn)出發(fā),選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向,以利于盡快達(dá)到極小點(diǎn).正是基于這樣一種愿望,早在1847年法國(guó)著名數(shù)學(xué)家Cauchy提出了最速下降法.后來(lái),Curry等人作了進(jìn)一步的研究.現(xiàn)在最速下降法已經(jīng)成為眾所周知的一種最基本的算法,它對(duì)其他算法的研究也很有啟發(fā)作用,因此在最優(yōu)化方法中占有重要地位.下面我們先來(lái)討論怎樣選擇最速下降方向.

我們知道,函數(shù)在點(diǎn)處沿方向的變化率可用方向?qū)?shù)來(lái)表達(dá),對(duì)于可微函數(shù),方向?qū)?shù)等于梯度與方向的內(nèi)積,即(6.1.2)因此,求函數(shù)在點(diǎn)處的下降最快的方向,可歸結(jié)為求解下列非線(xiàn)性規(guī)劃:(6.1.3)現(xiàn)在是6頁(yè)\一共有74頁(yè)\編輯于星期三根據(jù)Schwartz不等式,有去掉絕對(duì)值符號(hào),可以得到(6.1.4)由上式可知,當(dāng)(6.1.5)時(shí)等號(hào)成立.因此,在點(diǎn)處沿(6.1.5)所定義的方向變化率最小,即負(fù)梯度方向?yàn)樽钏傧陆捣较?

這里要特別指出,在不同尺度下最速下降方向是不同的.前面定義的最速下降方向,是在向量的毆氏范數(shù)不大于1的限制得到的,屬于毆氏度量意義下的最速下降方向.如果改用其他度量,比現(xiàn)在是7頁(yè)\一共有74頁(yè)\編輯于星期三如,設(shè)為對(duì)稱(chēng)正定矩陣,在向量的范數(shù)不大于1的限制下,極小化,則得到的最速下降方向與前者不同.

10.1.2最速下降算法

最速下降法的迭代公式是(10.1.6)其中是從出發(fā)的搜索方向,這里取在點(diǎn)處的最速下降方向,即

是從出發(fā)沿方向進(jìn)行一維搜索的步長(zhǎng),即滿(mǎn)足(10.1.11)現(xiàn)在是8頁(yè)\一共有74頁(yè)\編輯于星期三

計(jì)算步驟如下:1.給定初點(diǎn),允許誤差,置.2.計(jì)算搜索方向3.若,則停止計(jì)算;否則,從出發(fā),沿進(jìn)行一維搜索,求,使4.令,置,轉(zhuǎn)步2..

例10.1.1

用最速下降法解下列問(wèn)題:現(xiàn)在是9頁(yè)\一共有74頁(yè)\編輯于星期三解：第二次迭代：現(xiàn)在是10頁(yè)\一共有74頁(yè)\編輯于星期三第三次迭代：現(xiàn)在是11頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是12頁(yè)\一共有74頁(yè)\編輯于星期三在最速下降法的一位搜素中即在最速下降法中相鄰兩次搜索方向是正交的?，F(xiàn)在是13頁(yè)\一共有74頁(yè)\編輯于星期三對(duì)于二次嚴(yán)格凸函數(shù)其中A為n維對(duì)稱(chēng)正定矩陣可以求出步長(zhǎng)因子k（本章習(xí)題7）現(xiàn)在是14頁(yè)\一共有74頁(yè)\編輯于星期三鋸齒現(xiàn)象

最速下降法的迭代點(diǎn)在向極小點(diǎn)靠近的過(guò)程中，走的是曲折的路線(xiàn)：后一次搜索方向d(k+1)與前一次搜索方向d(k)總是相互垂直的，稱(chēng)它為鋸齒現(xiàn)象。這一點(diǎn)在前面的例題中已得到驗(yàn)證。除極特殊的目標(biāo)函數(shù)（如等值面為球面的函數(shù)）和極特殊的初始點(diǎn)外，這種現(xiàn)象一般都要發(fā)生。最速下降法的收斂性現(xiàn)在是15頁(yè)\一共有74頁(yè)\編輯于星期三

從直觀上可以看到，在遠(yuǎn)離極小點(diǎn)的地方，每次迭代都有可能使目標(biāo)函數(shù)值有較多的下降，但在接近極小點(diǎn)的地方，由于鋸齒現(xiàn)象，每次迭代行進(jìn)的距離開(kāi)始逐漸變小。因而收斂速度不快。

已有結(jié)論表明，最速下降法對(duì)于正定二次函數(shù)關(guān)于任意初始點(diǎn)都是收斂的(定理10.1.2)，而且恰好是線(xiàn)性收斂的?，F(xiàn)在是16頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是17頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是18頁(yè)\一共有74頁(yè)\編輯于星期三§10.2牛頓法

6.2.1牛頓法

設(shè)是二次可微實(shí)函數(shù),.又設(shè)是的極小點(diǎn)的一個(gè)估計(jì),我們把在展成Taylor級(jí)數(shù),并取二階近似:其中是在處的Hessian矩陣.為求的平穩(wěn)點(diǎn),令即(10.2.1)現(xiàn)在是19頁(yè)\一共有74頁(yè)\編輯于星期三設(shè)可逆,有(10.2.1)得到牛頓法的迭代公式(10.2.2)其中是Hessian矩陣的逆矩陣.這樣,知道后,算出在這一點(diǎn)處目標(biāo)函數(shù)的梯度和Hessian矩陣的逆,代人(10.2.2),便得到后繼點(diǎn),用代替,再用(10.2.2)計(jì)算,又得到的后繼點(diǎn).依此類(lèi)推,產(chǎn)生序列.在適當(dāng)?shù)臈l件下,這個(gè)序列收斂.

現(xiàn)在是20頁(yè)\一共有74頁(yè)\編輯于星期三則牛頓法產(chǎn)生的序列收斂于.

實(shí)際上,當(dāng)牛頓法收斂時(shí),有下列關(guān)系:其中C是某個(gè)常數(shù).因此,牛頓法至少2級(jí)收斂,參看文獻(xiàn)[19].可見(jiàn)牛頓法的收斂速率是很快的.現(xiàn)在是21頁(yè)\一共有74頁(yè)\編輯于星期三例

用牛頓法解下列問(wèn)題:

我們?nèi)〕觞c(diǎn)解：第2次迭代：現(xiàn)在是22頁(yè)\一共有74頁(yè)\編輯于星期三第2次迭代：繼續(xù)迭代，得到最終收斂到最優(yōu)解x*=(1,0)T現(xiàn)在是23頁(yè)\一共有74頁(yè)\編輯于星期三我們先用極值條件求解.令下面用牛頓法求解.任取初始點(diǎn)x(1)

,根據(jù)牛頓法的迭代公式：特別地,對(duì)于二次凸函數(shù),用牛頓法求解,經(jīng)1次迭代即達(dá)極小點(diǎn).設(shè)有二次凸函數(shù)其中A是對(duì)稱(chēng)正定矩陣。求迭代點(diǎn)x(2)

即1次迭代達(dá)到極小點(diǎn).現(xiàn)在是24頁(yè)\一共有74頁(yè)\編輯于星期三不一定是下降方向,經(jīng)迭代,目標(biāo)函數(shù)值可能上升.此外,即使目標(biāo)函數(shù)值下降,得到的點(diǎn)也不一定是沿牛頓方向的最好點(diǎn)或極小點(diǎn).因此,人們對(duì)牛頓法進(jìn)行修正,提出了阻尼牛頓法.

值得注意,當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時(shí),牛頓法可能不收斂.原因之一,牛頓方向

以后還會(huì)遇到一些算法,把它們用于二次凸函數(shù)時(shí),類(lèi)似于牛頓法,經(jīng)有限次迭代必達(dá)到極小點(diǎn).這種性質(zhì)稱(chēng)為二次終止性.對(duì)于二次凸函數(shù),用牛頓法求解,經(jīng)1次迭代即達(dá)極小點(diǎn)現(xiàn)在是25頁(yè)\一共有74頁(yè)\編輯于星期三10.2.2阻尼牛頓法

阻尼牛頓法與原始牛頓法的區(qū)別在于增加了沿牛頓方向的一維搜索,其迭代公式是(6.2.6)其中為牛頓方向,是由一維搜索得到的步長(zhǎng),即滿(mǎn)足

阻尼牛頓法的計(jì)算步驟如下:1.給定初始點(diǎn),允許誤差,置.2.計(jì)算現(xiàn)在是26頁(yè)\一共有74頁(yè)\編輯于星期三3.若,則停止迭代;否則,令4.從出發(fā),沿方向作一維搜索:令.5.置,轉(zhuǎn)步2..

由于阻尼牛頓法含有一維搜索,因此每次迭代目標(biāo)函數(shù)值一般有所下降(決不會(huì)上升).可以證明,阻尼牛頓法在適當(dāng)?shù)臈l件下具有全局收斂性,且為2級(jí)收斂.現(xiàn)在是27頁(yè)\一共有74頁(yè)\編輯于星期三10.3、共軛梯度法現(xiàn)在是28頁(yè)\一共有74頁(yè)\編輯于星期三10.3.1共軛方向法1.共軛方向和共軛方向法共軛是正交的推廣?，F(xiàn)在是29頁(yè)\一共有74頁(yè)\編輯于星期三幾何意義現(xiàn)在是30頁(yè)\一共有74頁(yè)\編輯于星期三幾何意義現(xiàn)在是31頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是32頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是33頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是34頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是35頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是36頁(yè)\一共有74頁(yè)\編輯于星期三推論：現(xiàn)在是37頁(yè)\一共有74頁(yè)\編輯于星期三共軛方向法現(xiàn)在是38頁(yè)\一共有74頁(yè)\編輯于星期三對(duì)于上述正交方向法，它是下降算法嗎？不難得到：故正交方向法，它是下降算法?，F(xiàn)在是39頁(yè)\一共有74頁(yè)\編輯于星期三可由一組線(xiàn)性無(wú)關(guān)向量組，類(lèi)似于schmidt正交化過(guò)程，現(xiàn)在是40頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是41頁(yè)\一共有74頁(yè)\編輯于星期三§10.3共軛梯度法

10.3.2共軛梯度法

共軛梯度法最初由Hesteness和Stiefel于1952年為求解線(xiàn)性方程組而提出.后來(lái),人們把這種方法用于求解無(wú)約束最優(yōu)化問(wèn)題,使之成為一種重要的最優(yōu)化方法.

下面,重點(diǎn)介紹Fletcher-Reeves共軛梯度法,簡(jiǎn)稱(chēng)FR法.

共軛梯度法的基本思想是把共軛性與最速下降方法相結(jié)合,利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向,并沿這組方向進(jìn)行搜索,求出目標(biāo)函數(shù)的極小點(diǎn).根據(jù)共軛方向的基本性質(zhì),這種方法具有二次終止性.

我們先討論對(duì)于二次凸函數(shù)的共軛梯度法,然后再把這種方法推廣到極小化一般函數(shù)的情形.現(xiàn)在是42頁(yè)\一共有74頁(yè)\編輯于星期三.共軛梯度法

如何選取一組共軛方向？以下分析算法的具體步驟。我們先討論對(duì)于二次凸函數(shù)的共軛梯度法,然后再把這種方法推廣到極小化一般函數(shù)的情形現(xiàn)在是43頁(yè)\一共有74頁(yè)\編輯于星期三初始搜索方向?yàn)樽钏傧陆捣较颥F(xiàn)在是44頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是45頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是46頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是47頁(yè)\一共有74頁(yè)\編輯于星期三常用兩個(gè)公式:著名的FR和PPR公式現(xiàn)在是48頁(yè)\一共有74頁(yè)\編輯于星期三求解二次凸規(guī)劃的FR共軛梯度法求解二次凸規(guī)劃的FR共軛梯度法迭代多少次才可以達(dá)到最優(yōu)解？現(xiàn)在是49頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是50頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是51頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是52頁(yè)\一共有74頁(yè)\編輯于星期三.用于一般函數(shù)的共軛梯度法現(xiàn)在是53頁(yè)\一共有74頁(yè)\編輯于星期三.用于一般函數(shù)的共軛梯度法現(xiàn)在是54頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是55頁(yè)\一共有74頁(yè)\編輯于星期三§10.3共軛梯度法

10.3.2共軛梯度法

共軛梯度法最初由Hesteness和Stiefel于1952年為求解線(xiàn)性方程組而提出.后來(lái),人們把這種方法用于求解無(wú)約束最優(yōu)化問(wèn)題,使之成為一種重要的最優(yōu)化方法.

下面,重點(diǎn)介紹Fletcher-Reeves共軛梯度法,簡(jiǎn)稱(chēng)FR法.

共軛梯度法的基本思想是把共軛性與最速下降方法相結(jié)合,利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向,并沿這組方向進(jìn)行搜索,求出目標(biāo)函數(shù)的極小點(diǎn).根據(jù)共軛方向的基本性質(zhì),這種方法具有二次終止性.

我們先討論對(duì)于二次凸函數(shù)的共軛梯度法,然后再把這種方法推廣到極小化一般函數(shù)的情形.

考慮問(wèn)題現(xiàn)在是56頁(yè)\一共有74頁(yè)\編輯于星期三其中,是對(duì)稱(chēng)正定矩陣,是常數(shù).

具體求解方法如下:

首先,任意給定一個(gè)初始點(diǎn),計(jì)算出目標(biāo)函數(shù)在這點(diǎn)的梯度,若,則停止計(jì)算;否則,令(10.3.12)沿方向搜索,得到點(diǎn).計(jì)算在處的梯度,若,則利用和構(gòu)造第2個(gè)搜索方向,再沿搜索.

一般地,若已知點(diǎn)和搜索方向,則從出發(fā),沿進(jìn)行搜索,得到(10.3.14)現(xiàn)在是57頁(yè)\一共有74頁(yè)\編輯于星期三其中步長(zhǎng)滿(mǎn)足我們可以求出的顯式表達(dá).令求的極小點(diǎn),令(10.3.15)根據(jù)二次函數(shù)的梯度的表達(dá)式,(6.3.15)即(10.3.16)現(xiàn)在是58頁(yè)\一共有74頁(yè)\編輯于星期三由(6.3.16)得到(10.3.17)

計(jì)算在處的梯度.若,則停止計(jì)算;否則,用共軛.按此設(shè)想,令(10.3.18)上式兩端左乘,并令由此得到(10.3.19)現(xiàn)在是59頁(yè)\一共有74頁(yè)\編輯于星期三

再?gòu)某霭l(fā),沿方向搜索.綜上分析，在第１個(gè)搜索方向取負(fù)梯度的前提下,重復(fù)使用公式(10.3.14),(10.3.17),(10.3.18)和(10.3.19),就能伴隨計(jì)算點(diǎn)的增加,構(gòu)造出一組搜索方向.下面將要證明,這組方向是關(guān)于共軛的.因此,上述方法具有二次終止性.

定理10.3.3

對(duì)于正定二次函數(shù)(10.3.12),具有精確一維搜索的Fletcher-Reeves法在次一維搜索后即終止，并且對(duì)所有,下列關(guān)系成立:現(xiàn)在是60頁(yè)\一共有74頁(yè)\編輯于星期三

例6.3.1

考慮下列問(wèn)題：

取初始點(diǎn)和初始搜索方向分別為

在FR法中，初始搜索方向必須取最速下降方向，這一點(diǎn)絕不可忽視。

對(duì)于二次凸函數(shù)，F(xiàn)R法的計(jì)算步驟如下：1.給定初始點(diǎn),置.現(xiàn)在是61頁(yè)\一共有74頁(yè)\編輯于星期三2.計(jì)算,若,則停止計(jì)算,得點(diǎn);否則,進(jìn)行下一步.3.構(gòu)造搜索方向,令其中,當(dāng)時(shí),,當(dāng)時(shí),按公式計(jì)算因子.4.令其中按公式(6.3.17)計(jì)算步長(zhǎng)現(xiàn)在是62頁(yè)\一共有74頁(yè)\編輯于星期三5.若,則停止計(jì)算,得點(diǎn);否則,置,返回步2..

由現(xiàn)在是63頁(yè)\一共有74頁(yè)\編輯于星期三§10.4擬牛頓法

6.4.1擬牛頓條件前面介紹了牛頓法,它的突出優(yōu)點(diǎn)是收斂很快.但是,運(yùn)用牛頓法需要計(jì)算二階便導(dǎo)數(shù),而且目標(biāo)函數(shù)的Hessian矩陣可能非正定.為了克服牛頓法的缺點(diǎn),人們提出了擬牛頓法.它的基本思想是用不包含二階導(dǎo)數(shù)的矩陣近似牛頓法中的Hessian矩陣的逆矩陣.現(xiàn)在是64頁(yè)\一共有74頁(yè)\編輯于星期三Newton法的優(yōu)缺點(diǎn)都很突出。

優(yōu)點(diǎn)：高收斂速度（二階收斂）；

缺點(diǎn)：對(duì)初始點(diǎn)、目標(biāo)函數(shù)要求高，計(jì)算量、存儲(chǔ)量大（需要計(jì)算、存儲(chǔ)Hesse矩陣及其逆）。

擬Newton法是模擬Newton法給出的一個(gè)保優(yōu)去劣的算法

擬Newton法是效果很好的一大類(lèi)方法。它當(dāng)中的DFP算法和BFGS算法是直到目前為止在不用Hesse矩陣的方法中的最好方法?，F(xiàn)在是65頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是66頁(yè)\一共有74頁(yè)\編輯于星期三現(xiàn)在是67頁(yè)\一共有74頁(yè)\編輯于星期三由于構(gòu)造近似矩陣的方法不同,因而出現(xiàn)不同的擬牛頓法.經(jīng)理論證明和實(shí)踐檢驗(yàn),擬牛頓法已經(jīng)成為一類(lèi)公認(rèn)的比較有效的算法下面分析怎樣構(gòu)造近似矩陣并用它取代牛頓法中的Hessian矩陣的逆.前面已經(jīng)給出牛頓法的迭代公式,即

k是從xk出發(fā)沿牛頓方向搜索的最優(yōu)步長(zhǎng).現(xiàn)在是68頁(yè)\一共有74頁(yè)\編輯于星期三

設(shè)在第次迭代后,得到點(diǎn),我們將目標(biāo)函數(shù)在點(diǎn)展成Taylor級(jí)數(shù),并取二階近似,得到由此可知,在附近有令,則記作現(xiàn)在是69頁(yè)\一共有74頁(yè)\編輯于星期三(10.4.3)(10.4.4)則有(10.4.5)又設(shè)Hessian矩陣可逆,則(10.4.6)這樣,計(jì)算出后,可以根據(jù)(10.4.6)估計(jì)在處