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

無約束最優(yōu)化方法無約束最優(yōu)化方法求解無約束最優(yōu)化問題

minf(x)的數(shù)值迭代解法。構(gòu)成約束最優(yōu)化方法的基礎(chǔ)解法。求解無約束最優(yōu)化問題的下降迭代解法具有統(tǒng)一的迭代格式，其基本問題是選擇搜索方向和在這些搜索方向上進(jìn)行一維搜索。由于構(gòu)成搜索方向的方式可以不同，從而形成了各種不同的無約束最優(yōu)化方法。多局部極小唯一極小(全局極小)根據(jù)搜索方向的不同構(gòu)成方式：導(dǎo)數(shù)法（解析法）：利用目標(biāo)函數(shù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)信息構(gòu)造搜索方向的方法。（梯度法、牛頓法、變尺度法、共軛梯度法）收斂性和收斂速度較好，較為常用模式法（直接法）：通過幾個已知點上函數(shù)值的比較構(gòu)造搜索方向的一類算法。（鮑威爾法）迭代次數(shù)多，收斂速度慢，搜索方向不理想梯度法（最速下降法）關(guān)于梯度的復(fù)習(xí)：梯度是一個向量。n元函數(shù)f(x1,x2,…xn)在某點x處的梯度為：梯度的方向與函數(shù)f的等值線的一個法線方向相同，從較低的等值線指向較高的等值線。梯度的方向就是函數(shù)f的值增加最快的方向，其相反方向就是函數(shù)值降低最快的方向。最速下降法又稱為梯度法，由Cauchy于1847年給出。最速下降法解決的是具有連續(xù)可微的目標(biāo)函數(shù)的UMP問題。最速下降法的基本思想：從當(dāng)前點xk出發(fā)尋找使得目標(biāo)函數(shù)下降最快的方向，即負(fù)梯度方向。式中，稱為最優(yōu)步長因子，由以下一維搜索確定：梯度法的迭代算式根據(jù)極值的必要條件和復(fù)合函數(shù)的求導(dǎo)公式，可得到上式表明，相鄰兩迭代點的梯度是彼此正交的。即，在梯度法的迭代過程中，相鄰的搜索方向相互垂直。這意味著，用梯度法迭代時，向極小點逼近的路徑是一條曲折的階梯形路線，而且越接近極小點，階梯越小，前進(jìn)速度越慢。梯度法只具有線性收斂速度。在梯度法的迭代過程中，離極小點越遠(yuǎn)時，一次迭代得到的函數(shù)下降量較大。或者說，梯度法在遠(yuǎn)離極小點時向極小點的逼近速度較快，而越接近極小點逼近速度越慢?；谶@一特點，許多算法在開始的第一步迭代都采用負(fù)梯度方向作為搜索方向。對于等值線為同心圓的目標(biāo)函數(shù)，無論從任何初始點出發(fā)，一次搜索即可以達(dá)到極小點。通過適當(dāng)坐標(biāo)變換，也可提高收斂速度梯度法算法步驟最速下降法計算步驟：選區(qū)初始點x0和精度計算是否停止，輸出x0求p0=計算t0,使計算x1=x0+t0p0例解：牛頓法牛頓法的搜索方向是根據(jù)目標(biāo)函數(shù)的負(fù)梯度和二階導(dǎo)數(shù)矩陣構(gòu)造的，稱為牛頓方向。Newton法基本思想：用探索點xk處的二階Taylor展開式近似代替目標(biāo)函數(shù)，以展開式的最小點為新的探索點。解題步驟給定初始點t1和精度是是停止，輸出t1是否停止，解題失敗否停止，輸出t2否牛頓法特點如果f是對稱正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過一次迭代就可達(dá)到最優(yōu)點,如不是二次函數(shù)，則牛頓法不能一步達(dá)到極值點，但由于這種函數(shù)在極值點附近和二次函數(shù)很近似,因此牛頓法的收斂速度還是很快的。牛頓法的收斂速度雖然較快，但要求Hessian矩陣要可逆，要計算二階導(dǎo)數(shù)和逆矩陣，就加大了計算機計算量和存儲量。在數(shù)學(xué)中，海森矩陣（Hessianmatrix

或Hessian）是一個自變量為向量的實值函數(shù)的二階偏導(dǎo)數(shù)組成的方塊矩陣，此函數(shù)如下：

如果f

所有的二階導(dǎo)數(shù)都存在，那么f

的海森矩陣即：H(f)ij(x)=DiDjf(x)阻尼牛頓法基本牛頓法對于一般非線性函數(shù)求解可能失效的缺陷可以通過在迭代中引入步長因子和一維搜索加以解決，改進(jìn)后的算法稱為阻尼牛頓法，引入的步長因子αk也稱為阻尼因子。由于引入阻尼因子和一維搜索，雖然增加了計算量，但可以保證迭代點的嚴(yán)格下降性，可以適用于任何非線性函數(shù)，具有更理想的收斂效果。阻尼牛頓法具有二階收斂性，在所有無約束最優(yōu)化方法中是收斂性最好的算法。牛頓法在構(gòu)造搜索方向時充分利用了函數(shù)在一點的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)信息，因此所產(chǎn)生的搜索方向能夠直接指向函數(shù)的極小點。對于正定二次函數(shù)，從任意初始點出發(fā)，一次迭代就可達(dá)到極小點。牛頓迭代法的優(yōu)缺點優(yōu)點：牛頓迭代法具有平方收斂的速度，所以在迭代過程中只要迭代幾次就會得到很精確的解。這是牛頓迭代法比簡單迭代法優(yōu)越的地方。缺點：選定的初值要接近方程的解，否則有可能的不到收斂的結(jié)果。再者，牛頓迭代法計算量比較大。因每次迭代除計算函數(shù)值外還要計算微商值。變尺度法（擬牛頓法）變尺度法是通過坐標(biāo)變換構(gòu)造的一類最優(yōu)化算法。這類算法的搜索方向在計算中以遞推形式逐步產(chǎn)生并最終逼近牛頓方向，而不需計算函數(shù)的二階導(dǎo)數(shù)及其及逆矩陣。變尺度法具有超線性收斂速度。坐標(biāo)變換當(dāng)函數(shù)在一點的二階導(dǎo)數(shù)矩陣為正定時，其函數(shù)在該點的泰勒二次展開式是正定二次函數(shù)，其等值線為同心橢圓族。引入變換矩陣U和如下變換：函數(shù)的二階導(dǎo)數(shù)矩陣的逆矩陣可以通過坐標(biāo)變換，由某個U矩陣得到。共軛梯度法共軛梯度法是最重要的共軛方向法之一，其特點是利用上一次的搜索方向和本次出發(fā)點的負(fù)梯度的線性組合來生成共軛方向，計算量和存貯量都較少。

共軛方向設(shè)H為一正定對稱矩陣，若有一組非零向量S1，S2，…，Sn滿足則稱這組向量關(guān)于矩陣H共軛，或稱它們是矩陣H的一組共軛向量（方向）共軛是正交的推廣，正交是共軛的特例共軛方向的性質(zhì)若Si（i=1，2，…，n）是以H共軛的n個向量，則對于正定二次函數(shù)，從任意初始點X0出發(fā)，依次沿這n個方向進(jìn)行一維搜索，最多n次即可到達(dá)該二次函數(shù)的極小點。從任意兩個點X01和X02出發(fā)，分別沿同一方向S0進(jìn)行兩次一維搜索，得到兩個一維極小點，連接此兩點構(gòu)成的向量與原方向S0關(guān)于該函數(shù)的二階導(dǎo)數(shù)矩陣共軛共軛方向的產(chǎn)生平行搜索向量組合平行搜索法從不同的兩點出發(fā)，沿同一方向進(jìn)行兩次一維搜索，或者說進(jìn)行兩次平行搜索，所得兩個極小點的連線方向便是與原方向共軛的另一方向。沿該方向作兩次平行搜索，又可得到第三個共軛方向。如此繼續(xù)下去，便可求得一個包含n個共軛方向的方向組。向量組合法基向量組合——取n個基向量ei（i=0,1,…,n-1）和另一個任意向量s0，令向量s1由e0和s0的線性組合形成，即式中，β0為待定常數(shù)。同理，令S2為e1和S0,S1的線性組合，可求得與S0和S1共軛的另一個方向S2。以此類推：梯度組合——從任意點Xk出發(fā)，沿負(fù)梯度方向作一維搜索。共軛梯度算法迭代算式：只需利用相鄰兩點的梯度就可以構(gòu)造一個新的共軛方向。以這種方式產(chǎn)生共軛方向進(jìn)行迭代運算的算法為共軛梯度法。共軛梯度法的迭代步驟給定初始點X0和收斂精度ε>0。取X0的負(fù)梯度作為搜索方向沿方向Sk作一維搜索得Xk+1收斂判斷：若k=n，則令X0=Xk+1轉(zhuǎn)②，否則轉(zhuǎn)⑥構(gòu)造新的共軛方向，轉(zhuǎn)③共軛梯度法的特點對于正定二元二次函數(shù)，沿一個梯度方向和一個共軛梯度方向進(jìn)行一維搜索，經(jīng)過兩次迭代即可達(dá)到極小點。對于一般正定二次函數(shù)，沿一組共軛梯度方向依次進(jìn)行一維搜索，最多n次迭代就可達(dá)到極小點。對于一般函數(shù)，當(dāng)n次迭代還未達(dá)到極小點時，應(yīng)將第n個迭代點作為新的起始點，重新產(chǎn)生一族新的共軛方向，繼續(xù)迭代，直至滿足收斂精度要求。共軛梯度法具有超線性收斂速度。例題試用共軛梯度法求下述二次函數(shù)的極小點求解過程將f(X)變換為如下形式：鮑威爾法鮑威爾法利用平行搜索逐漸構(gòu)造共軛方向，并沿共軛方向進(jìn)行一維搜索以逐漸逼近極小點的算法。由于共軛方法的產(chǎn)生不需要計算函數(shù)的導(dǎo)數(shù)，因此該法屬于求解無約束問題的模式法。鮑威爾法是模式法中最好的一種算法，具有超線性收斂速度?；镜袷揭詎個基向量e0，e1，…，en-1構(gòu)成初始方向組P0，由點X00出發(fā)，沿P0中的n個方向作n次一維搜索得到點Xn0，再以X00和Xn0的連線作為第一個新產(chǎn)生的方向S0。沿方向S0作一維搜索得點Xn+10，并以此點作為下一輪的迭代的起始點，X01=Xn+10。并以S0代換原方向組中的某個基向量，形成新的方向組。目標(biāo)函數(shù)是正定二元二次函數(shù)，Xn+11就是所求無約束問題的最優(yōu)點。目標(biāo)函數(shù)是n元二次函數(shù)，在第n輪中形成的方向Sn-1上進(jìn)行一維搜索的點是所求最優(yōu)點。對于一般函數(shù)，若n輪搜