無(wú)約束非線性規(guī)劃

關(guān)于無(wú)約束非線性規(guī)劃第1頁(yè)，共139頁(yè)，2023年，2月20日，星期四2.1非線性函數(shù)和非線性規(guī)劃的概念線性函數(shù):(1)f(kx)=kf(x)(2)f(x1+x2)=f(x1)+f(x2)則非線性函數(shù)就是不滿足以上兩個(gè)條件的函數(shù)．非線性規(guī)劃：如果目標(biāo)函數(shù)或約束條件中，有一個(gè)或多個(gè)是變量的非線性函數(shù)，就稱為非線性規(guī)劃．第2頁(yè)，共139頁(yè)，2023年，2月20日，星期四非線性規(guī)劃問(wèn)題例1

曲線的最優(yōu)擬合問(wèn)題第3頁(yè)，共139頁(yè)，2023年，2月20日，星期四例2構(gòu)件容積問(wèn)題第4頁(yè)，共139頁(yè)，2023年，2月20日，星期四非線性規(guī)劃問(wèn)題例3第5頁(yè)，共139頁(yè)，2023年，2月20日，星期四非線性規(guī)劃問(wèn)題例3第6頁(yè)，共139頁(yè)，2023年，2月20日，星期四非線性規(guī)劃通常情況下，目標(biāo)函數(shù)f(x)和約束條件hi(X)和gi(X)為自變量Ｘ的非線性函數(shù)第7頁(yè)，共139頁(yè)，2023年，2月20日，星期四非線性規(guī)劃ULP的可行解或可行點(diǎn)約束集或可行域第8頁(yè)，共139頁(yè)，2023年，2月20日，星期四向量化表示當(dāng)p=0,q=0時(shí)，稱為無(wú)約束非線性規(guī)劃或者無(wú)約束最優(yōu)化問(wèn)題。否則，稱為約束非線性規(guī)劃或者約束最優(yōu)化問(wèn)題。第9頁(yè)，共139頁(yè)，2023年，2月20日，星期四最優(yōu)解和極小點(diǎn)第10頁(yè)，共139頁(yè)，2023年，2月20日，星期四最優(yōu)解和極小點(diǎn)第11頁(yè)，共139頁(yè)，2023年，2月20日，星期四極值存在的條件１必要條件：設(shè)Ｒ是n維歐氏空間的某一區(qū)域，f(X)為定義在Ｒ上的實(shí)值函數(shù)，Ｘ＊是區(qū)域Ｒ的內(nèi)點(diǎn)，若f(Ｘ）在Ｘ＊處可微，且在該點(diǎn)取得局部極小值，則必有或第12頁(yè)，共139頁(yè)，2023年，2月20日，星期四極值存在的條件其中，為函數(shù)f(x)在Ｘ＊處的梯度，梯度的方向?yàn)閒(X)的等值面（等值線）的法線方向，沿這個(gè)方向函數(shù)值增加最快．滿足上式的點(diǎn)稱為駐點(diǎn)，在區(qū)域內(nèi)部，極值點(diǎn)必為駐點(diǎn)；但駐點(diǎn)不一定是極值點(diǎn)．第13頁(yè)，共139頁(yè)，2023年，2月20日，星期四14二次型二次型是X=(x1,x2,…,xn)T的二次齊次函數(shù)：aij=aji,A為n*n對(duì)稱矩陣。若A的所有元素均為實(shí)數(shù)，則為實(shí)二次型。一個(gè)二次型唯一對(duì)應(yīng)一個(gè)對(duì)稱矩陣，反之，一個(gè)對(duì)稱矩陣也唯一確定一個(gè)二次型。二次型（對(duì)稱矩陣）正定，負(fù)定，不定。半正定，半負(fù)定。第14頁(yè)，共139頁(yè)，2023年，2月20日，星期四15二次型二次型正定的充要條件，是它的矩陣的左上角各階主子式都大于零。二次型負(fù)定的充要條件，是它的矩陣的左上角各階主子式都負(fù)、正相間。例：判定正負(fù)性。第15頁(yè)，共139頁(yè)，2023年，2月20日，星期四極值存在的條件２充分條件：設(shè)Ｒ是n維歐氏空間的某一區(qū)域，f(X)為定義在Ｒ上的實(shí)值函數(shù)，Ｘ＊是區(qū)域Ｒ的內(nèi)點(diǎn)，f(Ｘ）在Ｒ上二次連續(xù)可微，若f(Ｘ）在Ｘ＊且處滿足（5．１）或（5．２）式，且對(duì)任何非零矢量均有則f(x)在Ｘ取嚴(yán)格局部極小值，此處Ｈ（x*)為f(x)在點(diǎn)Ｘ＊處的海賽（Hesse)矩陣．第16頁(yè)，共139頁(yè)，2023年，2月20日，星期四極值存在的條件此處Ｈ（x*)為f(x)在點(diǎn)Ｘ＊處的海賽（Hesse)矩陣．第17頁(yè)，共139頁(yè)，2023年，2月20日，星期四極值存在的條件例１求目標(biāo)函數(shù)的梯度和Hesse矩陣解:因?yàn)?所以第18頁(yè)，共139頁(yè)，2023年，2月20日，星期四極值存在的條件又因?yàn)樗约礊镠esse矩陣第19頁(yè)，共139頁(yè)，2023年，2月20日，星期四極值存在的條件例2試研究函數(shù)f(x1,x2)=x22-x1２的駐點(diǎn)．解：令得（０，０）點(diǎn)為駐點(diǎn)，x1=0是一無(wú)函數(shù)f(x1,0)=-x12的極大點(diǎn)，而x2=0卻是一元函數(shù)f(0,x2)=x22的極小點(diǎn)，即：故駐點(diǎn)（０，０）不是極值點(diǎn)，而是一個(gè)鞍點(diǎn)第20頁(yè)，共139頁(yè)，2023年，2月20日，星期四極值存在的條件例3試求函數(shù)f(x1,x2)=2x12-8x1+2x2２-4x2+20的極值和極值點(diǎn)．解：令得（2,1）點(diǎn)為駐點(diǎn)第21頁(yè)，共139頁(yè)，2023年，2月20日，星期四極值存在的條件其海賽矩陣之行列式可知（2,1）點(diǎn)為極小點(diǎn),其極小值為:第22頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸函數(shù)和凸規(guī)劃凸函數(shù)及其性質(zhì)凸規(guī)劃及其性質(zhì)第23頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸函數(shù)及其性質(zhì)第24頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸函數(shù)的性質(zhì)第25頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸函數(shù)的判定第26頁(yè)，共139頁(yè)，2023年，2月20日，星期四第27頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸函數(shù)的判定例4判定下述函數(shù)是凸函數(shù)還是凹函數(shù)解:因?yàn)槠浜Ｙ愱嚨男辛惺綖椋汗势浜Ｙ愱囂幪幷ǎ啥ɡ?.2.4得f(X)為嚴(yán)格凸函數(shù)第28頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸函數(shù)的判定例5試證明為凹函數(shù)證:(1)首先由定義來(lái)證明，任取兩點(diǎn)a1,a2,看下式是否成立？或由于，故．顯然，不管a1,a2取什么值，總有（３）式成立，故f(x1)=-x12為凹函數(shù)，同理可證f(x2)=-x22也是凹函數(shù)．或第29頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸函數(shù)的判定證:(２)用定理2.2.4來(lái)證明，由于故海賽矩陣處處負(fù)定，故f(X)為嚴(yán)格凹函數(shù)．第30頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸函數(shù)的判定證:(３)用定理5.2.3來(lái)證明，任意取第一點(diǎn)，第二點(diǎn)，這樣現(xiàn)看下式是否成立或或證:(３)用定理2.2.3來(lái)證明，任意取第一點(diǎn)，第二點(diǎn)，這樣第31頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸函數(shù)的判定不管a1,a2和b1,b2取什么值，上式均成立從而證明f(Ｘ）是凹函數(shù)．或第32頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸規(guī)劃及其性質(zhì)約束集如果(MP)的約束集X是凸集，目標(biāo)函數(shù)f是X上的凸函數(shù)，則(MP)叫做非線性凸規(guī)劃，或簡(jiǎn)稱為凸規(guī)劃。第33頁(yè)，共139頁(yè)，2023年，2月20日，星期四定理2.2.6

凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。第34頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸規(guī)劃及其性質(zhì)由于線性函數(shù)也既是凸函數(shù)，又是凹函數(shù)，故線性規(guī)劃也屬于凸規(guī)劃．第35頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸規(guī)劃及其性質(zhì)例6試分析非線性規(guī)劃解：f(X)和g2(X)的海賽矩陣的行列式是第36頁(yè)，共139頁(yè)，2023年，2月20日，星期四凸規(guī)劃及其性質(zhì)由上可知f(X)為嚴(yán)格凸函數(shù),g2(x)為凹函數(shù)，由于為線性函數(shù)，故上述約束條件構(gòu)成的可行域?yàn)橥辜@是一個(gè)凸規(guī)劃，Ｃ點(diǎn)為最優(yōu)點(diǎn)：Ｘ＊＝（0.58,1.34)T,目標(biāo)函數(shù)的最優(yōu)值為f(X*)=3.8.２g1(X)g2(X)=0C目標(biāo)函數(shù)等值線第37頁(yè)，共139頁(yè)，2023年，2月20日，星期四算法及有關(guān)概念最優(yōu)化問(wèn)題的數(shù)值解法及理論根據(jù)：1在集合Ｘ上的迭代算法是指：開(kāi)始：選定一個(gè)初始點(diǎn),置k=0,然后再按某種規(guī)則Ａ把k次迭代的x(k)映射為新的一點(diǎn)x(k+1),記為．這稱為第k+1次迭代．這個(gè)過(guò)程無(wú)限進(jìn)行下去，就產(chǎn)生一個(gè)點(diǎn)列，其中規(guī)則Ａ稱為算法．若收斂于問(wèn)題的最優(yōu)解，就稱算法Ａ在Ｘ上是收斂的，否則是發(fā)散的．第38頁(yè)，共139頁(yè)，2023年，2月20日，星期四算法及有關(guān)概念一種算法除了滿足計(jì)算終止準(zhǔn)則的迭代點(diǎn)外,還應(yīng)滿足:下降算法:若對(duì)于每個(gè)k,都有,則稱A為下降迭代算法,簡(jiǎn)稱下降算法.許多最優(yōu)化方法都采用將多維問(wèn)題轉(zhuǎn)化為一維問(wèn)題的方法來(lái)求解.第39頁(yè)，共139頁(yè)，2023年，2月20日，星期四算法及有關(guān)概念如:設(shè)第k次迭代點(diǎn)xk已求得,若它不滿足終止準(zhǔn)則,在該點(diǎn)必存在下降方向.對(duì)于可微目標(biāo)函數(shù),即是滿足的d.

按某種規(guī)則從中選取一個(gè),例如dk,再沿這個(gè)方向適當(dāng)邁進(jìn)一步,即在直線上適當(dāng)確定一個(gè)新點(diǎn),

使那我們就說(shuō)完成了第k+1次迭代,其中稱為步長(zhǎng)因子.第40頁(yè)，共139頁(yè)，2023年，2月20日，星期四算法及有關(guān)概念迭代過(guò)程中應(yīng)滿足兩個(gè)準(zhǔn)則:1是下降方向dk的選取;2是步長(zhǎng)因子

的選取各種迭代法的區(qū)別就在于得出方向dk與步長(zhǎng)的方式不同.對(duì)于非線性規(guī)劃,總結(jié)出:第41頁(yè)，共139頁(yè)，2023年，2月20日，星期四非線性規(guī)劃方法概述第42頁(yè)，共139頁(yè)，2023年，2月20日，星期四非線性規(guī)劃基本迭代格式第43頁(yè)，共139頁(yè)，2023年，2月20日，星期四無(wú)約束優(yōu)化:最優(yōu)解的分類和條件給定一個(gè)函數(shù)f(x),尋找x*使得f(x*)最小，即其中局部最優(yōu)解全局最優(yōu)解必要條件x*f(x)xlxgo充分條件Hessian陣最優(yōu)解在可行域邊界上取得時(shí)不能用無(wú)約束優(yōu)化方法求解第44頁(yè)，共139頁(yè)，2023年，2月20日，星期四2迭代法中直線搜索及其性質(zhì)：在搜索方向已經(jīng)確定的前提下,步長(zhǎng)因子的選取有多種方法,如

i)取步長(zhǎng)因子為某個(gè)常數(shù),但不能保證使目標(biāo)函數(shù)值下降;ii)可接受點(diǎn)算法，只要能使目標(biāo)函數(shù)下降，可任意選取步長(zhǎng);

iii)基于沿搜索方向使目標(biāo)函數(shù)值下降最多，沿射線求目標(biāo)函數(shù)的極小值：第45頁(yè)，共139頁(yè)，2023年，2月20日，星期四2迭代法中直線搜索及其性質(zhì)：

由于這項(xiàng)工作是求以為變量的一元函數(shù)的極小點(diǎn)，故稱這一過(guò)程為一維搜索（線搜索），這樣確定的步長(zhǎng)為最佳步長(zhǎng),實(shí)際計(jì)算中常用此方法.

一維搜索有個(gè)性質(zhì)：在搜索方向上所得最優(yōu)點(diǎn)處的梯度和搜索方向正交．定理：設(shè)目標(biāo)函數(shù)f(X)具有一階連續(xù)偏導(dǎo)數(shù)，x(k+1)按下列規(guī)劃產(chǎn)生：則有第46頁(yè)，共139頁(yè)，2023年，2月20日，星期四3收斂速度

一個(gè)算法不光能收斂于解,還必須以較快的速度收斂于解,這才是好的算法;

我們用以下收斂的階來(lái)度量一個(gè)算法的收斂速度.第47頁(yè)，共139頁(yè)，2023年，2月20日，星期四3收斂速度

定義:設(shè)序列收斂于,而且若,則稱為線性收斂的,為收斂比;

若,則稱為超線性收斂.

定義:設(shè)序列收斂于,若對(duì)于某個(gè)實(shí)數(shù),有

則稱序列為階收斂的第48頁(yè)，共139頁(yè)，2023年，2月20日，星期四3收斂速度

一般來(lái)說(shuō),線性收斂是比較慢的,而二階收斂則是很快的,超線性收斂居中,如果一個(gè)算法具有超線性以上的收斂速度,我們就認(rèn)為它是一個(gè)很好的算法了.第49頁(yè)，共139頁(yè)，2023年，2月20日，星期四50因真正的極值點(diǎn)事先并不知道，故在實(shí)用上只能根據(jù)相繼兩次迭代得到的計(jì)算結(jié)果來(lái)判斷是否已達(dá)到要求，從而建立終止迭代計(jì)算的準(zhǔn)則。常用的終止迭代準(zhǔn)則有：（1）根據(jù)相繼兩次迭代結(jié)果的絕對(duì)誤差。4.終止迭代準(zhǔn)則（2）根據(jù)相繼兩次迭代結(jié)果的相對(duì)誤差。（3）根據(jù)函數(shù)梯度的模足夠小。迭代終止準(zhǔn)則①點(diǎn)距準(zhǔn)則②函數(shù)值下降準(zhǔn)則③梯度準(zhǔn)則第50頁(yè)，共139頁(yè)，2023年，2月20日，星期四2.2一維搜索方法精確一維搜索方法

0.618法

Newton法非精確一維搜索方法

Goldstein法

Armijo法第51頁(yè)，共139頁(yè)，2023年，2月20日，星期四一維搜索

上節(jié)提到,在大多數(shù)無(wú)約束極值的算法中,為了確定最優(yōu)解,一般用解析的方法是很難得到的,即精確解通常是計(jì)算不出來(lái)的,故我們常采用的是數(shù)值的方法來(lái)得到其近似解,上節(jié)我們提到,數(shù)值解法最常用的一種方法是迭代法.

為了確定極小化點(diǎn)列,要沿逐次確定的系列射線求極小點(diǎn),即所謂的一維搜索.

一維搜索可歸結(jié)為單變量函數(shù)求極小的問(wèn)題,設(shè)目標(biāo)函數(shù)為,過(guò)點(diǎn)沿方向的直線可用點(diǎn)集表示為:

第52頁(yè)，共139頁(yè)，2023年，2月20日，星期四求在直線L上的極小點(diǎn)轉(zhuǎn)化為求一元函數(shù)

的極小點(diǎn).

如果的極小點(diǎn)為,通常稱為沿方向的步長(zhǎng)因子或簡(jiǎn)稱步長(zhǎng).函數(shù)在直線上的極小點(diǎn)就是

一維搜索的方法一般有以下幾類：

1.數(shù)學(xué)分析中所講的方法，即解方程，此方法稱為精確線性搜索.2.試探法:

按照某種方式試探點(diǎn),通過(guò)一系列試探點(diǎn)的比較確定極小點(diǎn).第53頁(yè)，共139頁(yè)，2023年，2月20日，星期四

3.函數(shù)逼近法:

用比較簡(jiǎn)單的曲線近似代替原來(lái)的曲線,用近似曲線的極小點(diǎn)來(lái)估計(jì)原來(lái)的極小點(diǎn).

下面我們將分別具體介紹幾種方法:

一.平分法根據(jù)以前我們所學(xué)習(xí)的知識(shí),我們知道，在的極小點(diǎn)處有,并且當(dāng)時(shí),函數(shù)是遞減的,即;而當(dāng)時(shí),函數(shù)遞增,即.

注:因?yàn)闉闃O小點(diǎn),若:

此時(shí)為極大點(diǎn).第54頁(yè)，共139頁(yè)，2023年，2月20日，星期四

我們找到了一個(gè)區(qū)間,具有性質(zhì)則在間必然有的極小點(diǎn),且.為了找到,

我們?nèi)?1.若,則在中有極小點(diǎn),

2.若,則在中有極小點(diǎn).y=f(x)00xy第55頁(yè)，共139頁(yè)，2023年，2月20日，星期四若情形1滿足時(shí),此時(shí)以作為新的區(qū)間;

若情形2滿足時(shí),此時(shí)以作為新的區(qū)間.

繼續(xù)上述過(guò)程,逐步將區(qū)間換小,當(dāng)區(qū)間充分小時(shí),或者當(dāng)充分小時(shí),即可將區(qū)間中點(diǎn)取做極小點(diǎn)的近似,此時(shí)有:0xy0xy第56頁(yè)，共139頁(yè)，2023年，2月20日，星期四注:也可以用以下的收斂準(zhǔn)則:1.成立,

2.成立.

但是我們?nèi)绾蝸?lái)確定初始區(qū)間呢?下面我們將解決這個(gè)問(wèn)題。

第57頁(yè)，共139頁(yè)，2023年，2月20日，星期四搜索區(qū)間的選取可采用如下的進(jìn)—退算法：給定初始點(diǎn)，初始步長(zhǎng)，求搜索區(qū)間：1）計(jì)算2）若,(此時(shí)稱搜索成功，下一步搜索就大步前進(jìn))，則步長(zhǎng)加倍，計(jì)算若，則；否則步長(zhǎng)再加倍，并重復(fù)上面的運(yùn)算；第58頁(yè)，共139頁(yè)，2023年，2月20日，星期四3）若,(此時(shí)稱搜索失敗，下一步就小步后退),則步長(zhǎng)縮為原來(lái)的1/4，并改變符號(hào)，即新步長(zhǎng)為，若

則；否則步長(zhǎng)再加倍，繼續(xù)后退。第59頁(yè)，共139頁(yè)，2023年，2月20日，星期四二、0.618法（近似黃金分割法）單谷函數(shù)退出前一頁(yè)后一頁(yè)第60頁(yè)，共139頁(yè)，2023年，2月20日，星期四搜索法求解：或基本過(guò)程：給出[a,b],使得t*在[a,b]中。[a,b]稱為搜索區(qū)間。迭代縮短[a,b]的長(zhǎng)度。當(dāng)[a,b]的長(zhǎng)度小于某個(gè)預(yù)設(shè)的值，或者導(dǎo)數(shù)的絕對(duì)值小于某個(gè)預(yù)設(shè)的正數(shù)，則迭代終止。退出前一頁(yè)后一頁(yè)第61頁(yè)，共139頁(yè)，2023年，2月20日，星期四假定：已經(jīng)確定了單谷區(qū)間[a,b]t1t2ababt1t2新搜索區(qū)間為[a,t2]新搜索區(qū)間為[t1,b]退出前一頁(yè)后一頁(yè)第62頁(yè)，共139頁(yè)，2023年，2月20日，星期四區(qū)間縮小比例的確定：區(qū)間縮短比例為(t2-a)/(b-a)縮短比例為(b-t1)/(b-a)縮短比例滿足：每次插入搜索點(diǎn)使得兩個(gè)區(qū)間[a,t2]和[t1,b]相等；每次迭代都以相等的比例縮小區(qū)間。0.618法t1t2ababt1t2退出前一頁(yè)后一頁(yè)第63頁(yè)，共139頁(yè)，2023年，2月20日，星期四確定[a,b],計(jì)算探索點(diǎn)t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解題步驟：是否是停止，輸出t1否以[a,t2]為新的搜索區(qū)間是停止，輸出t2否以[t1,b]為新的搜索區(qū)間退出前一頁(yè)后一頁(yè)第64頁(yè)，共139頁(yè)，2023年，2月20日，星期四例：解：t1t230t1、第一輪：t1=1.146,t2=1.854t2－0>0.5退出前一頁(yè)后一頁(yè)第65頁(yè)，共139頁(yè)，2023年，2月20日，星期四2、第二輪：t2=1.146,t1=0.708t2－0=1.146>0.53、第三輪：t1=0.438,t2=0.708b-t1=1.146-0.438>0.51.8540tt2t11.4160tt2t1退出前一頁(yè)后一頁(yè)第66頁(yè)，共139頁(yè)，2023年，2月20日，星期四4、第四輪：t2=0.876,t1=0.708b-t1=1.146-0.708<0.5輸出：t*=t2=0.876為最優(yōu)解，最優(yōu)值為-0.079801.416tt1t2退出前一頁(yè)后一頁(yè)第67頁(yè)，共139頁(yè)，2023年，2月20日，星期四68例求解f(x)=-18x2+72x+28的極大值點(diǎn)，≤0.1，起始搜索區(qū)間為[0,3]解：①用間接法：令f’(x)=-36x+72=0，得駐點(diǎn)x=2

又因?yàn)閒’’(x)=-36＜0，故x=2為f(x)的極大值點(diǎn)，fmax=100②用直接法中的黃金分割法：令n-1=，得n=1+(lg)/(lg)≈5.78442

約6步即可，計(jì)算結(jié)果見(jiàn)下表：kakbkf(ak)f(bk)pk=

bk-akpk/p0x1k=ak+·pkx2k=bk-·pkf(x2k)△f(x1k)0032882311.8541.14686.9＜99.62f(x)xo3x1x211.146386.9821.8540.6182.2921.85499.62＞98.4621.1462.29286.998.461.1460.3821.8541.58496.89＜99.6231.5842.29296.8998.460.7080.2362.0221.85499.62＜99.9941.8542.29299.6298.460.4380.1462.1252.02299.99＞98.7251.8542.12599.6299.720.2710.0903第68頁(yè)，共139頁(yè)，2023年，2月20日，星期四第69頁(yè)，共139頁(yè)，2023年，2月20日，星期四第70頁(yè)，共139頁(yè)，2023年，2月20日，星期四第71頁(yè)，共139頁(yè)，2023年，2月20日，星期四第72頁(yè)，共139頁(yè)，2023年，2月20日，星期四三、Newton法Newton法基本思想：用探索點(diǎn)tk處的二階Taylor展開(kāi)式近似代替目標(biāo)函數(shù)，以展開(kāi)式的最小點(diǎn)為新的探索點(diǎn)。退出前一頁(yè)后一頁(yè)第73頁(yè)，共139頁(yè)，2023年，2月20日，星期四解題步驟：給定初始點(diǎn)t1和精度是是停止，輸出t1是否停止，解題失敗否停止，輸出t2否退出前一頁(yè)后一頁(yè)第74頁(yè)，共139頁(yè)，2023年，2月20日，星期四例：解：取t1=1,計(jì)算：迭代過(guò)程如下表：1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411退出前一頁(yè)后一頁(yè)第75頁(yè)，共139頁(yè)，2023年，2月20日，星期四第76頁(yè)，共139頁(yè)，2023年，2月20日，星期四3、非精確一維搜索法數(shù)值方法的關(guān)鍵是從一個(gè)點(diǎn)迭代到下一個(gè)點(diǎn)。確定下一個(gè)點(diǎn)的關(guān)鍵是確定搜索方向和步長(zhǎng)如果已經(jīng)確定了搜索方向pk,則只要確定一個(gè)最佳的步長(zhǎng)即可。所謂的最佳步長(zhǎng)即是在pk方向上走一個(gè)最好的長(zhǎng)度使得目標(biāo)函數(shù)下降的最多，即下述的最優(yōu)化問(wèn)題：這樣的最優(yōu)化問(wèn)題不需要太高的精度，只要滿足某些更寬松的精度要求即可。這樣的搜索方法稱之為非精確一維搜索方法退出前一頁(yè)后一頁(yè)第77頁(yè)，共139頁(yè)，2023年，2月20日，星期四Goldstein法原理：yt0bcdaY=(0)+′(0)tY=(0)+m2′(0)tY=(0)+m1′(0)t退出前一頁(yè)后一頁(yè)第78頁(yè)，共139頁(yè)，2023年，2月20日，星期四是Goldstein算法確定m1,m2,α,t0,a=0,b=+∞(t0)≤(0)+m1’(0)t0(t0)≥(0)+m2’(0)t0是停止,輸出t0否a=a,b=t0,t1=(a+b)/2否a=t0,b=b,t1=(a+b)/2(若b=+∞,則t1=αa)退出前一頁(yè)后一頁(yè)第79頁(yè)，共139頁(yè)，2023年，2月20日，星期四Goldstein法步驟第80頁(yè)，共139頁(yè)，2023年，2月20日，星期四Armijo法第81頁(yè)，共139頁(yè)，2023年，2月20日，星期四82無(wú)約束條件下多變量函數(shù)尋優(yōu)一、爬山法原理：通過(guò)點(diǎn)的直接移動(dòng)，逐步改善目標(biāo)函數(shù)取值，直至達(dá)到極值點(diǎn)為止。由以下二部分組成：①選定搜索方向；②在選定的方向上爬山搜索。二、變量輪換法(或降維法):選擇與坐標(biāo)軸平行的方向?yàn)樗阉鞣较蛟O(shè)S=f(X)=f(x1,x2,…,xn)，極值點(diǎn)存在的區(qū)間為

x1*[a1,b1]，x2*[a2,b2]，…

，xn*[an,bn]1、原理：①?gòu)钠瘘c(diǎn)X(0)出發(fā)，沿平行于x1

軸的方向P(1)進(jìn)行一維搜索，求得f(X)在該方向P(1)上近似極值點(diǎn)X(1)；②從點(diǎn)X(1)出發(fā)，沿平行于x2

軸的方向P(2)進(jìn)行一維搜索，求得f(X)在該方向P(2)上近似極值點(diǎn)X(2)；③從點(diǎn)X(2)出發(fā)，照此交替進(jìn)行下去，直至滿足給定的精度為止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜

第82頁(yè)，共139頁(yè)，2023年，2月20日，星期四83

2、算法步驟：設(shè)S=f(X)=f(x1,x2)，極值點(diǎn)存在的區(qū)間為x1*[a1,b1]，x2*[a2,b2]

第一步：從X(0)=(x1(0),x2(0))T出發(fā)①先固定x1=x1(0):求以x2為單變量的目標(biāo)函數(shù)的極值點(diǎn)，得X(1)=(x1(0),x2(1))T

，S(1)=f(X(1))②再固定x2=x2(1):求以x1為單變量的目標(biāo)函數(shù)的極值點(diǎn)，得X(2)=(x1(2),x2(1))T

，S(2)=f(X(2))

此時(shí)S(2)優(yōu)于S(1)，且搜索區(qū)間縮短為x1*[x1(2),b1]，x2*[x2(1),b2]

第二步：如此交替搜索，直至滿足給定精度為止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜o(jì)x1X(0)X(1)X(2)X(3)X(4)x2第83頁(yè)，共139頁(yè)，2023年，2月20日，星期四84例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點(diǎn)，=0.01解：設(shè)起始點(diǎn)X(0)=(0,0)T，用變量輪換法計(jì)算：①先固定x1=x1(0)=0:則f(0,x2)=x22-4x2+60，尋優(yōu)得x2(1)=2

于是X(1)=(x1(0),x2(1))T=(0,2)T

，S(1)=f(X(1))=56②再固定x2=x2(1)=2:則f(x1,2)=x12-12x1+56，尋優(yōu)得x1(2)=6

于是X(2)=(x1(2),x2(1))T=(6,2)T

，S(2)=f(X(2))=20

如此交替搜索，直至滿足給定精度=0.01為止

|f(X(k))

-f(X(k-1))|＜0.01或

|S(k)-S(k-1)|＜0.01

最后得極小點(diǎn)X*=(8,6)T，f(X*)=8ox1X(0)X(1)X(2)X(3)X(4)x2計(jì)算結(jié)果見(jiàn)下表：第84頁(yè)，共139頁(yè)，2023年，2月20日，星期四85k固定的xi單變量的目標(biāo)函數(shù)f(xj)求得極點(diǎn)xj目標(biāo)值S(k)|S(k)-S(k-1)|12345678x1=x1(0)=0x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.88x2=x2(7)=5.94f(0,x2)=x22-4x2+60f(x1,2)=x12-12x1+56f(6,x2)=x22-10x2+36f(x1,5)=x12-15x1+65f(7.5,x2)=x22–11.5x2+41.25f(x1,5.75)=x12–15.75x1+70.06f(7.88,x2)=x22–11.88x2+43.27f(x1,5.94)=x12–15.94x1+71.50x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.875x2=x2(7)=5.94x1=x1(8)=7.975620118.758.18758.04698.01178.00293692.250.56250.14060.03520.0088ox1X(0)X(1)X(2)X(3)X(4)x2缺點(diǎn)：①很大程度上取決于目標(biāo)函數(shù)性質(zhì)。目標(biāo)函數(shù)等高線的性質(zhì)很重要。②道路迂回曲折，多次變換方向，在極點(diǎn)附近，目標(biāo)值改進(jìn)更小，收斂速度慢。故不是一個(gè)有利方向。第85頁(yè)，共139頁(yè)，2023年，2月20日，星期四最速下降法第86頁(yè)，共139頁(yè)，2023年，2月20日，星期四是X(k)處函數(shù)值下降最快的方向。當(dāng)時(shí)，p(k)是f(X)在X(k)處的下降方向。函數(shù)f(X)在X(k)處的負(fù)梯度方向梯度的性質(zhì)：1、迭代原理證明：結(jié)論：一元函數(shù)泰勒公式：第87頁(yè)，共139頁(yè)，2023年，2月20日，星期四2.迭代原理最優(yōu)步長(zhǎng)第88頁(yè)，共139頁(yè)，2023年，2月20日，星期四最速下降法迭代原理：一維搜索找極小點(diǎn)：1)確定[0,1],精度0.12)用0.618法得到

040.53184第89頁(yè)，共139頁(yè)，2023年，2月20日，星期四最速下降法迭代原理：

第90頁(yè)，共139頁(yè)，2023年，2月20日，星期四線性規(guī)劃3-42.迭代原理最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)第91頁(yè)，共139頁(yè)，2023年，2月20日，星期四線性收斂2.迭代原理最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)得到一個(gè)點(diǎn)列：可以證明：第92頁(yè)，共139頁(yè)，2023年，2月20日，星期四2.迭代原理證明：第93頁(yè)，共139頁(yè)，2023年，2月20日，星期四3.迭代步驟第94頁(yè)，共139頁(yè)，2023年，2月20日，星期四3.迭代步驟注釋：(一階必要條件)10停機(jī)準(zhǔn)則：設(shè)連續(xù)(即f(X)連續(xù)可微)第95頁(yè)，共139頁(yè)，2023年，2月20日，星期四注釋：3.迭代步驟一維搜索最優(yōu)解的梯度與搜索方向正交20結(jié)論：證明：第96頁(yè)，共139頁(yè)，2023年，2月20日，星期四注釋：最速下降法的任何兩個(gè)相鄰搜索方向正交(垂直)3.迭代步驟30結(jié)論：第97頁(yè)，共139頁(yè)，2023年，2月20日，星期四注釋：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得到的表達(dá)式：第98頁(yè)，共139頁(yè)，2023年，2月20日，星期四線性規(guī)劃3-4證明：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得到的表達(dá)式：注釋：該公式具有普遍性第99頁(yè)，共139頁(yè)，2023年，2月20日，星期四注釋：3.迭代步驟40將一維搜索用于正定二次函數(shù)：則可以得到的表達(dá)式：第100頁(yè)，共139頁(yè)，2023年，2月20日，星期四注釋：3.迭代步驟50將最速下降法用于正定二次函數(shù)：則可以得到的表達(dá)式：第101頁(yè)，共139頁(yè)，2023年，2月20日，星期四注釋：3.迭代步驟50最速下降法，Newton法，擬Newton法，共軛梯度法的區(qū)別就是搜索方向p(k)取得不同。第102頁(yè)，共139頁(yè)，2023年，2月20日，星期四4.舉例例3-10解：用最速下降法求的極小點(diǎn)，迭代兩次。第103頁(yè)，共139頁(yè)，2023年，2月20日，星期四例:試用最速下降法求的極小點(diǎn),迭代兩次,計(jì)算每個(gè)迭代點(diǎn)的函數(shù)值,梯度及模,并驗(yàn)證相鄰兩個(gè)搜索方向是正交的.

解:給初始點(diǎn),,,,,

利用必要條件：第104頁(yè)，共139頁(yè)，2023年，2月20日，星期四于是：由解得

第105頁(yè)，共139頁(yè)，2023年，2月20日，星期四驗(yàn)證搜索方向的正交性:第106頁(yè)，共139頁(yè)，2023年，2月20日，星期四107例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點(diǎn)，=0.1解:①②從點(diǎn)X(1)出發(fā)，照此進(jìn)行下去，直至滿足給定的精度=0.1為止|f(X(k+1))

-f(X(k))|＜0.1或||G(k)||＜0.1

第107頁(yè)，共139頁(yè)，2023年，2月20日，星期四108計(jì)算結(jié)果見(jiàn)下表：缺點(diǎn)：①搜索效果比變量輪換法快，但愈接近極值點(diǎn)，步長(zhǎng)愈小，目標(biāo)值改進(jìn)愈小。當(dāng)遇到強(qiáng)交互作用時(shí)，不是有效的方法;當(dāng)遇到山脊時(shí)，會(huì)慢慢爬行。②在遠(yuǎn)離極點(diǎn)時(shí)，收斂速度較快;在極點(diǎn)附近，收斂速度不快。k01234507.636.817.957.827.9903.055.115.565.875.93-102.21-1.490.33-0.220.05-4-5.53-0.60-0.82-0.09-0.1210.775.591.600.890.240.13-0.930.37-0.930.37-0.930.37-0.37-0.93-0.37-0.93-0.37-0.9288.222.211.220.330.180.056015.749.158.178.038.003744.266.590.980.140.026ox1x(0)x(1)x(2)X(3)x2第108頁(yè)，共139頁(yè)，2023年，2月20日，星期四第109頁(yè)，共139頁(yè)，2023年，2月20日，星期四110四、共軛梯度法:選擇共軛方向?yàn)樗阉鞣较颌鍐?wèn)題的提出：在極值點(diǎn)附近，如何加快收斂速度，須對(duì)函數(shù)在極值點(diǎn)附近的性質(zhì)進(jìn)行研究。

設(shè)有n維目標(biāo)函數(shù)S=f(X)=f(x1,x2,…,xn),在極值點(diǎn)X*附近展開(kāi)成泰勒級(jí)數(shù)：

特別：對(duì)二元二次函數(shù)，可證明：在極值點(diǎn)附近，其等高線可近似視為同心橢園族，而同心橢園族的任意兩根平行切線的切點(diǎn)連線必通過(guò)橢園中心。

ox1X(0)P(0)X’(0)X(2)X(1)x2P’(0)P(1)=X(2)-X(1)P(1)與P(0)共軛故：在極值點(diǎn)附近，沿搜索方向P(0)上巳得到一個(gè)切點(diǎn)X(1)，則只要得出通過(guò)極值點(diǎn)的連線方向P(1),在此方向上尋優(yōu),可一步直達(dá)極值點(diǎn)。而這個(gè)連線方向P(1)是上一次搜索方向P(0)的共軛方向。第110頁(yè)，共139頁(yè)，2023年，2月20日，星期四111㈡共軛方向的定義：1、定義：設(shè)X,Y是n維向量空間En中兩個(gè)向量，A為n×n對(duì)稱正定矩陣，若XTAY=0，則稱向量X與Y對(duì)于矩陣A共軛。特例：若A=I，得XTY=0，則稱向量X與Y正交。2、幾何意義：共軛方向是通過(guò)極值點(diǎn)的方向。㈢尋優(yōu)原理：設(shè)n元函數(shù)S=f(X)=f(x1,x2,…,xn),在極值點(diǎn)X*附近可用一個(gè)二次函數(shù)逼近其中H為n×n對(duì)稱正定矩陣第111頁(yè)，共139頁(yè)，2023年，2月20日，星期四112特別：對(duì)二元二次函數(shù)S=f(X)=f(x1，x2)①?gòu)哪滁c(diǎn)X(0)出發(fā),以P(0)方向搜索,使f(X)達(dá)到極小值點(diǎn)X(1),則:X(1)必為該點(diǎn)處等高線的切點(diǎn),P(0)為切線方向，且點(diǎn)X(1)的梯度方向f(X(1))為該等高線的法線方向，這兩個(gè)方向正交。②從另一點(diǎn)X’(0)出發(fā),仍以P(0)方向搜索,使f(X)達(dá)到另一個(gè)極小值點(diǎn)X(2),則:X(2)也必為該點(diǎn)處等高線的切點(diǎn),P(0)為切線方向，且點(diǎn)X(2)的梯度方向f(X(2))為該等高線的法線方向，這兩個(gè)方向正交。ox1X(0)P(0)X’(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1)P(1)與P(0)共軛故:對(duì)二元二次函數(shù),只須搜索兩個(gè)方向P(0)和P(1)就可達(dá)到極值點(diǎn)X*。一般:對(duì)n元二次函數(shù),可用不超過(guò)n次搜索就可達(dá)到極值點(diǎn)X*。而n元非二次函數(shù)在極值點(diǎn)附近可用二次函數(shù)逼近。第112頁(yè)，共139頁(yè)，2023年，2月20日，星期四113㈤適用于一般目標(biāo)函數(shù)的共軛梯度法：1、共軛方向的計(jì)算問(wèn)題：須用到目標(biāo)函數(shù)的海賽矩陣H(二階偏導(dǎo)數(shù)矩陣)，若目標(biāo)函數(shù)為二次函數(shù)時(shí)，H容易求出；若目標(biāo)函數(shù)為高次或高維函數(shù)時(shí)，H難以求出，此時(shí)共軛方向難以求出。2、共軛方向的計(jì)算方法：F-R法，由Fletcher和Reeves提出，可避免海賽矩陣H的計(jì)算，方便地確定共軛方向，簡(jiǎn)單有效。第113頁(yè)，共139頁(yè)，2023年，2月20日，星期四114

3、搜索過(guò)程：①?gòu)腦(0)出發(fā)：②從X(1)出發(fā)：第114頁(yè)，共139頁(yè)，2023年，2月20日，星期四115③從X(2)出發(fā)：4、搜索方法:①若目標(biāo)函數(shù)為n元二次函數(shù)，則理論上最多經(jīng)n次迭代可達(dá)極小點(diǎn)，實(shí)際由于舍入誤差，須n次以上的迭代。②若目標(biāo)函數(shù)為n元非二次函數(shù)，但共軛方向只有n個(gè)，迭代n次以后應(yīng)重新開(kāi)始迭代，減少誤差積累。一般，在開(kāi)始階段(二次型較弱)用一階梯度法，接近極點(diǎn)(二次型較強(qiáng))用共軛梯度法。一般有：第115頁(yè)，共139頁(yè)，2023年，2月20日，星期四第116頁(yè)，共139頁(yè)，2023年，2月20日，星期四117例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點(diǎn)。解:①②第117頁(yè)，共139頁(yè)，2023年，2月20日，星期四例2

用共軛梯度法求解,取解:用共軛梯度法的第一步和最速下降法是相同的,

故由前例知:

第118頁(yè)，共139頁(yè)，2023年，2月20日，星期四因?yàn)檩^大,還需要迭代,下一探索方向由共軛梯度并利用和組合而成.

其中

所以由

第119頁(yè)，共139頁(yè)，2023年，2月20日，星期四由：把分別代入的表達(dá)式中求得,因?yàn)?所以迭代終止,就是所求的極小點(diǎn).第120頁(yè)，共139頁(yè)，2023年，2月20日，星期四共軛梯度法的特點(diǎn):對(duì)于二次函數(shù)的情形,從理論上說(shuō),進(jìn)行n次迭代即可達(dá)到極小點(diǎn),但是,在實(shí)際計(jì)算中,由于數(shù)據(jù)的舍入以及計(jì)算誤差積累,往往做不到這一點(diǎn).由于n維問(wèn)題的共軛方向最多只有個(gè),在步之后繼續(xù)如上進(jìn)行就沒(méi)有意義.因此,實(shí)際計(jì)算中如迭代n步還不收斂,就將X(n)作為新的始點(diǎn),重新開(kāi)始迭代,這樣一般都可得到較好的效果.第121頁(yè)，共139頁(yè)，2023年，2月20日，星期四浙江理工大學(xué)經(jīng)濟(jì)管理學(xué)院1222.4牛頓法與擬牛頓法⑴牛頓方向四、牛頓法第122頁(yè)，共139頁(yè)，2023年，2月20日，星期四浙江理工大學(xué)經(jīng)濟(jì)管理學(xué)院123四、牛頓法（1）牛頓方向第123頁(yè)，共139頁(yè)，2023年，2月20日，星期四浙江理工大學(xué)經(jīng)濟(jì)管理學(xué)院1242.3無(wú)約束極值問(wèn)題四、牛頓法（2）廣義牛頓法步驟當(dāng)一維搜索是精確的，牛頓法為二階收斂。第124頁(yè)，共139頁(yè)，2023年，2月20日，星期四浙江理工大學(xué)經(jīng)濟(jì)管理學(xué)院1252.3無(wú)約束極值問(wèn)題四、牛頓法（3）牛頓法優(yōu)缺點(diǎn)優(yōu)點(diǎn)：收斂速度快。缺點(diǎn)：有時(shí)進(jìn)行不下去而需采取改進(jìn)措施；當(dāng)維數(shù)較高時(shí)，計(jì)算塞黑矩陣的逆工作量太大?？刹捎闷渌椒?，如共軛梯度法，變尺度法等。第125頁(yè)，共139頁(yè)，2023年，2月20日，星期四

定理5.3：設(shè),且正定,記是由修改的牛頓法所得到的迭代點(diǎn)列,若水平集有界,則必有聚點(diǎn),且任一聚點(diǎn)必滿足.

牛頓法的特征:1.牛頓法應(yīng)用于具有正定陣的二次函數(shù)時(shí),只要一次迭代就可以達(dá)到無(wú)約束優(yōu)化問(wèn)題的最優(yōu)解,即算法具有二次收斂性.2.當(dāng)初始點(diǎn)接近極小點(diǎn)時(shí),牛頓法產(chǎn)生的序列以二階收斂速度趨于問(wèn)題的平穩(wěn)點(diǎn),但當(dāng)初始點(diǎn)與極小點(diǎn)較遠(yuǎn)時(shí),陣可能是奇異的，牛頓方向不存在,或者陣不正定,

不再是下降方向,此時(shí)需要使用改進(jìn)的牛頓法,其收斂速度極大降低,因此,應(yīng)該盡可能選取離極小點(diǎn)較遠(yuǎn)的初始點(diǎn).3.牛頓法對(duì)目標(biāo)函數(shù)要求高(二階連續(xù)可微)且需要較多存儲(chǔ)單元,

每次迭代要進(jìn)行矩陣求逆運(yùn)算.第126頁(yè)，共139頁(yè)，2023年，2月20日，星期四

二.擬牛頓法(變尺度法)

修改的牛頓法具有全局收斂性和收斂快的特點(diǎn),但還存在一個(gè)

缺點(diǎn),即在每步確定搜索方向時(shí),要計(jì)算陣及其逆矩陣,這個(gè)計(jì)算工作最大.于是又有一種設(shè)想,將確定搜索方向公式中的用n階矩陣代替,從而在第k次迭代時(shí)

由線性搜索得到，其中和初始矩陣是預(yù)先給定的,

在迭代中,利用一階導(dǎo)數(shù)按某中規(guī)則得到.第127頁(yè)，共139頁(yè)，2023年，2月20日，星期四

確定的一種自然想法是將作為的近似來(lái)構(gòu)造,注意到是對(duì)稱的,且有關(guān)系即若記=,,,必須滿足:1.對(duì)稱正定

2.滿足擬牛頓方程

(2.30)

另外,再設(shè)想是由經(jīng)過(guò)簡(jiǎn)單修正而得到的,即校正矩陣自然應(yīng)是對(duì)稱矩陣,由(2.30)式應(yīng)滿足第128頁(yè)，共139頁(yè)，2023年，2月20日，星期四

(2.31)

滿足(2.31)的對(duì)稱矩陣有無(wú)窮多個(gè),因此,擬牛頓算法是一族算法,

其最常見(jiàn)的算法所謂DFP是由