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

1、關(guān)于無(wú)約束非線性規(guī)劃第一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月2.1 非線性函數(shù)和非線性規(guī)劃的概念線性函數(shù):(1) f(kx)=kf(x) (2) f(x1+x2)=f(x1)+f(x2)則非線性函數(shù)就是不滿(mǎn)足以上兩個(gè)條件的函數(shù)非線性規(guī)劃：如果目標(biāo)函數(shù)或約束條件中，有一個(gè)或多個(gè)是變量的非線性函數(shù)，就稱(chēng)為非線性規(guī)劃第二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月非線性規(guī)劃問(wèn)題例1 曲線的最優(yōu)擬合問(wèn)題第三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月例2 構(gòu)件容積問(wèn)題第四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月非線性規(guī)劃問(wèn)題例3第五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月非線

2、性規(guī)劃問(wèn)題例3第六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月非線性規(guī)劃通常情況下，目標(biāo)函數(shù)f(x)和約束條件hi(X)和gi(X)為自變量的非線性函數(shù)第七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月非線性規(guī)劃ULP的可行解或可行點(diǎn)約束集或可行域第八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月向量化表示當(dāng)p=0,q=0時(shí)，稱(chēng)為無(wú)約束非線性規(guī)劃或者無(wú)約束最優(yōu)化問(wèn)題。否則，稱(chēng)為約束非線性規(guī)劃或者約束最優(yōu)化問(wèn)題。第九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月最優(yōu)解和極小點(diǎn)第十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月最優(yōu)解和極小點(diǎn)第十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月極值

3、存在的條件必要條件：設(shè)是n維歐氏空間的某一區(qū)域，f(X)為定義在上的實(shí)值函數(shù)，是區(qū)域的內(nèi)點(diǎn)，若f(）在處可微，且在該點(diǎn)取得局部極小值，則必有或第十二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月極值存在的條件其中，為函數(shù)f(x)在處的梯度，梯度的方向?yàn)閒(X)的等值面（等值線）的法線方向，沿這個(gè)方向函數(shù)值增加最快滿(mǎn)足上式的點(diǎn)稱(chēng)為駐點(diǎn)，在區(qū)域內(nèi)部，極值點(diǎn)必為駐點(diǎn)；但駐點(diǎn)不一定是極值點(diǎn)第十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月14二次型二次型是X=(x1,x2,xn)T的二次齊次函數(shù)：aij=aji,A為n*n對(duì)稱(chēng)矩陣。若A的所有元素均為實(shí)數(shù)，則為實(shí)二次型。一個(gè)二次型唯一對(duì)應(yīng)一個(gè)對(duì)稱(chēng)矩陣

4、，反之，一個(gè)對(duì)稱(chēng)矩陣也唯一確定一個(gè)二次型。二次型（對(duì)稱(chēng)矩陣）正定，負(fù)定，不定。半正定，半負(fù)定。第十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月15二次型二次型正定的充要條件，是它的矩陣的左上角各階主子式都大于零。二次型負(fù)定的充要條件，是它的矩陣的左上角各階主子式都負(fù)、正相間。 例：判定正負(fù)性。 第十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月極值存在的條件充分條件：設(shè)是n維歐氏空間的某一區(qū)域，f(X)為定義在上的實(shí)值函數(shù)，是區(qū)域的內(nèi)點(diǎn)，f(）在上二次連續(xù)可微，若f(）在且處滿(mǎn)足（5）或（5）式，且對(duì)任何非零矢量均有則f(x)在取嚴(yán)格局部極小值，此處（x*)為f(x)在點(diǎn)處的海賽（Hes

5、se)矩陣第十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月極值存在的條件此處（x*)為f(x)在點(diǎn)處的海賽（Hesse)矩陣第十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月極值存在的條件例求目標(biāo)函數(shù)的梯度和Hesse矩陣解:因?yàn)?,所以第十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月極值存在的條件又因?yàn)樗约礊镠esse矩陣第十九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月極值存在的條件例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)（，）

6、不是極值點(diǎn)，而是一個(gè)鞍點(diǎn)第二十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月極值存在的條件例3試求函數(shù)f(x1,x2)=2x12-8x1+2x2-4x2+20的極值和極值點(diǎn)解：令得（2,1）點(diǎn)為駐點(diǎn)第二十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月極值存在的條件其海賽矩陣之行列式可知（2,1）點(diǎn)為極小點(diǎn),其極小值為:第二十二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸函數(shù)和凸規(guī)劃凸函數(shù)及其性質(zhì)凸規(guī)劃及其性質(zhì)第二十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸函數(shù)及其性質(zhì)第二十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸函數(shù)的性質(zhì)第二十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022

7、年6月凸函數(shù)的判定第二十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月第二十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸函數(shù)的判定例4 判定下述函數(shù)是凸函數(shù)還是凹函數(shù)解:因?yàn)槠浜Ｙ愱嚨男辛惺綖椋汗势浜Ｙ愱囂幪幷ǎ啥ɡ?.2.4得f(X)為嚴(yán)格凸函數(shù)第二十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸函數(shù)的判定例5 試證明為凹函數(shù)證: (1)首先由定義來(lái)證明，任取兩點(diǎn)a1,a2,看下式是否成立？或由于，故顯然，不管a1,a2取什么值，總有（）式成立，故f(x1)=-x12為凹函數(shù)，同理可證f(x2)=-x22也是凹函數(shù)或第二十九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸函數(shù)

8、的判定證: ()用定理2.2.4來(lái)證明，由于故海賽矩陣處處負(fù)定，故f(X)為嚴(yán)格凹函數(shù)第三十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸函數(shù)的判定證: ()用定理5.2.3來(lái)證明，任意取第一點(diǎn)，第二點(diǎn)，這樣現(xiàn)看下式是否成立或或證: ()用定理2.2.3來(lái)證明，任意取第一點(diǎn)，第二點(diǎn)，這樣第三十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸函數(shù)的判定不管a1,a2和b1,b2取什么值，上式均成立從而證明f(）是凹函數(shù)或第三十二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸規(guī)劃及其性質(zhì)約束集如果(MP)的約束集X是凸集，目標(biāo)函數(shù)f是X上的凸函數(shù)，則(MP)叫做非線性凸規(guī)劃，或簡(jiǎn)稱(chēng)為凸規(guī)劃。

9、第三十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月定理 2.2.6 凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。第三十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸規(guī)劃及其性質(zhì)由于線性函數(shù)也既是凸函數(shù)，又是凹函數(shù)，故線性規(guī)劃也屬于凸規(guī)劃第三十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸規(guī)劃及其性質(zhì)例6試分析非線性規(guī)劃解：f(X)和g2(X)的海賽矩陣的行列式是第三十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月凸規(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)

10、函數(shù)的最優(yōu)值為f(X*)=3.8.g1(X)g2(X)=0C目標(biāo)函數(shù)等值線第三十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月算法及有關(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),記為這稱(chēng)為第k+1次迭代這個(gè)過(guò)程無(wú)限進(jìn)行下去，就產(chǎn)生一個(gè)點(diǎn)列，其中規(guī)則稱(chēng)為算法若收斂于問(wèn)題的最優(yōu)解，就稱(chēng)算法在上是收斂的，否則是發(fā)散的第三十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月算法及有關(guān)概念一種算法除了滿(mǎn)足計(jì)算終止準(zhǔn)則的迭代點(diǎn)外,還應(yīng)滿(mǎn)足:下降算法:若對(duì)于每個(gè)k,都有 ,則稱(chēng)A為下降迭代

11、算法,簡(jiǎn)稱(chēng)下降算法.許多最優(yōu)化方法都采用將多維問(wèn)題轉(zhuǎn)化為一維問(wèn)題的方法來(lái)求解.第三十九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月算法及有關(guān)概念 如:設(shè)第k次迭代點(diǎn)xk已求得,若它不滿(mǎn)足終止準(zhǔn)則,在該點(diǎn)必存在下降方向.對(duì)于可微目標(biāo)函數(shù),即是滿(mǎn)足 的d. 按某種規(guī)則從中選取一個(gè),例如dk,再沿這個(gè)方向適當(dāng)邁進(jìn)一步,即在直線 上適當(dāng)確定一個(gè)新點(diǎn) , 使 那我們就說(shuō)完成了第k+1次迭代,其中 稱(chēng)為步長(zhǎng)因子.第四十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月算法及有關(guān)概念迭代過(guò)程中應(yīng)滿(mǎn)足兩個(gè)準(zhǔn)則: 1 是下降方向dk的選取; 2是步長(zhǎng)因子 的選取 各種迭代法的區(qū)別就在于得出方向 dk 與步 長(zhǎng) 的

12、方式不同.對(duì)于非線性規(guī)劃,總結(jié)出:第四十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月非線性規(guī)劃方法概述第四十二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月非線性規(guī)劃基本迭代格式第四十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月無(wú)約束優(yōu)化:最優(yōu)解的分類(lèi)和條件給定一個(gè)函數(shù) f(x),尋找 x* 使得 f(x*)最小，即其中局部最優(yōu)解全局最優(yōu)解必要條件x*f(x)xlxgo充分條件Hessian陣最優(yōu)解在可行域邊界上取得時(shí)不能用無(wú)約束優(yōu)化方法求解第四十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月2 迭代法中直線搜索及其性質(zhì)： 在搜索方向已經(jīng)確定的前提下,步長(zhǎng)因子的選取有多種方法,如 i

13、)取步長(zhǎng)因子為某個(gè)常數(shù),但不能保證使目標(biāo)函數(shù)值下降; ii)可接受點(diǎn)算法，只要能使目標(biāo)函數(shù)下降，可任意選取步長(zhǎng);iii)基于沿搜索方向使目標(biāo)函數(shù)值下降最多，沿射線 求目標(biāo)函數(shù)的極小值：第四十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月2 迭代法中直線搜索及其性質(zhì)： 由于這項(xiàng)工作是求以為變量的一元函數(shù)的極小點(diǎn)，故稱(chēng)這一過(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)生：則有第四十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月3 收斂速度

14、 一個(gè)算法不光能收斂于解,還必須以較快的速度收斂于解,這才是好的算法; 我們用以下收斂的階來(lái)度量一個(gè)算法的收斂速度.第四十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月3 收斂速度 定義:設(shè)序列 收斂于 ,而且 若 ,則稱(chēng) 為線性收斂的, 為收斂比; 若 ,則稱(chēng) 為超線性收斂. 定義:設(shè)序列 收斂于 ,若對(duì)于某個(gè)實(shí)數(shù) ,有 則稱(chēng)序列 為 階收斂的第四十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月3 收斂速度 一般來(lái)說(shuō),線性收斂是比較慢的,而二階收斂則是很快的,超線性收斂居中,如果一個(gè)算法具有超線性以上的收斂速度,我們就認(rèn)為它是一個(gè)很好的算法了.第四十九張，PPT共一百三十九頁(yè)，創(chuàng)作于20

15、22年6月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)則第五十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月2.2 一維搜索方法精確一維搜索方法 0.618法 Newton法非精確一維搜索方法 Goldstein法 Armijo法第五十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月一維搜索 上節(jié)提到,在大多數(shù)無(wú)約束極值的算

16、法中,為了確定最優(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)集表示為: 第五十二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月 求 在直線L上的極小點(diǎn)轉(zhuǎn)化為求一元函數(shù) 的極小點(diǎn). 如果 的極小點(diǎn)為 ,通常稱(chēng) 為沿方向 的步長(zhǎng)因子 或簡(jiǎn)稱(chēng)步長(zhǎng). 函數(shù) 在直線上的極小點(diǎn)就是 一維搜索的方法一般有以下幾類(lèi)： 1. 數(shù)學(xué)分析中所講的方法，即

17、解方程，此方法稱(chēng)為精確線性搜索. 2. 試探法: 按照某種方式試探點(diǎn),通過(guò)一系列試探點(diǎn)的比較確定極小點(diǎn).第五十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月 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)?為極小點(diǎn),若: 此時(shí) 為極大點(diǎn).第五十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月 我們找到了一個(gè)區(qū)間 ,具有性質(zhì) 則在 間必然有 的極小點(diǎn) ,且 .為了找

18、到 , 我們?nèi)?. 1. 若 ,則在 中有極小點(diǎn), 2 .若 ,則在 中有極小點(diǎn).y=f(x)00 xy第五十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月 若情形1滿(mǎn)足時(shí),此時(shí)以 作為新的區(qū)間; 若情形2滿(mǎn)足時(shí),此時(shí)以 作為新的區(qū)間. 繼續(xù)上述過(guò)程,逐步將區(qū)間換小,當(dāng)區(qū)間 充分小時(shí),或者當(dāng) 充分小時(shí),即可將區(qū)間 中點(diǎn)取做極小點(diǎn)的近似,此時(shí)有:0 xy0 xy第五十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月 注:也可以用以下的收斂準(zhǔn)則: 1 . 成立, 2. 成立. 但是我們?nèi)绾蝸?lái)確定初始區(qū)間 呢?下面我們將解決這個(gè)問(wèn)題。 第五十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月搜索區(qū)間

19、 的選取可采用如下的進(jìn)退算法：給定初始點(diǎn) ，初始步長(zhǎng) ，求搜索區(qū)間 ：1）計(jì)算 2）若 ,(此時(shí)稱(chēng)搜索成功，下一步搜索就大步前進(jìn))，則步長(zhǎng)加倍，計(jì)算 若 ， 則 ；否則步長(zhǎng)再加倍，并重復(fù)上面的運(yùn)算；第五十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月3）若 ,(此時(shí)稱(chēng)搜索失敗，下一步就小步后退),則步長(zhǎng)縮為原來(lái)的1/4，并改變符號(hào)，即新步長(zhǎng)為 ，若 則 ；否則步長(zhǎng)再加倍， 繼續(xù)后退。第五十九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月二、0.618法（近似黃金分割法）單谷函數(shù)退 出前一頁(yè)后一頁(yè)第六十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月搜索法求解：或基本過(guò)程：給出a,b,使得t*在

20、a,b中。a,b稱(chēng)為搜索區(qū)間。迭代縮短a,b的長(zhǎng)度。當(dāng)a,b的長(zhǎng)度小于某個(gè)預(yù)設(shè)的值，或者導(dǎo)數(shù)的絕對(duì)值小于某個(gè)預(yù)設(shè)的正數(shù)，則迭代終止。退 出前一頁(yè)后一頁(yè)第六十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月假定：已經(jīng)確定了單谷區(qū)間a,bt1t2ababt1t2新搜索區(qū)間為a,t2新搜索區(qū)間為t1,b退 出前一頁(yè)后一頁(yè)第六十二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月區(qū)間縮小比例的確定：區(qū)間縮短比例為(t2-a)/(b-a)縮短比例為(b-t1)/(b-a)縮短比例 滿(mǎn)足：每次插入搜索點(diǎn)使得兩個(gè)區(qū)間a,t2和t1,b相等；每次迭代都以相等的比例縮小區(qū)間。0.618法t1t2ababt1t2退

21、出前一頁(yè)后一頁(yè)第六十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月確定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è)第六十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月例：解：t1t230t1、第一輪：t1=1.146, t2=1.854t200.5退 出前一頁(yè)后一頁(yè)第六十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月2、第二輪：t2=1.146, t1=0.708t20=1.1460.53、第三輪：t1=0.438, t2=0.

22、708b-t1=1.146-0.4380.51.8540tt2t11.4160tt2t1退 出前一頁(yè)后一頁(yè)第六十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月4、第四輪：t2=0.876, t1=0.708b-t1=1.146-0.7080.5輸出：t*=t2=0.876為最優(yōu)解，最優(yōu)值為-0.079801.416tt1t2退 出前一頁(yè)后一頁(yè)第六十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月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)=-360，故 x=2 為f(x

23、)的極大值點(diǎn)，fmax=100 用直接法中的黃金分割法：令 n-1=，得n=1+(lg)/(lg)5.78442 約6步即可，計(jì)算結(jié)果見(jiàn)下表：kakbkf(ak)f(bk)pk= bk- akpk/ p0 x1k=ak+ pkx2k=bk- pkf (x2k) f (x1k)0032882311.8541.14686.999.62f(x)xo3x1x211.146386.9821.8540.6182.2921.85499.62 98.4621.1462.29286.998.461.1460.3821.8541.58496.8999.6231.5842.29296.8998.460.7080.2

24、362.0221.85499.62 99.9941.8542.29299.6298.460.4380.1462.1252.02299.99 98.7251.8542.12599.6299.720.2710.0903第六十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月第六十九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月第七十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月第七十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月第七十二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月三、Newton法Newton法基本思想：用探索點(diǎn)tk處的二階Taylor展開(kāi)式近似代替目標(biāo)函數(shù)，以展開(kāi)式的最小點(diǎn)為新

25、的探索點(diǎn)。退 出前一頁(yè)后一頁(yè)第七十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月解題步驟：給定初始點(diǎn)t1和精度是是停止，輸出t1是否停止，解題失敗否停止，輸出t2否退 出前一頁(yè)后一頁(yè)第七十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月例：解：取t1=1,計(jì)算：迭代過(guò)程如下表：1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411退 出前一頁(yè)后一頁(yè)第七十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月第七十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月3、非精確一維搜索法數(shù)值方法的關(guān)鍵是從一個(gè)點(diǎn)迭代到下一個(gè)點(diǎn)。確定下一個(gè)點(diǎn)的關(guān)鍵

26、是確定搜索方向和步長(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)題不需要太高的精度，只要滿(mǎn)足某些更寬松的精度要求即可。這樣的搜索方法稱(chēng)之為非精確一維搜索方法退 出前一頁(yè)后一頁(yè)第七十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月Goldstein法原理：yt0bcdaY=(0)+ (0)tY=(0)+ m2(0)tY=(0)+ m1(0)t退 出前一頁(yè)后一頁(yè)第七十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月是Goldstein算法確定m1,m2,t0, a=0,b=+(t0

27、) (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è)第七十九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月Goldstein法步驟第八十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月Armijo法第八十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月82無(wú)約束條件下多變量函數(shù)尋優(yōu)一、爬山法原理： 通過(guò)點(diǎn)的直接移動(dòng)，逐步改善目標(biāo)函數(shù)取值，直至達(dá)到極值點(diǎn)為止。 由以下二部分組成： 選定搜索方向； 在選定的方向上爬山搜索。二、變量輪換法(或降維法

28、):選擇與坐標(biāo)軸平行的方向?yàn)樗阉鞣较?設(shè) S=f(X)=f(x1,x2,xn)，極值點(diǎn)存在的區(qū)間為 x1*a1,b1，x2*a2,b2， ，xn*an,bn1、原理：從起點(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)行下去，直至滿(mǎn)足給定的精度 為止 |f(X(k) -f(X(k-1)| 或 |S(k)-S(k-1)| 第八十二張，PPT共一百三十九頁(yè)，創(chuàng)

29、作于2022年6月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 第二步：如此交替搜索，直至滿(mǎn)足給定精度 為止 |f(X(k)

30、-f(X(k-1)| 或 |S(k)-S(k-1)|ox1X(0)X(1)X(2)X(3)X(4)x2第八十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月84例 求 S = f(x) = x12 + x22 - x1x2 -10 x1 - 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 - 1

31、2x1 +56，尋優(yōu)得 x1(2)=6 于是 X(2)=(x1(2),x2(1)T=(6,2)T ，S(2)=f(X(2)=20 如此交替搜索，直至滿(mǎn)足給定精度 =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)下表：第八十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月85k固定的xi單變量的目標(biāo)函數(shù)f(xj)求得極點(diǎn)xj目標(biāo)值S(k)|S( k ) - S( k-1 )|12345678x1=x1(0)=0 x2=x2(1)=2x

32、1=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 - 10 x2 +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.50 x2=x2(1)=2x1=x1(2)=6x2=x2(3

33、)=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è)有利方向。第八十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月最速下降法第八十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月是X(

34、k)處函數(shù)值下降最快的方向。當(dāng) 時(shí)，p(k)是 f (X)在 X(k) 處的下降方向。函數(shù)f (X)在X(k)處的負(fù)梯度方向梯度的性質(zhì)：1、迭代原理證明：結(jié)論：一元函數(shù)泰勒公式：第八十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月2.迭代原理最優(yōu)步長(zhǎng)第八十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月最速下降法迭代原理：一維搜索找極小點(diǎn) ：1)確定0 , 1, 精度0.1 2)用0.618法得到 040.53184第八十九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月最速下降法迭代原理： 第九十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月線性規(guī)劃3-42.迭代原理最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)第九十一

35、張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月線性收斂2.迭代原理最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)得到一個(gè)點(diǎn)列：可以證明：第九十二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月2.迭代原理證明：第九十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月3.迭代步驟第九十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月3.迭代步驟注釋?zhuān)?一階必要條件)10 停機(jī)準(zhǔn)則：設(shè) 連續(xù)(即 f(X)連續(xù)可微)第九十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月注釋?zhuān)?.迭代步驟一維搜索最優(yōu)解的梯度 與搜索方向 正交20 結(jié)論：證明：第九十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月注釋?zhuān)鹤钏傧陆捣ǖ娜魏蝺蓚€(gè)相鄰搜索方向

36、正交(垂直)3.迭代步驟30 結(jié)論：第九十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月注釋?zhuān)?.迭代步驟40 將一維搜索用于正定二次函數(shù)：則可以得到 的表達(dá)式： 第九十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月線性規(guī)劃3-4證明：3.迭代步驟40 將一維搜索用于正定二次函數(shù)：則可以得到 的表達(dá)式： 注釋?zhuān)涸摴骄哂衅毡樾缘诰攀艔?，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月注釋?zhuān)?.迭代步驟40 將一維搜索用于正定二次函數(shù)：則可以得到 的表達(dá)式： 第一百?gòu)?，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月注釋?zhuān)?.迭代步驟50 將最速下降法用于正定二次函數(shù)：則可以得到 的表達(dá)式： 第一百零

37、一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月注釋?zhuān)?.迭代步驟50 最速下降法，Newton法，擬Newton法，共軛梯度法的區(qū)別就是搜索方向p(k)取得不同。第一百零二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月4.舉例例3-10解：用最速下降法求 的極小點(diǎn)，迭代兩次。第一百零三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月例:試用最速下降法求 的極小點(diǎn),迭代兩次,計(jì)算每個(gè)迭代點(diǎn)的函數(shù)值,梯度及模,并驗(yàn)證相鄰兩個(gè)搜索方向是正交的. 解:給初始點(diǎn) , , , , , 利用必要條件：第一百零四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月于是： 由 解得 第一百零五張，PPT共一百三十九頁(yè)

38、，創(chuàng)作于2022年6月驗(yàn)證搜索方向的正交性:第一百零六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月107例 求 S = f(x) = x12 + x22 - x1x2 -10 x1 - 4x2 + 60 的極小值點(diǎn)， =0.1解: 從點(diǎn) X(1) 出發(fā)，照此進(jìn)行下去，直至滿(mǎn)足給定的精度 =0.1 為止 |f(X(k+1) -f(X(k)|0.1 或 |G(k) |0.1 第一百零七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月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)

39、離極點(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

40、)x2第一百零八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月第一百零九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月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)附近，沿

41、搜索方向P(0)上巳得到一個(gè) 切點(diǎn)X(1)，則只要得出通過(guò)極值點(diǎn)的連線方向 P(1),在此方向上尋優(yōu),可一步直達(dá)極值點(diǎn)。 而這個(gè)連線方向P(1)是上一次搜索方向P(0)的 共軛方向。 第一百一十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月111 共軛方向的定義： 1、定義：設(shè) X,Y 是n維向量空間En中兩個(gè)向量，A 為nn對(duì)稱(chēng)正定矩陣， 若 XTAY = 0 ，則稱(chēng)向量X與Y對(duì)于矩陣A共軛。 特例：若 A = I，得 XTY = 0，則稱(chēng)向量X與Y正交。 2、幾何意義：共軛方向是通過(guò)極值點(diǎn)的方向。 尋優(yōu)原理： 設(shè)n元函數(shù) S=f(X)=f(x1,x2,xn),在極值點(diǎn)X*附近可用一個(gè)二次函

42、數(shù)逼近其中 H 為nn對(duì)稱(chēng)正定矩陣第一百一十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月112特別：對(duì)二元二次函數(shù) S=f(X)=f(x1，x2) 從某點(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(

43、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ù)逼近。第一百一十二張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月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 法，由Flet

44、cher和Reeves提出， 可避免海賽矩陣 H 的計(jì)算，方便地確定共軛方向，簡(jiǎn)單有效。第一百一十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月114 3、搜索過(guò)程： 從X(0)出發(fā)： 從X(1)出發(fā)：第一百一十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月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)) 用共軛梯度法。 一般有：第一百

45、一十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月第一百一十六張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月117例 求 S = f(x) = x12 + x22 - x1x2 -10 x1 - 4x2 + 60 的極小值點(diǎn)。解: 第一百一十七張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月例2 用共軛梯度法求解 ,取 解:用共軛梯度法的第一步和最速下降法是相同的, 故由前例知: 第一百一十八張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月因?yàn)?較大,還需要迭代,下一探索方向由共軛梯度并利用 和 組合而成. 其中 所以由 第一百一十九張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月由： 把 分別代

46、入 的表達(dá)式中求得 ,因 為 ,所以迭代終止, 就是 所求的極小點(diǎn).第一百二十張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月共軛梯度法的特點(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)始迭代,這樣一般都可得到較好的效果.第一百二十一張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月浙江理工大學(xué)經(jīng)濟(jì)管理學(xué)院1222.4 牛頓法與擬牛頓法牛頓方向四、牛頓法第一百二十二張，PPT共一百

47、三十九頁(yè)，創(chuàng)作于2022年6月浙江理工大學(xué)經(jīng)濟(jì)管理學(xué)院123四、牛頓法（1）牛頓方向第一百二十三張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月浙江理工大學(xué)經(jīng)濟(jì)管理學(xué)院1242.3 無(wú)約束極值問(wèn)題四、牛頓法（2）廣義牛頓法步驟當(dāng)一維搜索是精確的，牛頓法為二階收斂。第一百二十四張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月浙江理工大學(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ì)算塞黑矩陣的逆工作量太大。可采用其他方法，如共軛梯度法，變尺度法等。第一百二十五張，PPT共一百三十九頁(yè)，創(chuàng)作于2022年6月 定理5.3 ： 設(shè) ,且 正定,記 是由修改的牛頓法 所得到的迭代點(diǎn)列,若水平集 有界,則 必有 聚點(diǎn),且任一聚點(diǎn) 必滿(mǎ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í)需要使用改