§2-4無約束優(yōu)化方法

無約束優(yōu)化問題的下降迭代算法具有統(tǒng)一的迭代格式，問題之一是選擇搜索方向。根據(jù)搜索方向的不同構成方式，分：

1)導數(shù)法(解析法)

利用目標函數(shù)的一階導數(shù)或二階導數(shù)信息構造搜索方向的方法。

梯度法、牛頓法、共軛梯度法和變尺度法…

條件：

①目標函數(shù)求導容易；②目標函數(shù)一階導數(shù)連續(xù)；③目標函數(shù)是設計變量的顯函數(shù)。

§2-4無約束優(yōu)化方法無約束優(yōu)1§2-4無約束優(yōu)化方法

2)模式法(直接法)

通過比較幾個已知點的函數(shù)值構造搜索方向的算法。

鮑威爾法。構成搜索方向的信息僅僅是幾個有限點上的函數(shù)值，難于得到較理想的搜索方向。一般迭代次數(shù)較多，收斂速度較慢。Rosenbrock函數(shù)x1x2§2-4無約束優(yōu)化方法2)模式法(2一、梯度法

迭代方向是由迭代點的負梯度構成——最速下降法。梯度法迭代公式一、梯度法迭代方向是由迭代點的負梯度構成——最速下3一、梯度法根據(jù)極值的必要條件和復合函數(shù)求導公式，有相鄰兩迭代點的梯度正交最優(yōu)步長因子k，由一維搜索確定一、梯度法根據(jù)極值的必要條件和復合函數(shù)求導公式，有相鄰兩迭代4一、梯度法

特點：

(1)算法簡單，只計算目標函數(shù)一階導數(shù)，占用內(nèi)存少；(2)初始點任選；(3)初始迭代速度快；(4)

搜索路線正交，收斂速度越來越慢。一、梯度法特點：5梯度法程序框圖梯度法6一、梯度法例

用梯度法求解解：①第一次迭代

=0.1一、梯度法例用梯度法求解解：①第一次迭代=0.7一、梯度法②

第二次迭代X(1)為初始點，進行迭代……一、梯度法②

第二次迭代8二、牛頓法

梯度法除在最初幾次迭代中函數(shù)值下降很快外，總的來說下降不快，且愈接近極值點下降愈慢。尋求使目標函數(shù)值下降更快的方法→牛頓法。

基本思路：——利用二次曲線逐點近似原目標函數(shù)，以二次曲線的極小點近似原目標函數(shù)的極小點并逐漸逼近該點。牛頓法分基本牛頓法和阻尼牛頓法。二、牛頓法梯度法除在最初幾次迭代中函數(shù)值下91.基本牛頓法函數(shù)f(X)在點X(k)處展開成泰勒二次近似式設X(k+1)是函數(shù)的極小點，有用基本牛頓法求解正定二次函數(shù)時，無論從哪個初始點出發(fā)，一次計算即可達到極小點。1.基本牛頓法函數(shù)f(X)在點X(k)處展開成泰勒二次近101．基本牛頓法

對于非線性正定函數(shù)，二階泰勒展開式只是原函數(shù)的近似式，得到X(k+1)只是原函數(shù)的近似極小點。以此點作為下一次迭代的起始點X(k)，能夠加快逼近的速度。對于非正定函數(shù)，為保證牛頓方向是函數(shù)值下降的方向，海賽矩陣必須正定。采用定步長，即使牛頓方向是函數(shù)值下降的方向，也不能保證函數(shù)值下降，即得到的點并不能始終保持函數(shù)的下降性→基本牛頓法有可能失效。1．基本牛頓法對于非線性正定函數(shù)，二階泰112．阻尼牛頓法在迭代中引入步長因子和一維搜索。

阻尼牛頓法在每次迭代中沿牛頓方向作一維搜索，保證迭代點的嚴格下降性，適用于任何函數(shù)，且保證得到的迭代點更加靠近極小點，具有更加理想的收斂效果。牛頓法均指阻尼牛頓法。2．阻尼牛頓法在迭代中引入步長因子和一維搜索。122．阻尼牛頓法阻尼牛頓法程序框圖特點：

(1)具有二階收斂性，收斂速度快；(2)在極值點附近有效；(3)計算復雜；(4)X(0)位置和函數(shù)性態(tài)影響計算結果。2．阻尼牛頓法阻尼牛頓法特點：13二、牛頓法例牛頓法求解解

(1)基本牛頓法

=0.1二、牛頓法例牛頓法求解解(1)基本牛頓法=014二、牛頓法(2)阻尼牛頓法基本牛頓法計算得二、牛頓法(2)阻尼牛頓法15二、牛頓法解得=1

二、牛頓法解得=116三、變尺度法

變尺度法是擬牛頓法。克服牛頓法的缺點，繼承其收斂快的優(yōu)點，具有超線性收斂速度。1959年，Davidon提出變尺度法，F(xiàn)letcher和Powell改進——DFP法。

優(yōu)化算法一般迭代公式

三、變尺度法變尺度法是擬牛頓法。優(yōu)化算法一般迭代公17三、變尺度法梯度法，搜索方向為負梯度方向牛頓法，搜索方向為牛頓方向統(tǒng)一形式三、變尺度法梯度法，搜索方向為負梯度方向牛頓法，搜索方向為18三、變尺度法——梯度法

——牛頓法

在迭代開始時，按負梯度方向搜索；爾后每次迭代時不斷調(diào)整A(k)，修正搜索方向，使A(k)逐步逼近目標函數(shù)的海賽矩陣之逆矩陣；當?shù)c臨近極小點時，構成的方向就近似為牛頓方向，直指極小點。整個迭代過程收斂速度很快。矩陣A(k)代替海賽矩陣之逆矩陣，且迭代過程中不斷改變→變尺度矩陣。三、變尺度法——梯度法——牛頓法在迭代開始時，按19三、變尺度法關鍵：構造變尺度矩陣1.變尺度矩陣構造原則1)算法具有下降性

——為了使方向S(k)=-A(k)g(k)為目標函數(shù)值的下降方向，構造的變尺度矩陣A(k)應為正定對稱矩陣。

若目標函數(shù)f(X)的值沿S(k)下降，則S(k)與X(k)點的負梯度方向之間的夾角應為銳角，即只要A(k)正定，S(k)=-A(k)g(k)必為目標函數(shù)值的下降方向。三、變尺度法關鍵：構造變尺度矩陣1.變尺度矩陣構造原20三、變尺度法2）計算方便性——構造的變尺度矩陣A(k)應便于計算，在迭代過程中應逐漸地逼近海賽矩陣之逆矩陣。取單位矩陣I為初始矩陣A(0)E(k)——校正矩陣。2.變尺度矩陣構造Davidon提出，F(xiàn)letcher和Powell修正，校正矩陣E(k)

三、變尺度法2）計算方便性——構造的變尺度矩陣A(k21三、變尺度法DFP變尺度法在函數(shù)f(X)梯度易求的情況下，非常有效。對于多維問題(n>100)，收斂快，效果佳→無約束極值問題優(yōu)化的最好方法之一。計算程序較復雜，需要較大的存儲量，特別是在有舍入誤差時，存在數(shù)值穩(wěn)定性不夠理想的情況。

三、變尺度法DFP變尺度法在函數(shù)f(X)梯度易求的22三、變尺度法

BFGS變尺度法(Broyden、Fletcher、Goldfarb、Shanno)具有較好的數(shù)值穩(wěn)定性。BFGS法迭代公式與DFP法一樣，也是通過校正矩陣來求矩陣，只是求E(k)的公式不同。計算實踐發(fā)現(xiàn)，使用DFP法變尺度矩陣A(k)有時變?yōu)椴B(tài)的奇異矩陣；BFGS法算法比較穩(wěn)定，不易出現(xiàn)奇異矩陣，但A(k)偶而可能趨于無窮。使用BFGS法，否則用DFP法。Fletcher增加開關語句(開關算法)三、變尺度法BFGS變尺度法(Broyden、Fl23DFP變尺度法程序框圖DFP變尺度法24三、變尺度法例DFP變尺度法求解解(1)第一次迭代沿負梯度方向，解得=0.1三、變尺度法例DFP變尺度法求解解(1)第一次迭25三、變尺度法(2)第二次迭代用DFP變尺度法

三、變尺度法(2)第二次迭代用DFP變尺度法26三、變尺度法DFP變尺度法的迭代次數(shù)接近于牛頓法，但不需要計算函數(shù)的二階導數(shù)矩陣及其逆矩陣。三、變尺度法DFP變尺度法的迭代次數(shù)接近于牛頓法，但27四、共軛梯度法1964年Fletcher和Reeves提出→F-R法。

1．共軛方向的概念與性質(zhì)設A為一正定對稱矩陣，若有一組非零向量滿足稱這組向量關于矩陣A共軛。當A為單位矩陣時，有稱向量Si相互正交。共軛是正交推廣，正交是共軛特例。四、共軛梯度法1964年Fletcher和Reeve28四、共軛梯度法③從任意兩個點X1(0)和X2(0)出發(fā)，分別沿同一方向S(0)進行一維搜索，得到兩個一維極小點X1(1)和X2(1)，連接此兩點構成的向量與原方向關于該函數(shù)的二階導數(shù)矩陣相共軛。對于一般函數(shù)，共軛方向性質(zhì)：①若A為n階實對稱正定矩陣，為A共軛的n個非零向量，則這一向量組線性無關。②若S(i)是以A共軛的n個非零向量，則對于正定二次函數(shù)從任意初始點X(0)出發(fā)，依次沿這n個方向進行一維搜索，最多n次即可達到極小點。四、共軛梯度法③從任意兩個點X1(0)和X2(0)29四、共軛梯度法2．共軛方向形成共軛方向成方法——平行搜索法和基向量組合法。

(1)平行搜索法由共軛方向性質(zhì)③知，從不同的兩點出發(fā)，沿同一方向進行兩次一維搜索(進行兩次平行搜索)，所得兩個極小點的連線方向是與原方向共軛的另一方向。沿該方向作兩次平行搜索，又可得到第三個共軛方向。繼續(xù)下去，得到一個包含n個共軛方向的方向組。四、共軛梯度法2．共軛方向形成30四、共軛梯度法(2)基向量組合法

取n個基向量(單位坐標向量)ei和另一個獨立向量S(0)，令向量S(1)為S(0)和e(0)的線性組合，使S(0)和S(1)共軛，必須四、共軛梯度法(2)基向量組合法S(0)和S(1)共31四、共軛梯度法3．共軛梯度方向

從任意點X(k)出發(fā)，沿負梯度方向作一維搜索得設與S(k)共軛的下一個方向S(k+1)由S(k)和點X(k+1)的負梯度的線性組合構成，即根據(jù)共軛條件有四、共軛梯度法3．共軛梯度方向設與S(k)共32四、共軛梯度法只需利用相鄰兩點的梯度就可以構造一個共軛方向。以這種方式產(chǎn)生共軛方向并進行迭代運算的算法稱共軛梯度法。對于正定二元二次函數(shù)，沿兩個共軛梯度方向進行一維搜索，經(jīng)過兩次迭代即可達到極小點。四、共軛梯度法只需利用相鄰兩點的梯度就可以構造一個共33四、共軛梯度法對于一般正定二次函數(shù)，沿一組共軛梯度方向依次進行一維搜索，最多n次迭代就可達到極小點。對于一般函數(shù)，當n次迭代還未達到極小點時，應將第n個迭代點作為新的起始點，重新產(chǎn)生新的一組共軛方向，繼續(xù)迭代，直到滿足收斂精度為止。共軛梯度法具有超線性收斂速度。

四、共軛梯度法對于一般正定二次函數(shù)，沿一組共軛梯度方34共軛梯度法程序框圖共軛梯度法35四、共軛梯度法例用共軛梯度法求解解①第一次迭代沿負梯度方向進行搜索②第二次迭代=0.1四、共軛梯度法例用共軛梯度法求解解①第一次迭代沿36四、共軛梯度法

用共軛梯度法經(jīng)過兩次迭代便求得該二元二次優(yōu)化問題的極小點。迭代路線與DFP法完全相同。四、共軛梯度法用共軛梯度法經(jīng)過兩次迭代便求得該二元二次優(yōu)37五、鮑威爾法

無約束優(yōu)化的求導法不能使用，如何確定搜索方向？由前述知，兩次平行搜索可以產(chǎn)生一個共軛方向。鮑威爾(Powell)法就是利用平行搜索逐漸構造共軛方向和共軛方向組，并沿共軛方向進行一維搜索以逐漸逼近極小點的算法。由于共軛方向的產(chǎn)生不需要計算函數(shù)的導數(shù)→屬于求解無約束問題的模式法。鮑威爾法具有超線性收斂速度。五、鮑威爾法無約束優(yōu)化的求導法不能使用，如38五、鮑威爾法1．基本迭代格式以n個基向量e(i)構成初始方向組，由點X0(0)出發(fā)，沿n個坐標軸方向作n次一維搜索得點X0(n)(坐標輪換法)，以X0(n)和X0(0)的連線作為第一個新產(chǎn)生的方向沿方向S(0)作一維搜索得點X0(n+1)，以此點作為下一輪迭代的起始點，即以S(0)代換原方向組中的某基向量，構成新的方向組。從點X1(0)出發(fā)，分別沿n個方向作n次一維搜索，得點X1(n)。令則S(1)與S(0)相共軛。五、鮑威爾法1．基本迭代格式沿方向S(0)作一維搜39五、鮑威爾法2.基本鮑威爾法鮑威爾法的基本迭代格式包括共軛方向和方向替換兩個步驟。其中方向替換可以采用不同的方式。如果每次產(chǎn)生新的共軛方向S(k)后，去掉原方向組pk中的第一個，而將新的方向S(k)加到該方向組的末尾構成一新的方向pk+1。Powell于1964年提出，稱基本鮑威爾法。五、鮑威爾法2.基本鮑威爾法Powell于1964年40五、鮑威爾法

在基本算法中，方向組的替換采用固定格式，運算簡便。但是由此形成的方向組中，有可能出現(xiàn)幾個方向線性相關或近似線性相關的現(xiàn)象。

例從X(0)=[1/2，1，1/2]T出發(fā)，用基本鮑威爾法求函數(shù)極小點解沿坐標軸方向依次進行一維搜索，得最優(yōu)步長因子和迭代點五、鮑威爾法在基本算法中，方向組的替換采用固定格式，運41五、鮑威爾法i

SiαiXi1[1，0，0]T0[1/2，1，1/2]T2[0，1，0]T-2/3[1/2，1/3，1/2]T3[0，0，1]T-2/9[1/2，1/3，5/18]T首尾相連得搜索方向=[0，-2/3，-2/9]T下一輪迭代的搜索方向S1(2)、S2(2)、S3(2)=S(1)線性相關S3(2)=-2S1(2)/3-2S2(2)/9以后各次迭代均在x1=1/2平面內(nèi)進行降維搜索(極小點X*=[0，0，0]T)。五、鮑威爾法iSiαiXi1[1，0，0]T0[1/2，142五、鮑威爾法3.修正鮑威爾法為了防止方向組中新加入的方向與原來的方向線性相關，在用新的方向作替換之前，首先解決是否替換和替換哪個方向同時成立，表明方向Sk(n)與原方向組線性無關，可以用來進行替換。五、鮑威爾法3.修正鮑威爾法同時成立，表明方向S43五、鮑威爾法兩式滿足，替換替換公式

兩式不成立，表明Sk(n)與原方向組中的某些方向線性相關，不能用來進行替換，仍以原方向組中的n個方向進行新的迭代。五、鮑威爾法兩式滿足，替換替換公式兩式不成立，表明44五、鮑威爾法鮑威爾法方向替換

五、鮑威爾法鮑威爾法方向替換45POWELL法程序框圖POWELL法46五、鮑威爾法例用共軛梯度法求解=0.1解(1)第一輪迭代，取五、鮑威爾法例用共軛梯度法求解=0.1解(147五、鮑威爾法1)沿S1(0)進行一維搜索

解得=2

2)沿S1(1)進行一維搜索解得=0.5

五、鮑威爾法1)沿S1(0)進行一維搜索解得=248五、鮑威爾法3)收斂判斷

繼續(xù)計算

4)求最大下降量

5)構成新的方向

五、鮑威爾法3)收斂判斷繼續(xù)計算4)求最大下降量49五、鮑威爾法6)求反射點

7)方向S1(2)的有效性判斷判別式成立

五、鮑威爾法6)求反射點7)方向S1(2)的有效性判斷50五、鮑威爾法8)沿S1(2)進行一維搜索解得=1.49)進行方向替換，用S1(2)替換S1(0)

(Δ1=4大)，得新的方向組

五、鮑威爾法8)沿S1(2)進行一維搜索解得=151五、鮑威爾法

(2)第二輪迭代1)沿S2(0)進行一維搜索2)沿S2(1)進行一維搜索3)收斂判斷4)求最大下降量5)構成新的共軛方向6)求反射點7)方向S2(2)的有效性判斷8)沿S2(2)進行一維搜索最優(yōu)點

五、鮑威爾法(2)第二輪迭代最優(yōu)點52§2-4無約束優(yōu)化方法

無約束優(yōu)化問題的下降迭代算法具有統(tǒng)一的迭代格式，問題之一是選擇搜索方向。根據(jù)搜索方向的不同構成方式，分：

1)導數(shù)法(解析法)

利用目標函數(shù)的一階導數(shù)或二階導數(shù)信息構造搜索方向的方法。

梯度法、牛頓法、共軛梯度法和變尺度法…

條件：

①目標函數(shù)求導容易；②目標函數(shù)一階導數(shù)連續(xù)；③目標函數(shù)是設計變量的顯函數(shù)。

§2-4無約束優(yōu)化方法無約束優(yōu)53§2-4無約束優(yōu)化方法

2)模式法(直接法)

通過比較幾個已知點的函數(shù)值構造搜索方向的算法。

鮑威爾法。構成搜索方向的信息僅僅是幾個有限點上的函數(shù)值，難于得到較理想的搜索方向。一般迭代次數(shù)較多，收斂速度較慢。Rosenbrock函數(shù)x1x2§2-4無約束優(yōu)化方法2)模式法(54一、梯度法

迭代方向是由迭代點的負梯度構成——最速下降法。梯度法迭代公式一、梯度法迭代方向是由迭代點的負梯度構成——最速下55一、梯度法根據(jù)極值的必要條件和復合函數(shù)求導公式，有相鄰兩迭代點的梯度正交最優(yōu)步長因子k，由一維搜索確定一、梯度法根據(jù)極值的必要條件和復合函數(shù)求導公式，有相鄰兩迭代56一、梯度法

特點：

(1)算法簡單，只計算目標函數(shù)一階導數(shù)，占用內(nèi)存少；(2)初始點任選；(3)初始迭代速度快；(4)

搜索路線正交，收斂速度越來越慢。一、梯度法特點：57梯度法程序框圖梯度法58一、梯度法例

用梯度法求解解：①第一次迭代

=0.1一、梯度法例用梯度法求解解：①第一次迭代=0.59一、梯度法②

第二次迭代X(1)為初始點，進行迭代……一、梯度法②

第二次迭代60二、牛頓法

梯度法除在最初幾次迭代中函數(shù)值下降很快外，總的來說下降不快，且愈接近極值點下降愈慢。尋求使目標函數(shù)值下降更快的方法→牛頓法。

基本思路：——利用二次曲線逐點近似原目標函數(shù)，以二次曲線的極小點近似原目標函數(shù)的極小點并逐漸逼近該點。牛頓法分基本牛頓法和阻尼牛頓法。二、牛頓法梯度法除在最初幾次迭代中函數(shù)值下611.基本牛頓法函數(shù)f(X)在點X(k)處展開成泰勒二次近似式設X(k+1)是函數(shù)的極小點，有用基本牛頓法求解正定二次函數(shù)時，無論從哪個初始點出發(fā)，一次計算即可達到極小點。1.基本牛頓法函數(shù)f(X)在點X(k)處展開成泰勒二次近621．基本牛頓法

對于非線性正定函數(shù)，二階泰勒展開式只是原函數(shù)的近似式，得到X(k+1)只是原函數(shù)的近似極小點。以此點作為下一次迭代的起始點X(k)，能夠加快逼近的速度。對于非正定函數(shù)，為保證牛頓方向是函數(shù)值下降的方向，海賽矩陣必須正定。采用定步長，即使牛頓方向是函數(shù)值下降的方向，也不能保證函數(shù)值下降，即得到的點并不能始終保持函數(shù)的下降性→基本牛頓法有可能失效。1．基本牛頓法對于非線性正定函數(shù)，二階泰632．阻尼牛頓法在迭代中引入步長因子和一維搜索。

阻尼牛頓法在每次迭代中沿牛頓方向作一維搜索，保證迭代點的嚴格下降性，適用于任何函數(shù)，且保證得到的迭代點更加靠近極小點，具有更加理想的收斂效果。牛頓法均指阻尼牛頓法。2．阻尼牛頓法在迭代中引入步長因子和一維搜索。642．阻尼牛頓法阻尼牛頓法程序框圖特點：

(1)具有二階收斂性，收斂速度快；(2)在極值點附近有效；(3)計算復雜；(4)X(0)位置和函數(shù)性態(tài)影響計算結果。2．阻尼牛頓法阻尼牛頓法特點：65二、牛頓法例牛頓法求解解

(1)基本牛頓法

=0.1二、牛頓法例牛頓法求解解(1)基本牛頓法=066二、牛頓法(2)阻尼牛頓法基本牛頓法計算得二、牛頓法(2)阻尼牛頓法67二、牛頓法解得=1

二、牛頓法解得=168三、變尺度法

變尺度法是擬牛頓法?？朔ｎD法的缺點，繼承其收斂快的優(yōu)點，具有超線性收斂速度。1959年，Davidon提出變尺度法，F(xiàn)letcher和Powell改進——DFP法。

優(yōu)化算法一般迭代公式

三、變尺度法變尺度法是擬牛頓法。優(yōu)化算法一般迭代公69三、變尺度法梯度法，搜索方向為負梯度方向牛頓法，搜索方向為牛頓方向統(tǒng)一形式三、變尺度法梯度法，搜索方向為負梯度方向牛頓法，搜索方向為70三、變尺度法——梯度法

——牛頓法

在迭代開始時，按負梯度方向搜索；爾后每次迭代時不斷調(diào)整A(k)，修正搜索方向，使A(k)逐步逼近目標函數(shù)的海賽矩陣之逆矩陣；當?shù)c臨近極小點時，構成的方向就近似為牛頓方向，直指極小點。整個迭代過程收斂速度很快。矩陣A(k)代替海賽矩陣之逆矩陣，且迭代過程中不斷改變→變尺度矩陣。三、變尺度法——梯度法——牛頓法在迭代開始時，按71三、變尺度法關鍵：構造變尺度矩陣1.變尺度矩陣構造原則1)算法具有下降性

——為了使方向S(k)=-A(k)g(k)為目標函數(shù)值的下降方向，構造的變尺度矩陣A(k)應為正定對稱矩陣。

若目標函數(shù)f(X)的值沿S(k)下降，則S(k)與X(k)點的負梯度方向之間的夾角應為銳角，即只要A(k)正定，S(k)=-A(k)g(k)必為目標函數(shù)值的下降方向。三、變尺度法關鍵：構造變尺度矩陣1.變尺度矩陣構造原72三、變尺度法2）計算方便性——構造的變尺度矩陣A(k)應便于計算，在迭代過程中應逐漸地逼近海賽矩陣之逆矩陣。取單位矩陣I為初始矩陣A(0)E(k)——校正矩陣。2.變尺度矩陣構造Davidon提出，F(xiàn)letcher和Powell修正，校正矩陣E(k)

三、變尺度法2）計算方便性——構造的變尺度矩陣A(k73三、變尺度法DFP變尺度法在函數(shù)f(X)梯度易求的情況下，非常有效。對于多維問題(n>100)，收斂快，效果佳→無約束極值問題優(yōu)化的最好方法之一。計算程序較復雜，需要較大的存儲量，特別是在有舍入誤差時，存在數(shù)值穩(wěn)定性不夠理想的情況。

三、變尺度法DFP變尺度法在函數(shù)f(X)梯度易求的74三、變尺度法

BFGS變尺度法(Broyden、Fletcher、Goldfarb、Shanno)具有較好的數(shù)值穩(wěn)定性。BFGS法迭代公式與DFP法一樣，也是通過校正矩陣來求矩陣，只是求E(k)的公式不同。計算實踐發(fā)現(xiàn)，使用DFP法變尺度矩陣A(k)有時變?yōu)椴B(tài)的奇異矩陣；BFGS法算法比較穩(wěn)定，不易出現(xiàn)奇異矩陣，但A(k)偶而可能趨于無窮。使用BFGS法，否則用DFP法。Fletcher增加開關語句(開關算法)三、變尺度法BFGS變尺度法(Broyden、Fl75DFP變尺度法程序框圖DFP變尺度法76三、變尺度法例DFP變尺度法求解解(1)第一次迭代沿負梯度方向，解得=0.1三、變尺度法例DFP變尺度法求解解(1)第一次迭77三、變尺度法(2)第二次迭代用DFP變尺度法

三、變尺度法(2)第二次迭代用DFP變尺度法78三、變尺度法DFP變尺度法的迭代次數(shù)接近于牛頓法，但不需要計算函數(shù)的二階導數(shù)矩陣及其逆矩陣。三、變尺度法DFP變尺度法的迭代次數(shù)接近于牛頓法，但79四、共軛梯度法1964年Fletcher和Reeves提出→F-R法。

1．共軛方向的概念與性質(zhì)設A為一正定對稱矩陣，若有一組非零向量滿足稱這組向量關于矩陣A共軛。當A為單位矩陣時，有稱向量Si相互正交。共軛是正交推廣，正交是共軛特例。四、共軛梯度法1964年Fletcher和Reeve80四、共軛梯度法③從任意兩個點X1(0)和X2(0)出發(fā)，分別沿同一方向S(0)進行一維搜索，得到兩個一維極小點X1(1)和X2(1)，連接此兩點構成的向量與原方向關于該函數(shù)的二階導數(shù)矩陣相共軛。對于一般函數(shù)，共軛方向性質(zhì)：①若A為n階實對稱正定矩陣，為A共軛的n個非零向量，則這一向量組線性無關。②若S(i)是以A共軛的n個非零向量，則對于正定二次函數(shù)從任意初始點X(0)出發(fā)，依次沿這n個方向進行一維搜索，最多n次即可達到極小點。四、共軛梯度法③從任意兩個點X1(0)和X2(0)81四、共軛梯度法2．共軛方向形成共軛方向成方法——平行搜索法和基向量組合法。

(1)平行搜索法由共軛方向性質(zhì)③知，從不同的兩點出發(fā)，沿同一方向進行兩次一維搜索(進行兩次平行搜索)，所得兩個極小點的連線方向是與原方向共軛的另一方向。沿該方向作兩次平行搜索，又可得到第三個共軛方向。繼續(xù)下去，得到一個包含n個共軛方向的方向組。四、共軛梯度法2．共軛方向形成82四、共軛梯度法(2)基向量組合法

取n個基向量(單位坐標向量)ei和另一個獨立向量S(0)，令向量S(1)為S(0)和e(0)的線性組合，使S(0)和S(1)共軛，必須四、共軛梯度法(2)基向量組合法S(0)和S(1)共83四、共軛梯度法3．共軛梯度方向

從任意點X(k)出發(fā)，沿負梯度方向作一維搜索得設與S(k)共軛的下一個方向S(k+1)由S(k)和點X(k+1)的負梯度的線性組合構成，即根據(jù)共軛條件有四、共軛梯度法3．共軛梯度方向設與S(k)共84四、共軛梯度法只需利用相鄰兩點的梯度就可以構造一個共軛方向。以這種方式產(chǎn)生共軛方向并進行迭代運算的算法稱共軛梯度法。對于正定二元二次函數(shù)，沿兩個共軛梯度方向進行一維搜索，經(jīng)過兩次迭代即可達到極小點。四、共軛梯度法只需利用相鄰兩點的梯度就可以構造一個共85四、共軛梯度法對于一般正定二次函數(shù)，沿一組共軛梯度方向依次進行一維搜索，最多n次迭代就可達到極小點。對于一般函數(shù)，當n次迭代還未達到極小點時，應將第n個迭代點作為新的起始點，重新產(chǎn)生新的一組共軛方向，繼續(xù)迭代，直到滿足收斂精度為止。共軛梯度法具有超線性收斂速度。

四、共軛梯度法對于一般正定二次函數(shù)，沿一組共軛梯度方86共軛梯度法程序框圖共軛梯度法87四、共軛梯度法例用共軛梯度法求解解①第一次迭代沿負梯度方向進行搜索②第二次迭代=0.1四、共軛梯度法例用共軛梯度法求解解①第一次迭代沿88四、共軛梯度法

用共軛梯度法經(jīng)過兩次迭代便求得該二元二次優(yōu)化問題的極小點。迭代路線與DFP法完全相同。四、共軛梯度法用共軛梯度法經(jīng)過兩次迭代便求得該二元二次優(yōu)89五、鮑威爾法

無約束優(yōu)化的求導法不能使用，如何確定搜索方向？由前述知，兩次平行搜索可以產(chǎn)生一個共軛方向。鮑威爾(Powell)法就是利用平行搜索逐漸構造共軛方向和共軛方向組，并沿共軛方向進行一維搜索以逐漸逼近極小點的算法。由于共軛方向的產(chǎn)生不需要計算函數(shù)的導數(shù)→屬于求解無約束問題的模式法。鮑威爾法具有超線性收斂速度。五、鮑威爾法無約束優(yōu)化的求導法不能使用，如90五、鮑威爾法1．基本迭代格式以n個基向量e(i)構成初始方向組，由點X0(0)出發(fā)，沿n個坐標軸方向作n次一維搜索得點X0(n)(坐標輪換法)，以X0(n)和X0(0)的連線作為第一個新產(chǎn)生的方向沿方向S(0)作一維搜索得點X0(n+1)，以此點作為下一輪迭代的起始點，即以S(0)代換原方向組中的某基向量，構成新的方向組。從點X1(0)出發(fā)，分別沿n個方向作n次一維搜索，得點X1(n)。令則S(1)與S(0)相共軛。五、鮑威爾法1．基本迭代格式沿方向S(0)作一維搜91五、鮑威爾法2.基本鮑威爾法鮑威爾法的基本迭代格式包括共軛方向和方向替換兩個步驟。其中方向替換可以采用不同的方式。如果每次產(chǎn)生新的共軛方向S(k)后，去掉原方向組pk中的第一個，而將新的方向S(k)加到該方向組的末尾構成一新的方向pk+1。Powell于1964年提出，稱基本鮑威爾法。五、鮑威爾法2.基本鮑威爾法Powell于1964年92五、鮑威爾法

在基本算法中，方向組的替換采用固定格式，運算簡便。但