優(yōu)化設(shè)計第7次課

第四章

無約束優(yōu)化方法第七節(jié)鮑威爾法一、共軛方向的生成

具有正定矩陣的二次函數(shù)另一方面，對于上述二次函數(shù)，其、兩點處的梯度可表示為兩式相減，得因而有若取方向

則得

說明和對共軛。根據(jù)共軛方向的性質(zhì)，沿方向分別對函數(shù)做兩次一維搜索，得到兩個極小點、，則這兩點的連線所形成的方向就是與一起對共軛的方向。通過上面的分析可知：對于二維問題，沿著此共軛方向做一次一維搜索即可找到目標(biāo)函數(shù)的極值點。二、鮑威爾法的基本算法(1)任選一初始點，令，選擇兩個線性無關(guān)的向量，如坐標(biāo)軸單位向量和作為初始搜索方向。(2)從出發(fā),順次沿、進(jìn)行一維搜索得點、，兩點連線得一新方向，即(3)從出發(fā),順次沿、進(jìn)行一維搜索得點、，兩點連線得一新方向，即用代替形成兩個線性無關(guān)的向量和，作為下一輪迭代的搜索方向。再從出發(fā)，沿做一維搜索得點

(即點)，作為下一輪迭代的初始點。、兩點是從不同點、出發(fā)，分別沿方向進(jìn)行一維搜索而得到的極小點，因此根據(jù)前面所敘述的理論，、兩點連線的方向同一起對共軛。再從出發(fā)，沿做一維搜索得，因為相當(dāng)于從出發(fā)分別沿的兩個共軛方向、進(jìn)行兩次一維搜索而得到的點，所以點即是二維問題的極小點。同理，將上述二維優(yōu)化問題的基本算法擴(kuò)展到n維情況，則鮑威爾基本算法的原理為：從初始點出發(fā)，順次沿n個線性無關(guān)的搜索方向所構(gòu)成的搜索方向組進(jìn)行一維搜索得到一個終點，由終點和初始點的連線形成一個新的搜索方向，用這個新的搜索方向替換原來n個方向中的第一個方向，而將新方向排在原方向組的最后，這樣就形成了一個新的搜索方向組。此外規(guī)定，從這一輪的搜索終點出發(fā)沿新的搜索方向進(jìn)行一維搜索而得到的極小點，作為下一輪迭代的初始點，這樣就形成算法的循環(huán)。因為這種方法在迭代中逐次生成共軛方向，而共軛方向又是較好的搜索方向，所以鮑威爾法又稱作方向加速法。三、鮑威爾基本算法的退化現(xiàn)象通過前面鮑威爾基本算法的介紹可知，在共軛方向的形成過程中，每一輪迭代都用連接始點和終點所產(chǎn)生的搜索方向去替換原搜索方向組中的第一個方向，而不管它的“好壞”，這樣就有可能造成在迭代中新形成的n個搜索方向會變成線性相關(guān)而不能形成共軛方向，即可能形不成n維空間，進(jìn)而求不到極小點，我們稱鮑威爾基本算法的這種缺陷為退化現(xiàn)象。下面以三維問題為例來說明鮑威爾基本算法的退化現(xiàn)象。對一個三維問題，首先由初始點出發(fā)，沿著3個坐標(biāo)軸方向、、進(jìn)行第一輪搜索，得到點，連接始點和終點，形成搜索方向，在這一輪中、、和是不共面的一組向量，如下圖所示。新生方向可表示為如果在某種條件下，即在方向上搜索沒有進(jìn)展，迭代點的位移為零，此時，則必與，共面，共面的3個向量必線性相關(guān)。由右圖可看出，在隨后的各輪的方向組中各向量必在由，所決定的平面內(nèi)，使以后的搜索局限在二維平面內(nèi)進(jìn)行，顯然，這種降維后的搜索將無法獲得三維目標(biāo)函數(shù)的最優(yōu)點四、鮑威爾基本算法的退化現(xiàn)象因為鮑威爾基本算法在迭代過程中存在上述退化現(xiàn)象，所以需要對鮑威爾基本算法進(jìn)行改進(jìn)。針對上述缺陷，鮑威爾基本算法改進(jìn)的原則是：首先要判斷原方向組是否需要替換；其次，如果需要替換，還要進(jìn)一步判斷原向量組中那個方向最壞，然后再用新產(chǎn)生的方向替換這個最壞的方向，以保證逐次生成共扼方向。鮑威爾改進(jìn)算法的具體步驟如下。(1)給定初始點和計算精度，選取初始方向組，它由n個線性無關(guān)的向量（比如n個坐標(biāo)軸單位向量）所組成，置，。

(2)如下圖所示,從出發(fā)，順次沿做一維搜索得，即這一步相當(dāng)于最佳步長的坐標(biāo)輪換法。(3)接著以為起點，沿方向移動一個的距離，得到、、分別稱為第輪迭代的始點、終點和反射點。始點、終點和反射點所對應(yīng)的函數(shù)值分別表示為(4)計算第輪中相鄰兩點目標(biāo)函數(shù)值的下降量，并求出下降量最大者，即相應(yīng)的方向為(5)判斷是否滿足判別條件和若滿足上述判別條件，說明共軛性好，則下輪迭代應(yīng)對原方向組進(jìn)行替換，將補(bǔ)充到原方向組的最后位置，而除掉，即新方向組為作為下輪迭代的搜索方向組。下輪迭代的始點取為沿方向進(jìn)行一維搜索的極小點。若不滿足判別條件，則下輪迭代仍用原方向組，即同時比較和的函數(shù)值和，取函數(shù)值相對小者作為下輪迭代的始點。(6)判斷是否滿足收斂準(zhǔn)則。若滿足，則取為極小點，為最優(yōu)值；否則應(yīng)置，返回步驟(2)，繼續(xù)進(jìn)行下一輪迭代。

例：試用Powell法求目標(biāo)函數(shù)

的最優(yōu)解。

試用Powell法求目標(biāo)函數(shù)的最優(yōu)解。已知初始點，迭代精度。

課堂練習(xí)第八節(jié)單純形法一、單純形法的基本思想

采用單純形法求解無約束優(yōu)化問題是指在不計算導(dǎo)數(shù)的情況下，先計算出若干點處的函數(shù)值，然后依據(jù)函數(shù)值的大小關(guān)系來判斷函數(shù)變化的趨勢，確定函數(shù)的下降方向，進(jìn)而求得目標(biāo)函數(shù)值的極值，這里所說的若干點，一般是取在單純形的頂點上。所謂單純形是指在n維空間中由n+1個線性獨立的點構(gòu)成的簡單圖形或凸多面體，例如，在一維空間中由兩點構(gòu)成的線段(見下圖(a))；在二維空間中由不在同一直線上的三個點構(gòu)成的簡單圖形，即三角形(見下圖(b))；在三維空間中由不在同一平面上的四個點構(gòu)成的簡單圖形，即四面體(見下圖(c))；在n維空間中由n+1個頂點構(gòu)成的凸多面體等。單形替換法的基本思想是指在無約束優(yōu)化求解過程中、根據(jù)問題的維數(shù)n，選取由n+1個頂點構(gòu)成的單純形．求出這些頂點處的目標(biāo)函數(shù)值并加以比較，確定它們當(dāng)中有最大值的點及函數(shù)值的下降方向，再設(shè)法找到一個新的比較好的點替換那個有最大值的點，從而構(gòu)成新的單純形。隨著這種取代過程的不斷進(jìn)行，新的單純形將向著極小點收縮，這樣經(jīng)過若干次迭代，即可得到滿足收斂準(zhǔn)則的近似解。一般來講，為加快單純形法的尋優(yōu)過程，可采用四種基本的尋優(yōu)措施，即反射、擴(kuò)張、壓縮和縮短邊長。下面以二維無約束優(yōu)化問題為例來說明單純形法的尋優(yōu)過程。若如下圖所示，設(shè)二維目標(biāo)函數(shù)為，在平面上為線性獨立(不在同一直線上)三個點，以它們?yōu)轫旤c構(gòu)造單純形——三角形，計算這三個頂點處的函數(shù)值并做比較。則說明點最差，點最好。如圖所示。查明單純形各項點目標(biāo)函數(shù)值的情況之后，采取以下基本策略搜索極小點。

(1)反射。單純形各項點目標(biāo)函數(shù)值的大小反映了目標(biāo)函數(shù)在單純形這個局部區(qū)域的變化性態(tài)。一般來說，目標(biāo)函數(shù)最小點在最差點的對稱位置的可能性最大，因此首先求出最差點的反射點，以探測目標(biāo)函數(shù)變化的趨向。首先，求出除以外的所有頂點(在本題中僅為，兩點)的形心點(如圖)，并以為對稱中心，求取的關(guān)于的對稱點。應(yīng)在和連線的延長線上，并滿足

(2)擴(kuò)張。若反射點的函數(shù)值小于最好點的函數(shù)值，即當(dāng)時，則表明所取的搜索方向正確。這時，可以進(jìn)一步擴(kuò)大效果，繼續(xù)沿向前進(jìn)行擴(kuò)張在更遠(yuǎn)處取一點，并使如果，說明擴(kuò)張有利，就用代替最差點，構(gòu)成新的單純形；如果，說明擴(kuò)張不利．則舍棄，仍以代替構(gòu)成新的單純形

(3)壓縮。若反射點的函數(shù)值小于最差點的函數(shù)值但大于次差點的函數(shù)值，即當(dāng)時，則表示點走得太遠(yuǎn)，應(yīng)回縮一些，即進(jìn)行壓縮，并且得到壓縮點，即這時，若式中，為壓縮系數(shù)，常取即用壓縮點代替最差點，形成新的單純形；否則不用壓縮點，而用反射點代替最差點構(gòu)成新的單純形若反射點的函數(shù)值大于最差點的函數(shù)值，即當(dāng)時，應(yīng)當(dāng)壓縮得更多一些，即將新點壓縮至與之間，這時所得的壓縮點應(yīng)為這時若，用壓縮點代替最差點，形成新的單純形；否則不用。

(4)縮短邊長。如果在方向上所有點的函數(shù)值都大于，則不能沿此方向搜索。這時可使單純形向最好點進(jìn)行收縮，即使最好點不動，其余各頂點、皆向移近為原距離的一半，如下圖所示，由單純形，收縮成單純形，在此基礎(chǔ)上．繼續(xù)采用上面的搜索策略進(jìn)行尋優(yōu)。以上說明，可以通過反射、擴(kuò)張、壓縮和縮短邊長等方式得到一個新單純形，其中至少有一個頂點的函數(shù)值比原單純形中最差點的函數(shù)值要小。二、單純形法的計算步驟

(1)構(gòu)造初始單純形。對于n維變量的目標(biāo)函數(shù)，其單純形應(yīng)有n+1個頂點，即。構(gòu)造初始單純形時，先在n維空間中取一初始點，從出發(fā)沿各坐標(biāo)軸方向，以步長找到其余n個頂點，即式中——第個坐標(biāo)軸的單位向量；——步長，一般取值范圍為，接近最優(yōu)點時要減小，構(gòu)成初始單純形的步長可取。這樣選取頂點可以保證形成的單純形的各個棱邊線性無關(guān)，即下述幾個向量是線性無關(guān)的，否則，就有可能會使搜索范圍局限在較低的空間內(nèi)而可能找不到最優(yōu)點。當(dāng)然，沿各坐標(biāo)軸方向可以采取不等的步長。

(2)計算單純形各頂點函數(shù)值

(3)比較函數(shù)值的大小，確定最好點和最差點和次差點，即有

(4)檢驗是否滿足收斂準(zhǔn)則若滿足，則即為極小點，，停止迭代；否則，進(jìn)行下一步。求反射點，即

(5)計算除最差點外，其余各點的形心為并計算函數(shù)值

若，則用代替形成新的單純形，并返回（3）；否則用代替形成新的單純形，并返回（3）。

(6)當(dāng)，即反射點比最好點還要好，則進(jìn)行擴(kuò)張，得擴(kuò)張點為當(dāng)時，即反射點比最好點差，則進(jìn)行下一步。

(7)當(dāng)時，即反射點比次差點好，則用代替，并返回(3)；若，則進(jìn)行下一步。

(8)如果，計算壓縮點，即計算函數(shù)值求得壓縮點的函數(shù)值后與最差點的函數(shù)值比較，若，則用代替形成新的單純形，返回(3)；否則，進(jìn)行下一步。若，計算壓縮點，即

(9)將單純形邊長縮短，即使單純形向最好點收縮，收縮后的單純形各頂點為然后返回(3)

例：試用單純形法求目標(biāo)函數(shù)的極小值。第五章

約束優(yōu)化方法約束優(yōu)化方法是求解復(fù)雜約束優(yōu)化問題的重要方法。本章主要講述隨機(jī)方向搜索法、復(fù)合形法、可行方向法、懲罰函數(shù)法、增廣乘子法等幾種典型的約束優(yōu)化方法。第一節(jié)概述約束優(yōu)化問題：

直接法：隨機(jī)方向法、可行方向法、復(fù)合形法、簡約梯度法——適于僅含不等式約束間接法：懲罰函數(shù)法、增廣乘子法

——適于同時有等式和不等式約束約束優(yōu)化問題解法

（6-1）一、約束優(yōu)化問題的直接解法

原理：直接從可行的約束區(qū)域內(nèi)尋找最優(yōu)解。

每次迭代：——可行搜索方向)目標(biāo)函數(shù)值下降又不越出可行域。(特點：(1)由于全部求解過程是在可行域內(nèi)進(jìn)行的，因此，迭代計算不論何時終止，都可以獲得一個比初始點好的設(shè)計點。(2)若目標(biāo)函數(shù)為凸函數(shù)，可行域為凸集，則可保證獲得全局最優(yōu)解，如下圖(a)所示；否則，將由于所選擇的初始點的不同，而搜索到局部最優(yōu)解上。如；下圖(b)所示，在這種情況下，搜索結(jié)果經(jīng)常與初始點的選擇有關(guān)。為此，常常在可行域內(nèi)選擇幾個差別較大的初始點分別進(jìn)行計算，以便從求得的多個局部最優(yōu)解中選擇最好的最優(yōu)解——全局最優(yōu)解。(3)要求可行域D為有界非空集，即存在滿足約束條件的點列且目標(biāo)函數(shù)有定義。二、約束優(yōu)化問題的間接解法

間接解法與直接解法有著不同的求解策略，它的基本思路是將約束優(yōu)化問題中的約束函數(shù)進(jìn)行特殊的加權(quán)處理后和目標(biāo)函數(shù)結(jié)合起來，構(gòu)成一個新的目標(biāo)函數(shù)，即將原約束優(yōu)化問題轉(zhuǎn)化成為一個或一系列的無約束優(yōu)化問題，再對新的目標(biāo)函數(shù)進(jìn)行無約束優(yōu)化計算，從而間接地搜索到原約束優(yōu)化問題的最優(yōu)解。

間接解法的基本迭代過程是，首先將式(5．1)所示的約束優(yōu)化問題轉(zhuǎn)化成新的無約束目標(biāo)函數(shù)，即式中——轉(zhuǎn)化后的新目標(biāo)函數(shù)；、——分別為由不等式約束函數(shù)、等式約束函數(shù)經(jīng)過加權(quán)處理后構(gòu)成的某種形式的復(fù)合函數(shù)；——加權(quán)因子。

然后對進(jìn)行無約束優(yōu)化計算。由于在新的目標(biāo)函數(shù)中包含了各種約束條件，在求極值的過程中還將改變加權(quán)因子的大小，由此，可以不斷地調(diào)整設(shè)計點，使其逐步逼近約束邊界，從而間接地求得原約束優(yōu)化問題的最優(yōu)解，這一基本迭代過程如下圖所示。例:求約束優(yōu)化問題的最優(yōu)解。間接解法是目前在機(jī)械優(yōu)化設(shè)計中應(yīng)用較為廣泛的一類有效方法，具有以下特點。(1)由于無約束優(yōu)化方法的研究日趨成熟，已經(jīng)研究出不少有效的無約束優(yōu)化方法和程序，使得間接解法有了可靠的基礎(chǔ)。目前，這類算法的計算效率和數(shù)值計算的穩(wěn)定性也都有很大提高。(2)可以有效地處理具有等式約束條件的約束優(yōu)化問題。(3)間接解法存在的主要問題是，選取加權(quán)因子比較困難，加權(quán)因子選取不當(dāng)響收斂速度和計算精度，甚至?xí)?dǎo)致計算失敗。第二節(jié)隨機(jī)方向搜索法

隨機(jī)方向搜索法是求解約束優(yōu)化設(shè)計問題的一種較為流行的直接解法，這種方法的優(yōu)點是對目標(biāo)函數(shù)的性態(tài)無特殊要求，程序設(shè)計簡單，使用方便。由于可行搜索方向是從許多隨機(jī)方向中選擇的使目標(biāo)函數(shù)值下降最快的方向，加之步長還可以靈活變動，所以該算法的收斂速度比較快。若能取得一個較好的初始點，迭代次數(shù)可以大大減少。它是求解小型機(jī)械優(yōu)化設(shè)計問題的一種十分有效的算法。一、隨機(jī)方向搜索法的基本原理長進(jìn)行搜索，得到新點，新點應(yīng)滿足約束條件：且，至此完成一次迭代，然后，將起始點移至，即令。重復(fù)以上過程，經(jīng)過若干次迭代計算后，最終取得約束最優(yōu)解。

隨機(jī)方向搜索法的基本思路(見下圖)是在可行域內(nèi)選擇一個初始點，利用隨機(jī)數(shù)的概率特性，產(chǎn)生若干個隨機(jī)方向，并從中選擇一個能使目標(biāo)函數(shù)值下降最快的隨機(jī)方向作為可行搜索方向，記作。從初始點出發(fā)，沿可行搜索方向以一定的步在隨機(jī)方向搜索法中，為產(chǎn)生可行的初始點及可行搜索方向，需要用到大量的(0，1)和(-1，1)區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)。在計算機(jī)內(nèi)，隨機(jī)數(shù)通常是按一定的數(shù)學(xué)模型進(jìn)行計算后得到的，這樣得到的隨機(jī)數(shù)稱為偽隨機(jī)數(shù)，它的特點是產(chǎn)生速度快，計算機(jī)內(nèi)存占用少，并且有較好的概率統(tǒng)計特性。產(chǎn)生偽隨機(jī)數(shù)的方法很多，這里僅介紹一種常用的產(chǎn)生偽隨機(jī)數(shù)的數(shù)學(xué)方法二、隨機(jī)數(shù)的產(chǎn)生首先，令，，，?。樾∮诘恼鏀?shù)）,然后按以下步驟計算：令

若

，則

若

，則

，則

若

則為(0，1)區(qū)間內(nèi)均勻分布的偽隨機(jī)數(shù)。利用，很容易求得任意區(qū)間(a，b)內(nèi)的偽隨機(jī)數(shù)，其計算公式為三、初始點的選擇隨機(jī)方向搜索法的初始點必須是一個可行點，即滿足的全部要求，確定這樣的一個點的方法通常有以下兩種。

1．決定性的方法在可行域內(nèi)人為地確定一個可行的初始點。當(dāng)約束條件比較簡單時，這種方法是可用的，但當(dāng)約束條件比較復(fù)雜時，人為選擇這樣一個點就比較困難，因此，建議用隨機(jī)選擇的方法來產(chǎn)生初始點。

2．隨機(jī)選擇的方法

利用計算機(jī)產(chǎn)生的偽隨機(jī)數(shù)選擇可行的初始點，其步驟如下

(1)輸入設(shè)計變量的上限值和下限值，即

(2)在(0，1)區(qū)間內(nèi)產(chǎn)生n個偽隨機(jī)數(shù)

(3)計算隨機(jī)點的各分量，即

(4)判別隨機(jī)點是否可行，若隨機(jī)點為可行點，則取初始點；若隨機(jī)點為非可行點，則返回步驟(2)重新計算，直到產(chǎn)生的隨機(jī)點為可行點為止。四、可行搜索方向的產(chǎn)生長因子(也稱試驗步長)將單位圓縮小或放大，使試驗點落在以為半徑的圓周上。太小，搜索方向的選擇受目標(biāo)函數(shù)局部性質(zhì)的影響大；若太大，同樣數(shù)量的試驗點分別在很大的圓周上，降低了密度，取得較優(yōu)的搜索方向的機(jī)會就會減少，有時還會造成搜索的徒勞往返，影響收斂速度。==如下圖所示，對于二維問題，其單位向量的端點分布于單位圓的圓周上。為了盡可能得到較優(yōu)的搜索方向，可同時選取多個試驗點，從中找出使目標(biāo)函數(shù)值下降最多的試驗點，以該點與初始點的連線方向作為搜索方向。另外，還應(yīng)選取適當(dāng)?shù)牟皆陔S機(jī)方向搜索法中，產(chǎn)生可行搜索方向的方法是從個隨機(jī)方向中，選取一個較好的方向，其計算步驟如下。

(1)在(-1，1)區(qū)間內(nèi)產(chǎn)生偽隨機(jī)數(shù)，按下式計算隨機(jī)單位向量,即

(2)取一試驗步長，按下式計算N個隨機(jī)點：

顯然，N個隨機(jī)點分布在以初始點為中心，以試驗步長為半徑的超球面上。

(3)檢驗N個隨機(jī)點是否為可行點，去除非可行點，計算剩下的可行隨機(jī)點(為可行隨機(jī)點個數(shù))的目標(biāo)函數(shù)值，比較目標(biāo)函數(shù)值的大小，并從中選出目標(biāo)函數(shù)值最小的點，即

(4)比較與兩點的目標(biāo)函數(shù)值的大小，若，則取與兩點的連線方向作為可行搜索方向，即否則，則將試驗步長縮小，返回步驟(1)重新計算，直到出現(xiàn)為止。如果已經(jīng)縮到很