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

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

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

按某種規(guī)則從中選取一個,例如dk,再沿這個方向適當邁進一步,即在直線上適當確定一個新點,

使那我們就說完成了第k+1次迭代,其中稱為步長因子.第40頁，共139頁，2022年，5月20日，3點3分，星期五算法及有關概念迭代過程中應滿足兩個準則:1是下降方向dk的選取;2是步長因子

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

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

iii)基于沿搜索方向使目標函數(shù)值下降最多，沿射線求目標函數(shù)的極小值：第45頁，共139頁，2022年，5月20日，3點3分，星期五2迭代法中直線搜索及其性質：

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

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

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

我們用以下收斂的階來度量一個算法的收斂速度.第47頁，共139頁，2022年，5月20日，3點3分，星期五3收斂速度

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

若,則稱為超線性收斂.

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

則稱序列為階收斂的第48頁，共139頁，2022年，5月20日，3點3分，星期五3收斂速度

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

0.618法

Newton法非精確一維搜索方法

Goldstein法

Armijo法第51頁，共139頁，2022年，5月20日，3點3分，星期五一維搜索

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

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

一維搜索可歸結為單變量函數(shù)求極小的問題,設目標函數(shù)為,過點沿方向的直線可用點集表示為:

第52頁，共139頁，2022年，5月20日，3點3分，星期五求在直線L上的極小點轉化為求一元函數(shù)

的極小點.

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

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

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

按照某種方式試探點,通過一系列試探點的比較確定極小點.第53頁，共139頁，2022年，5月20日，3點3分，星期五

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

用比較簡單的曲線近似代替原來的曲線,用近似曲線的極小點來估計原來的極小點.

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

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

注:因為為極小點,若:

此時為極大點.第54頁，共139頁，2022年，5月20日，3點3分，星期五

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

我們取.1.若,則在中有極小點,

2.若,則在中有極小點.y=f(x)00xy第55頁，共139頁，2022年，5月20日，3點3分，星期五若情形1滿足時,此時以作為新的區(qū)間;

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

繼續(xù)上述過程,逐步將區(qū)間換小,當區(qū)間充分小時,或者當充分小時,即可將區(qū)間中點取做極小點的近似,此時有:0xy0xy第56頁，共139頁，2022年，5月20日，3點3分，星期五注:也可以用以下的收斂準則:1.成立,

2.成立.

但是我們如何來確定初始區(qū)間呢?下面我們將解決這個問題。

第57頁，共139頁，2022年，5月20日，3點3分，星期五搜索區(qū)間的選取可采用如下的進—退算法：給定初始點，初始步長，求搜索區(qū)間：1）計算2）若,(此時稱搜索成功，下一步搜索就大步前進)，則步長加倍，計算若，則；否則步長再加倍，并重復上面的運算；第58頁，共139頁，2022年，5月20日，3點3分，星期五3）若,(此時稱搜索失敗，下一步就小步后退),則步長縮為原來的1/4，并改變符號，即新步長為，若

則；否則步長再加倍，繼續(xù)后退。第59頁，共139頁，2022年，5月20日，3點3分，星期五二、0.618法（近似黃金分割法）單谷函數(shù)退出前一頁后一頁第60頁，共139頁，2022年，5月20日，3點3分，星期五搜索法求解：或基本過程：給出[a,b],使得t*在[a,b]中。[a,b]稱為搜索區(qū)間。迭代縮短[a,b]的長度。當[a,b]的長度小于某個預設的值，或者導數(shù)的絕對值小于某個預設的正數(shù)，則迭代終止。退出前一頁后一頁第61頁，共139頁，2022年，5月20日，3點3分，星期五假定：已經確定了單谷區(qū)間[a,b]t1t2ababt1t2新搜索區(qū)間為[a,t2]新搜索區(qū)間為[t1,b]退出前一頁后一頁第62頁，共139頁，2022年，5月20日，3點3分，星期五區(qū)間縮小比例的確定：區(qū)間縮短比例為(t2-a)/(b-a)縮短比例為(b-t1)/(b-a)縮短比例滿足：每次插入搜索點使得兩個區(qū)間[a,t2]和[t1,b]相等；每次迭代都以相等的比例縮小區(qū)間。0.618法t1t2ababt1t2退出前一頁后一頁第63頁，共139頁，2022年，5月20日，3點3分，星期五確定[a,b],計算探索點t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解題步驟：是否是停止，輸出t1否以[a,t2]為新的搜索區(qū)間是停止，輸出t2否以[t1,b]為新的搜索區(qū)間退出前一頁后一頁第64頁，共139頁，2022年，5月20日，3點3分，星期五例：解：t1t230t1、第一輪：t1=1.146,t2=1.854t2－0>0.5退出前一頁后一頁第65頁，共139頁，2022年，5月20日，3點3分，星期五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退出前一頁后一頁第66頁，共139頁，2022年，5月20日，3點3分，星期五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退出前一頁后一頁第67頁，共139頁，2022年，5月20日，3點3分，星期五68例求解f(x)=-18x2+72x+28的極大值點，≤0.1，起始搜索區(qū)間為[0,3]解：①用間接法：令f’(x)=-36x+72=0，得駐點x=2

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

約6步即可，計算結果見下表：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頁，共139頁，2022年，5月20日，3點3分，星期五第69頁，共139頁，2022年，5月20日，3點3分，星期五第70頁，共139頁，2022年，5月20日，3點3分，星期五第71頁，共139頁，2022年，5月20日，3點3分，星期五第72頁，共139頁，2022年，5月20日，3點3分，星期五三、Newton法Newton法基本思想：用探索點tk處的二階Taylor展開式近似代替目標函數(shù)，以展開式的最小點為新的探索點。退出前一頁后一頁第73頁，共139頁，2022年，5月20日，3點3分，星期五解題步驟：給定初始點t1和精度是是停止，輸出t1是否停止，解題失敗否停止，輸出t2否退出前一頁后一頁第74頁，共139頁，2022年，5月20日，3點3分，星期五例：解：取t1=1,計算：迭代過程如下表：1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411退出前一頁后一頁第75頁，共139頁，2022年，5月20日，3點3分，星期五第76頁，共139頁，2022年，5月20日，3點3分，星期五3、非精確一維搜索法數(shù)值方法的關鍵是從一個點迭代到下一個點。確定下一個點的關鍵是確定搜索方向和步長如果已經確定了搜索方向pk,則只要確定一個最佳的步長即可。所謂的最佳步長即是在pk方向上走一個最好的長度使得目標函數(shù)下降的最多，即下述的最優(yōu)化問題：這樣的最優(yōu)化問題不需要太高的精度，只要滿足某些更寬松的精度要求即可。這樣的搜索方法稱之為非精確一維搜索方法退出前一頁后一頁第77頁，共139頁，2022年，5月20日，3點3分，星期五Goldstein法原理：yt0bcdaY=(0)+′(0)tY=(0)+m2′(0)tY=(0)+m1′(0)t退出前一頁后一頁第78頁，共139頁，2022年，5月20日，3點3分，星期五是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)退出前一頁后一頁第79頁，共139頁，2022年，5月20日，3點3分，星期五Goldstein法步驟第80頁，共139頁，2022年，5月20日，3點3分，星期五Armijo法第81頁，共139頁，2022年，5月20日，3點3分，星期五82無約束條件下多變量函數(shù)尋優(yōu)一、爬山法原理：通過點的直接移動，逐步改善目標函數(shù)取值，直至達到極值點為止。由以下二部分組成：①選定搜索方向；②在選定的方向上爬山搜索。二、變量輪換法(或降維法):選擇與坐標軸平行的方向為搜索方向設S=f(X)=f(x1,x2,…,xn)，極值點存在的區(qū)間為

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

，xn*[an,bn]1、原理：①從起點X(0)出發(fā)，沿平行于x1

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

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

|f(X(k))

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

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

第82頁，共139頁，2022年，5月20日，3點3分，星期五83

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

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

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

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

此時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)|＜ox1X(0)X(1)X(2)X(3)X(4)x2第83頁，共139頁，2022年，5月20日，3點3分，星期五84例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的極小值點，=0.01解：設起始點X(0)=(0,0)T，用變量輪換法計算：①先固定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

最后得極小點X*=(8,6)T，f(X*)=8ox1X(0)X(1)X(2)X(3)X(4)x2計算結果見下表：第84頁，共139頁，2022年，5月20日，3點3分，星期五85k固定的xi單變量的目標函數(shù)f(xj)求得極點xj目標值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缺點：①很大程度上取決于目標函數(shù)性質。目標函數(shù)等高線的性質很重要。②道路迂回曲折，多次變換方向，在極點附近，目標值改進更小，收斂速度慢。故不是一個有利方向。第85頁，共139頁，2022年，5月20日，3點3分，星期五最速下降法第86頁，共139頁，2022年，5月20日，3點3分，星期五是X(k)處函數(shù)值下降最快的方向。當時，p(k)是f(X)在X(k)處的下降方向。函數(shù)f(X)在X(k)處的負梯度方向梯度的性質：1、迭代原理證明：結論：一元函數(shù)泰勒公式：第87頁，共139頁，2022年，5月20日，3點3分，星期五2.迭代原理最優(yōu)步長第88頁，共139頁，2022年，5月20日，3點3分，星期五最速下降法迭代原理：一維搜索找極小點：1)確定[0,1],精度0.12)用0.618法得到

040.53184第89頁，共139頁，2022年，5月20日，3點3分，星期五最速下降法迭代原理：

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

解:給初始點,,,,,

利用必要條件：第104頁，共139頁，2022年，5月20日，3點3分，星期五于是：由解得

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

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

第107頁，共139頁，2022年，5月20日，3點3分，星期五108計算結果見下表：缺點：①搜索效果比變量輪換法快，但愈接近極值點，步長愈小，目標值改進愈小。當遇到強交互作用時，不是有效的方法;當遇到山脊時，會慢慢爬行。②在遠離極點時，收斂速度較快;在極點附近，收斂速度不快。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頁，共139頁，2022年，5月20日，3點3分，星期五第109頁，共139頁，2022年，5月20日，3點3分，星期五110四、共軛梯度法:選擇共軛方向為搜索方向㈠問題的提出：在極值點附近，如何加快收斂速度，須對函數(shù)在極值點附近的性質進行研究。設有n維目標函數(shù)S=f(X)=f(x1,x2,…,xn),在極值點X*附近展開成泰勒級數(shù)：

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

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

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

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

故由前例知:

第118頁，共139頁，2022年，5月20日，3點3分，星期五因為較大,還需要迭代,下一探索方向由共軛梯度并利用和組合而成.

其中

所以由

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

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

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

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

每次迭代要進行矩陣求逆運算.第126頁，共139頁，2022年，5月20日，3點3分，星期五

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

修改的牛頓法具有全局收斂性和收斂快的特點,但還存在一個

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

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

在迭代中,利用一階導數(shù)按某中規(guī)則得到.第127頁，共139頁，2022年，5月20日，3點3分，星期五

確定的一種自然想法是將作為的近似來構造,注意到是對稱的,且有關系即若記=,,,必須滿足:1.對稱正定

2.滿足擬牛頓方程

(2.30)

另外,再設想是由經過簡單修正而得到的,即校正矩陣自然應是對稱矩陣,由(2.30)式應滿足第128頁，共139頁，2022年，5月20日，3點3分，星期五

(2.31)

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

其最常見的算法所謂D