無約束優(yōu)化方法

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

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

1)導(dǎo)數(shù)法(解析法)

利用目標(biāo)函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)信息構(gòu)造搜索方向的方法。

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

條件：

①目標(biāo)函數(shù)求導(dǎo)容易；②目標(biāo)函數(shù)一階導(dǎo)數(shù)連續(xù)；③目標(biāo)函數(shù)是設(shè)計(jì)變量的顯函數(shù)。

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

2)模式法(直接法)

通過比較幾個(gè)已知點(diǎn)的函數(shù)值構(gòu)造搜索方向的算法。

如坐標(biāo)輪換法、共軛方向法、鮑威爾法等。構(gòu)成搜索方向的信息僅僅是幾個(gè)有限點(diǎn)上的函數(shù)值，難于得到較理想的搜索方向。一般迭代次數(shù)較多，收斂速度較慢。Rosenbrock函數(shù)x1x2一、梯度法

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

特點(diǎn)：

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

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

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

=0.1一、梯度法②

第二次迭代X(1)為初始點(diǎn)，進(jìn)行迭代……二、牛頓法

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

基本思路：——利用二次曲線逐點(diǎn)近似原目標(biāo)函數(shù)，以二次曲線的極小點(diǎn)近似原目標(biāo)函數(shù)的極小點(diǎn)并逐漸逼近該點(diǎn)。牛頓法分基本牛頓法和阻尼牛頓法。1.基本牛頓法函數(shù)f(X)在點(diǎn)X(k)處展開成泰勒二次近似式設(shè)X(k+1)是函數(shù)的極小點(diǎn)，有用基本牛頓法求解正定二次函數(shù)時(shí)，無論從哪個(gè)初始點(diǎn)出發(fā)，一次計(jì)算即可達(dá)到極小點(diǎn)。1．基本牛頓法

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

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

(1)具有二階收斂性，收斂速度快；(2)在極值點(diǎn)附近有效；(3)計(jì)算復(fù)雜；(4)X(0)位置和函數(shù)性態(tài)影響計(jì)算結(jié)果。二、牛頓法例牛頓法求解解

(1)基本牛頓法

=0.1二、牛頓法(2)阻尼牛頓法基本牛頓法計(jì)算得二、牛頓法解得=1

三、變尺度法

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

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

三、變尺度法梯度法，搜索方向?yàn)樨?fù)梯度方向牛頓法，搜索方向?yàn)榕ｎD方向統(tǒng)一形式三、變尺度法——梯度法

——牛頓法

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

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

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

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

三、變尺度法

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

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

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

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

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

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

共軛梯度法程序框圖四、共軛梯度法例用共軛梯度法求解解①第一次迭代沿負(fù)梯度方向進(jìn)行搜索②第二次迭代=0.1四、共軛梯度法

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

五、坐標(biāo)輪換法

無約束優(yōu)化的求導(dǎo)法不能使用，如何確定搜索方向？1、坐標(biāo)輪換法的基本原理坐標(biāo)輪換法又稱變量輪換法，其基本原理是將一個(gè)多維無約束優(yōu)化問題轉(zhuǎn)化為一系列一維優(yōu)化問題求解，即依次沿著坐標(biāo)軸的方向進(jìn)行一維搜索，求得極小點(diǎn)。以二維為例說明。再對n維作進(jìn)一步解釋。2、特點(diǎn)簡單易行，但效率低下，收斂速度很慢。六、鮑威爾法

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

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

例從X(0)=[1/2，1，1/2]T出發(fā)，用基本鮑威爾法求函數(shù)極小點(diǎn)解沿坐標(biāo)軸方向依次進(jìn)行一維搜索，得最優(yōu)步長因子和迭代點(diǎn)六、鮑威爾法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)線性相關(guān)S3(2)=-2S1(2)/3-2S2(2)/9以后各次迭代均在x1=1/2平面內(nèi)進(jìn)行降維搜索(極小點(diǎn)X*=[0，0，0]T)。六、鮑威爾法3.修正鮑威爾法為了防止方向組中新加入的方向與原來的方向線性相關(guān)，在用新的方向作替換之前，首先解決是否替換和替換哪個(gè)方向同時(shí)成立，表明方向Sk(n)與原方向組線性無關(guān)，可以用來進(jìn)行替換。六、鮑威爾法兩式滿足，替換替換公式