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

第五章

無約束優(yōu)化方法無約束優(yōu)化問題是：求n維設(shè)計變量使目標函數(shù)

，而對

沒有任何限制條件。可以利用極值定義，將上式變成求以下方程本章介紹的是數(shù)值方法。其中最常用的是搜索方法，即給定初始點和搜索方向，沿著該方向?qū)ふ易顑?yōu)點。搜索方向的構(gòu)成是關(guān)鍵。無約束極小算法的粗框圖根據(jù)構(gòu)成搜索方向所使用的信息性質(zhì)的不同，無約束優(yōu)化方法可以分成兩類。一類是利用目標函數(shù)的一階或二階導(dǎo)數(shù)的無約束優(yōu)化方法，另一類是指利用目標函數(shù)值的無約束優(yōu)化方法。第一節(jié) 最速下降法最速下降法是以負梯度方向作為搜索方向，所以又稱梯度法。根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得相鄰兩個迭代點上的函數(shù)梯度方向互相垂直求目標函數(shù)

的極小點。解取初始值則初始點處函數(shù)值及梯度分別為沿負梯度方向進行一維搜索，有為一維搜索最佳步長，應(yīng)滿足極值必要條件從而算出一維搜索最佳步長及第一次迭代設(shè)計點位置和函數(shù)值經(jīng)過10次迭代，得到最優(yōu)值若將上例的目標函數(shù)引入變換其等值線就由一族橢圓變成一族同心圓，仍從

即

開始尋優(yōu)此時有沿負梯度方向進行一維搜索，有為一維搜索最佳步長，可由極值條件算得得到第一次迭代的結(jié)果就是最優(yōu)解最速下降法的收斂速度與變量的尺度關(guān)系很大，下面是最速下降收斂速度的估計式式中的海賽矩陣最大特征值上界；其最小特征值下屆。一、特征值與特征向量的定義定義2.1設(shè)A為復(fù)數(shù)域上的n階矩陣，若存在復(fù)數(shù)和非零n維列向量X使得則稱數(shù)為A的一個特征值，X為A的屬于（或?qū)?yīng)于）特征值的特征向量。由（2-1）式得由此可見，特征值是使齊次方程組有非零解 的的值。方程組（2-3）有非零解的充要條件是，對于等值線為橢圓的二次型函數(shù)其海賽矩陣兩個特征值分別為

。因此可見等值線為橢圓的長短軸相差越大，收斂就越慢。，因此兩個特征值相等代入（4-4），有得即經(jīng)過一次迭代便可到達極值點。最速下降法是一個求解極值問題的古老算法，早在1847年就已由柯西（Cauchy）提出。此法直觀、簡單。由于它采用了函數(shù)的負梯度方向作為下一步的搜索方向，所以收斂速度較慢，越是接近極值點收斂越慢，這就是它的主要缺點。應(yīng)用最速下降法可以使頭幾次迭代的收斂速度很快，所以它可與其他方法配合使用。第二節(jié)

牛頓型方法一維情況下牛頓迭代公式多維情況下牛頓迭代公式根據(jù)極值的必要條件，得：對二次函數(shù)來說，上述的泰勒展開式不是近似的，而是精確的。海森矩陣是一個常數(shù)陣。無論從任何點出發(fā)，只需一步就可找到極小點。二次收斂的概念：如果某一種迭代方法能夠使二次型函數(shù)在有限次迭代內(nèi)達到極小點，則稱此迭代方法是二次收斂的。從牛頓法迭代公式的推演中可以看到，迭代點的位置是按照極值條件去訂的，其中并未含有沿下降方向搜索的概念。因此對于非二次函數(shù)，如果采用上述牛頓法迭代公式，有時會使函數(shù)值上升，為了解決這個問題，提出“阻尼牛頓法”為沿牛頓方向進行一維搜索的最佳步長，可稱為阻尼因子?？赏ㄟ^如下極小化過程求得其中：這樣，原來的牛頓法就相當于阻尼牛頓法的步長因子取成固定值1的情況。由于阻尼牛頓法每次迭代都在牛頓方向上進行一維搜索，這就避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法二次收斂的特性，而對初始點的選取并沒有苛刻的要求。阻尼牛頓法的計算步驟如下：1）給定初始點，收斂精度，置

。。，其中為沿進行一維搜計算和求索的最佳步長。則

，，返回到2繼續(xù)進行搜4）檢查收斂精度。若停機；否則，置索。牛頓法和阻尼牛頓法統(tǒng)稱牛頓型方法。這類方法的主要缺點是每次迭代都要計算函數(shù)的二階導(dǎo)數(shù)矩陣，并對該矩陣求逆，當維數(shù)高時工作量更大。針對上述的梯度法收斂速度慢，提出收斂速度更快的共軛梯度。針對牛頓法的缺點提出了變尺度法。作業(yè):用牛頓迭代法求解最優(yōu)解，用matlab實現(xiàn)。已知第三節(jié)變尺度法一、尺度矩陣的概念變量的尺度變換是放大或縮小各個坐標，通過尺度變換可以把函數(shù)的偏心程度降低到最低限度。尺度變換技巧能顯著地改善幾乎所有極小化方法的收斂性質(zhì)。如：求目標函數(shù)若將上例的目標函數(shù)的極小點。引入變換對于一般二次函數(shù)如果進行尺寸變換則在新的坐標系中，函數(shù)

的二次項變?yōu)槿艟仃嘒是正定的，則總存在矩陣Q，使得：（單位矩陣）將函數(shù)的偏心降為0用右乘等式兩邊，得再用Q左乘等式兩邊，得所以這說明二次函數(shù)矩陣G的逆陣，可以通過尺度變換矩陣Q來求得。牛頓方向便可寫成牛頓迭代公式變?yōu)槔樱鹤儞Q則在變換后的坐標系中，矩陣G變?yōu)橹恍柰ㄟ^一次迭代即可求得極小點比較牛頓法迭代公式和梯度法迭代公式可以看出，差別在于牛頓法中多了

部分。實際上是在x空間內(nèi)測量距離大小的一種度量，稱作尺度矩陣H如在未進行尺度變換前，向量x長度的概念是變換后向量x對于H尺度下的長度這樣的長度定義，在確定“長度”這個純量大小是，使得某些方向起的作用比較大，另一些方向起的作用比較小。它和梯度法的公式只差一個H，牛頓法就可以看成是經(jīng)過尺度變換后的剃度法。經(jīng)過尺度變換，使函數(shù)的偏心率減小到0，函數(shù)的等值面變成球面，使設(shè)計空間中任意點處的梯度都通過極小點。（對二次函數(shù)）。為使這種尺度有用，必須對一切非零向量的x均有矩陣，既然牛頓法迭代公式可用尺度變換表示出來，即變尺度矩陣的建立對于一般函數(shù)f(x)，當用牛頓法尋求極小點時，其牛頓迭代公式為為了避免在迭代公式中計算海賽矩陣的逆矩陣

，可以用在迭代中逐步建立的變尺度矩陣來替換

，即構(gòu)造一個矩陣序列

來逼近海賽逆矩陣序列

。1）為了保證迭代公式具有下降性質(zhì)，要求Hk中的每個矩陣都是對稱正定的其中是從出發(fā)，沿方向搜索而得到的最佳步長。為了使變尺度矩陣加某些條件：確實與

近似，并必須附求若要求搜索方向

為下降方向，即要也就是

，即

，即應(yīng)為對稱正定。2）要求

之間的迭代具有簡單的形式。顯然為最簡單的形式，其中為校正矩陣。上式稱作校正公式。3）要求

必須滿足擬牛頓條件。所謂擬牛頓條件可以推導(dǎo)：設(shè)迭代過程已經(jīng)進行了k+1步，

，

均已求出，現(xiàn)在推導(dǎo)

所需要的條件。當f(x)為具有正定矩陣G的二次函數(shù)時因為具有正定海賽矩陣

的一般函數(shù)，在極小點附近可用二次函數(shù)很好的近似，所以如果迫使?jié)M足類似于上式的關(guān)系那么

就可以很好地近似于

。上述關(guān)系稱擬牛頓條件根據(jù)上述擬牛頓條件，不通過海賽矩陣求逆就可以構(gòu)造一個矩陣來逼近海賽矩陣的逆陣，這類方法統(tǒng)稱作擬牛頓法。由于變尺度矩陣的建立應(yīng)用了擬牛頓條件，所以變尺度法也是屬于一種擬牛頓法。還可以證明，變尺度法對于具有正定矩陣G的二次函數(shù)，能產(chǎn)生對G共軛的搜索方向，因此變尺度法又可以看成

是一種共軛方向法。三、變尺度法的一般步驟對一般多元函數(shù)f(x)，用變尺度法求極小點，其一般步驟是：選定初始點和收斂精度。計算如

），置，選取初始對稱正定矩陣（例。3）計算搜索方向。4）沿

方向進行一維搜索

，計算，判斷是否滿足迭代終止準則，若滿足則停機。當?shù)鷑次后還沒找到極小點時，重置為單位矩陣I，并以當前設(shè)計點為初始點，返回到2進行下一輪迭代，否則轉(zhuǎn)到7。7）計算矩陣

，置

返回到3。對于校正矩陣，可由具體的公式來計算，不同的公式對應(yīng)不同的變尺度法，但不論哪種變尺度法，必須滿足擬牛頓條件滿足上式的有無窮多個，因此上述變尺度法（屬于擬牛頓法）構(gòu)成一族算法。第五章

約束優(yōu)化方法工程問題中絕大部分問題是約束問題。只要由約束條件決定的可行域是凸集，同時目標函數(shù)也是凸函數(shù)，否則將由于選擇的初始點不同，而搜索到不同的局部最有點上。約束優(yōu)化的模型，通常如下：根據(jù)求解方式的不同，可分為直接解法、間接解法。直接解法通常用于僅含不等式約束的問題，他的基本思路是：在m個不等式約束所確定的可行域內(nèi)，選擇一個初始點，然后決定可行的搜索方向，以適當?shù)牟介L沿該方向進行搜索，得到一個使目標函數(shù)值下降的可行的新點。所謂可行搜索方向是指當設(shè)計點沿該方向作微量移動時，目標函數(shù)值將下降，且不會越出可行域。圖6-1直接解法的搜索路線直接法的特點是：由于整個求解的工程在可行域內(nèi)進行，因此，迭代過程不論何時終止，都可以獲得一個比初始點好的設(shè)計點。若目標函數(shù)為凸函數(shù)，可行域為凸集，則可保證獲得全域最優(yōu)解。否則，因存在多個局部最優(yōu)解，當選擇的初始點不相同是，可能搜索到不同的局部最優(yōu)點。為此，常在可行域內(nèi)選擇幾個差別較大的初始點分別進行計算，以便從求得的多個局部最優(yōu)解中選擇更好的最優(yōu)解。要求可行域為有界的非空集，即在有界可行域內(nèi)存在滿足全部約束條件的點，且目標函數(shù)有定義。間接解法有不同的求解策略，其中一種解法的基本思路是將約束優(yōu)化問題中的約束函數(shù)進行特殊的加權(quán)處理后，和目標函數(shù)結(jié)合起來，構(gòu)成一個新的目標函數(shù)，即將原約束優(yōu)化問題轉(zhuǎn)化成為一個或一系列的無約束優(yōu)化問題?！D(zhuǎn)換后的新目標函數(shù)。對新函數(shù)進行無約束極小化計算，由于在新目標函數(shù)中包含了各種約束條件，在求極值的過程中還將改變加權(quán)因子的大小。因此可以不斷調(diào)整設(shè)計點，使其逐步逼近約束邊界。從而間接地求得原約束問題的最優(yōu)解。例5-1求約束優(yōu)化問題的最優(yōu)解。，轉(zhuǎn)換后的新目解該問題的約束最優(yōu)解為用間接解法求解時，可取標函數(shù)為可以用解析法求

即令，得到方程組解此方程組，求得的無約束最優(yōu)解為：間接法是在優(yōu)化過程中得到廣泛應(yīng)用的方法，主要原因有以下個方面：由于無約束方法的研究日趨成熟，已經(jīng)研究出不少有效的無約束最優(yōu)化方法，使得間接解法有了可靠的基礎(chǔ)。可以有效地處理具有等式約束的約束優(yōu)化問題。間接解法存在的主要問題是：選取加權(quán)因子比較困難，加權(quán)因子選取不當，不但影響收斂速度和計算精度，甚至?xí)?dǎo)致計算失敗。求解約束優(yōu)化問題的方法很多，我們將著重介紹

屬于直接解法的隨機方向法，復(fù)合形法、可行方向法、廣義簡約梯度法，屬于間接法的罰函數(shù)法和增廣乘子

法。第一節(jié)隨機方向法隨機方向法是一種原理簡單的直接解法?；舅悸肥窃诳尚杏騼?nèi)選擇一個初始點，利用隨機函數(shù)的概率特性，產(chǎn)生若干個隨機方向，并從中選擇一個能使目標函數(shù)值下降最快的隨機方向作為可行搜索方向，記作d，從初始點x0出發(fā)，沿d方向以一定的步長進行搜索，得到新點x，新點x應(yīng)滿足約束條件且函數(shù)值小于初始點的函數(shù)值。不斷重復(fù)以上過程，經(jīng)過若干次迭代后，最終得到約束最優(yōu)解。隨機方向法的優(yōu)點是對目標函數(shù)的性態(tài)無特殊要求，程序設(shè)計簡單，使用方便。由于可行搜索方向是從許多隨機方向種選擇的使目標函數(shù)下降最快的方向，加之步長還可以靈活變動，所以此算法的收斂速度比較快。若能取得一個較好的初始點，迭代次數(shù)可以大大減少。它是求解小型的機器優(yōu)化設(shè)計問題的一種十分有效的算法。隨機數(shù)的產(chǎn)生：在隨機方向法中，為產(chǎn)生可行的初始點及隨機方向，需要用到大量的（0，1）、（-1，1）區(qū)域的均勻分布的隨機數(shù)。初始點的選擇隨機方向法的初始點必須是可行點，即滿足所

有不等式約束條件，當約束條件比較復(fù)雜，用人工不易選擇時，可用隨機選擇的方式產(chǎn)生。步驟如下：可行搜索方向的產(chǎn)生在隨機方向法中，產(chǎn)生可行按索方向的方法是從

k(k＞n)個隨機方向中選擇較好的方向，其計算步驟為：i1)在(—1，1)區(qū)間內(nèi)產(chǎn)生偽隨機數(shù)r

j

(i＝1，2，…n；J=1，2，…k按下式計算隨機單位向量2）取一個試驗步長a0

按照下式計算k個隨機點顯然，k個隨機點分布在以初始點xo為中心，以試驗步長a0為半徑的超球面上。檢驗k個隨機點xj(j＝1，2，…，n)是否為可行點，除去非可行點，計算余下的可行隨機點的目標函數(shù)值比

較其大小，選出目標函數(shù)值最小的點xL。比較xL和xo兩點的目標函數(shù)值，若則取xL和xo的連線方向作為可行搜索方向；否則將步長a0縮小返回2）計算。如果a0縮到非常小仍然找不到合適的xL說明該點是局部極小點，可以更換初始點，重新開始計算。綜上所述，產(chǎn)生可行搜索方向的條件可概括為，當xL點滿足則可行搜索方向為搜索步長的確定可行搜索方向d確定后，初始點移至xL點，即xL

xo，從xo點出發(fā)沿d方向進行搜索，所用的步長。一般按加速步長法來確定。所謂加速步長法是指依次迭代的步長按一定的比例遞增的方法。各次迭代的步長按下式計算：a=ma式中m——步長加速系數(shù)，可取m=1．33a——步長，初始步長取a=a0隨機方向法的計算步驟：選擇一個可行的初始點xo；產(chǎn)生k個n維隨機單位向量;取試驗步長a，計算出k個隨機點xj

(j＝l，2，…，k)；在k個隨機點中，找出滿足式條件的隨機點xL

，產(chǎn)生可行搜索方向從初始點xo出發(fā)，沿可行搜索方向d以步長。進行達代計算，直至擔索到一個滿足全部約束條件，且目標函數(shù)值不再下降的新點xo收斂條件第二節(jié)復(fù)合形法復(fù)合形法是求解約束優(yōu)化問題的一種重要的直接解法。它的基本思路是在可行域內(nèi)構(gòu)造一個具有

A個頂點的初始復(fù)合形。對該復(fù)合形各頂點的目標函數(shù)值進行比較，找到目標函數(shù)值最大的頂點(稱最壞點)，然后按一定的法則求出目標函數(shù)值有所下降的可行的新點，并用此點代替最壞點，構(gòu)成新的復(fù)合形，復(fù)合形的形狀每改變一次，就向最優(yōu)點移動一步，直至逼近最優(yōu)點。由于復(fù)合形的形狀不必保持規(guī)則圖形，對目標函數(shù)及約束函數(shù)的性狀又無特殊要求，因此該法的適應(yīng)性較強，在機械優(yōu)化設(shè)計中得到廣泛應(yīng)用。初始復(fù)臺形的形成復(fù)合形法是在可行域內(nèi)直接搜索最優(yōu)點，因此，要求初始復(fù)合形在可行域內(nèi)生成，即復(fù)合形的k個定點必須是可行點。生成初始復(fù)合形法的算法原理由設(shè)計者決定k個可行點，構(gòu)成初始復(fù)合形。當設(shè)計變量較多或約束函數(shù)復(fù)雜時，由設(shè)計者決定k個可行點常常很困難。只有在設(shè)計變量少，約束函數(shù)簡單的情況下，這種方法才被采用。由設(shè)計者選定一個可行點，其余的(k—1)個可行點