最優(yōu)化方法綜述

最優(yōu)化方法綜述1.引論1.1應(yīng)用介紹最優(yōu)化理論與算法是一個重要的數(shù)學(xué)分支，它所研究的問題是討論在眾多的方案中什么樣的方案最優(yōu)以及怎樣找出最優(yōu)方案。這類問題普遍存在。例如，工程設(shè)計中怎樣選擇設(shè)計參數(shù)，使得設(shè)計方案滿足設(shè)計要求，又能降低本錢；資源分配中，怎樣分配有限資源，使得分配方案既能滿足各方面的根本要求，又能獲得好的經(jīng)濟效益；生產(chǎn)評價安排中，選擇怎樣的方案方案才能提高產(chǎn)值和利潤；原料配比問題中，怎樣確定各種成分的比例，才能提高質(zhì)量，降低本錢；城建規(guī)劃中，怎樣安排工廠、機關(guān)、學(xué)校、商店、醫(yī)院、住戶和其他單位的合理布局，才能方便群眾，有利于城市各行各業(yè)的開展；農(nóng)田規(guī)劃中，怎樣安排各種農(nóng)作物的合理布局，才能保持高產(chǎn)穩(wěn)產(chǎn)，發(fā)揮地區(qū)優(yōu)勢；軍事指揮中，怎樣確定最正確作戰(zhàn)方案，才能有效地消滅敵人，保存自己，有利于戰(zhàn)爭的全局；在人類活動的各個領(lǐng)域中，諸如此類，不勝枚舉。最優(yōu)化這一數(shù)學(xué)分支，正是為這些問題的解決，提供理論根底和求解方法，它是一門應(yīng)用廣泛、實用性強的學(xué)科。1.2優(yōu)化的問題的根本概念工程設(shè)計問題一般都可以用數(shù)學(xué)模型來描述，即轉(zhuǎn)化為數(shù)學(xué)模型。優(yōu)化設(shè)計的數(shù)學(xué)模型通常包括設(shè)計變量、目標(biāo)函數(shù)和約束條件。三個根本要素。設(shè)計變量的個數(shù)決定了設(shè)計空間的維數(shù)。確定設(shè)計變量的原那么是：在滿足設(shè)計根本要求的前提下，將那些對設(shè)計目標(biāo)影響交大的而參數(shù)選為設(shè)計變量，而將那些對設(shè)計目標(biāo)影響不大的參數(shù)作為設(shè)計變量，并根據(jù)具體情況，賦以定值，以減少設(shè)計變量的個數(shù)。用來評價和追求最優(yōu)化設(shè)計方案的函數(shù)就稱為目標(biāo)函數(shù)，目標(biāo)函數(shù)的一般表達式為。優(yōu)化設(shè)計的目的，就是要求所選擇的設(shè)計變量使目標(biāo)函數(shù)到達最正確值。所謂最正確值就是極大值或極小值。在設(shè)計空間中，雖然有無數(shù)個設(shè)計點，即可能的設(shè)計方案，但是一般工程實際問題對設(shè)計變量的取值總是有一些限制的，這些限制條件顯然是設(shè)計變量的函數(shù)，一般稱之為優(yōu)化設(shè)計問題的約束條件或約束函數(shù)。在優(yōu)化設(shè)計問題中，約束條件有兩種表現(xiàn)形式，一種是不等式約束，其一般表達式為：，另一種是等式約束，即。由設(shè)計變量、目標(biāo)函數(shù)和約束條件三個根本要素所組成的工程優(yōu)化設(shè)計數(shù)學(xué)模型所表達的意思是：在滿足一定的約束以偶案件下，尋求一組設(shè)計變量，使得目標(biāo)函數(shù)取得極小值或極大值。在設(shè)計空間中，每一個不等式約束條件都把設(shè)計空間劃分成兩局部，一局部是滿足不等式約束條件的，另一局部是不滿足約束條件的，兩局部的分界面就是所形成的曲面，稱為約束面。在二維設(shè)計空間中約束面是一條曲線或直線，在三維設(shè)計空間中那么是一個曲面或超曲面。一個優(yōu)化設(shè)計問題的所有不等式約束的邊界將組成一個復(fù)合約束邊界。滿足約束條件的區(qū)域稱為可行域，而不滿足約束條件的區(qū)域稱為非可行域?？尚杏騼?nèi)的點稱為可行點。1.3分類：假設(shè)工程優(yōu)化設(shè)計問題的數(shù)學(xué)模型中只有目標(biāo)函數(shù)而沒有約束條件，那么稱之為無約束優(yōu)化問題。無約束優(yōu)化問題的目標(biāo)函數(shù)如果是一元函數(shù)，，那么稱之為一維優(yōu)化問題，他的求解方法稱之為一維搜索方法。對于約束優(yōu)化問題，課按其目標(biāo)函數(shù)和約束函數(shù)的特性，分為線性規(guī)劃問題和非線性規(guī)劃問題。如果目標(biāo)函數(shù)和所有的約束函數(shù)都是線性函數(shù)，那么稱之為線性規(guī)劃問題；否那么稱之為非線性規(guī)劃問題。對于目標(biāo)函數(shù)是二次函數(shù)而約束函數(shù)都是線性函數(shù)這一類問題，一般稱之為二次規(guī)劃問題。另外，還有整數(shù)規(guī)劃、幾何規(guī)劃和多目標(biāo)規(guī)劃等。線性規(guī)劃和非線性規(guī)劃是數(shù)學(xué)規(guī)劃中歐偶那個的兩個重要的分支，在工程實際問題中均得到了廣泛的應(yīng)用。1.4凸函數(shù)、凸規(guī)劃：工程優(yōu)化設(shè)計問題大多是非線性規(guī)劃問題，其數(shù)學(xué)本質(zhì)是多元非線性函數(shù)求極值問題，如果函數(shù)在整個區(qū)域有兩個或兩個以上的極值點，那么稱每一個極值點為局部極值點。在整個可行域中，比擬所有的局部極值點，可得到一個最小或最大的局部極值點，稱為全局極值點。但基于數(shù)學(xué)規(guī)劃的工程優(yōu)化設(shè)計方法一般只能求得為題的局部極值點，只有當(dāng)函數(shù)具有凸性的情況下，局部極值點才是全域極值點。對于一元函數(shù)來說，在某區(qū)間內(nèi)，如果函數(shù)的曲線是下凸的，即在刺區(qū)間內(nèi)，一元函數(shù)曲線上任意兩點間相連的弦線，總不會位于這兩點間函數(shù)曲線的下面，那么稱此一元函數(shù)具有凸性，或稱此函數(shù)為凸函數(shù)；反之，假設(shè)函數(shù)曲線上任意兩點間相連的弦線，總不會位于這兩點間的函數(shù)曲線的上面，那么稱此函數(shù)具有下凸性，或稱此函數(shù)為凹函數(shù)。如果約束優(yōu)化問題中的目標(biāo)函數(shù)是凸函數(shù)，所有的不等式約束也都是凸函數(shù)，那么稱此約束優(yōu)化問題為凸規(guī)劃。凸規(guī)劃具有一個重要特性，這就是：凸規(guī)劃的局部極小值一定是全域極小值。對于凸規(guī)劃問題，只要求出一個局部極小值，它就是全域極小值。所以，優(yōu)化理論與方法常限于討論凸規(guī)劃問題，故稱為凸規(guī)劃理論。應(yīng)強調(diào)指出的是。實際工程優(yōu)化問題往往不是凸規(guī)劃問題。所以，采用常用的優(yōu)化方法，求得的最優(yōu)解往往是局部最優(yōu)解。凸規(guī)劃的可行域是凸集。2.線性規(guī)劃問題：2.1線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃即目標(biāo)函數(shù)和約束函數(shù)都是線性的約束最優(yōu)化問題。線性規(guī)劃在理論和計算方法上都很成熟。他在工程管理和經(jīng)濟管理中，應(yīng)用都和廣泛。它的解法在理論上和方法上都很成熟。雖然大多數(shù)工程設(shè)計是非線性的，但是也有采用線性逼近方法求解非線性問題的。此外，線性規(guī)劃方法還常被用作解決非線性問題的子問題的工具，如在可行方向法中可行方向的尋求就是采用線性規(guī)劃方法。當(dāng)然，對于真正的線性優(yōu)化問題，線性規(guī)劃方法就更有用了。線性規(guī)劃的標(biāo)準(zhǔn)形式：n為線性規(guī)劃的維數(shù)，m為線性規(guī)劃的階數(shù)，一般m<n。任何其他形式的線性規(guī)劃均可化為標(biāo)準(zhǔn)形式，并可借助標(biāo)準(zhǔn)形式的求解方法求解。一般形式化成標(biāo)準(zhǔn)形式的方法：⑴如果目標(biāo)函數(shù)為極大化，那么可轉(zhuǎn)化為極小化，因為在同樣的約束條件下，maxz與min〔-z〕有相同的最優(yōu)解，故以后常限于討論極小化的情況。⑵在約束條件中，如果有不等式約束：那么可加上新的變量，把他們?nèi)優(yōu)榈仁郊s束，即如果有不等式約束那么可以減去新的變量，把他們?nèi)孔優(yōu)榈仁羌s束，即以上這些引進來的新變量叫做松弛變量，松弛變量并不出現(xiàn)在目標(biāo)函數(shù)中，也不影響問題的解。因此可把所有的約束條件化為統(tǒng)一的等式形式。⑶當(dāng)在某些問題中，實際情況并不要求某一變量為非負時，可另，其中，，并將其帶入目標(biāo)函數(shù)和約束方程中去。線性規(guī)劃的幾個根本概念⑴可行解凡同時滿足標(biāo)準(zhǔn)形式中目標(biāo)函數(shù)和約束條件的任何一個解，稱為線性問題的可行解。所有可行解的集合稱為可行域。⑵根本解另標(biāo)準(zhǔn)形式中某〔n-m〕個變量等于零，如果剩余的m個變量構(gòu)成的m個線性方程有唯一的解，那么稱由此得到的n個變量的解為根本解。⑶根本可行解凡滿足非負條件的根本解為根本可行解，即既是根本解又是可行解。⑷最優(yōu)解滿足目標(biāo)函數(shù)的可行解是線性規(guī)劃的最優(yōu)解〔即目標(biāo)函數(shù)到達最小值的可行解叫最優(yōu)解〕。當(dāng)一個線性規(guī)劃的值無窮大時，那么稱這樣的線性規(guī)劃是無界的。⑸根本變量和非根本變量根本可行解中大于零的分量稱為根本變量，其余變量稱為非根本變量。根本變量和非根本變量是相對于根本可行解來說的。⑹基向量與基根本變量所對應(yīng)的系數(shù)稱為基向量。線性規(guī)劃有如下兩個根本性質(zhì)：⑴線性規(guī)劃可行解的集合構(gòu)成一個凸集，且這個凸集是凸多面體。它的每一個定點對應(yīng)一個根本可行解。⑵線性規(guī)劃的最優(yōu)解如果存在，必然在凸集的某個頂點上到達。2.2解線性規(guī)劃的單純形法：求解思路：單純形法是從一個初始根本可行解出發(fā)，尋找使目標(biāo)函數(shù)有較大下降的一個新的根本可行解代替原來的根本可行解，如此完成一個迭代。經(jīng)過判斷，如果沒到達最優(yōu)點，那么繼續(xù)迭代下去。根本可行解的個數(shù)是有限的，所以經(jīng)過有限次迭代，一定能到達最優(yōu)解。采用單純形法求解線性規(guī)劃，主要解決以下三個問題：⑴如何確定根本可行解；⑵如何由一個根本可行解迭代出另一個根本可行解，并使目函數(shù)值獲得較大的下降方向；⑶如何判斷一個根本可行解是否為最優(yōu)解。3.無約束優(yōu)化方法無約束優(yōu)化問題的一般數(shù)學(xué)表達式為求解這類問題的方法，稱為無約束優(yōu)化方法。假設(shè)為一元函數(shù)，求解這類為題的無約束優(yōu)化方法稱為一維搜索方法。求解優(yōu)化問題的迭代算法是按迭代格式求解的，即從點出發(fā)，沿給定的方向搜索，以得到目標(biāo)函數(shù)沿方向的極小點，其實質(zhì)是求的一個最優(yōu)步長因子使和是已確定的，所以上述表達式所表達的問題就是以為設(shè)計變量的一維優(yōu)化為題，因而一維搜索方法是優(yōu)化方法的根底。一維搜索方法有：分數(shù)法、黃金分割法、二次插值法和三次插值法。多元函數(shù)的無約束優(yōu)化方法，可按其確定搜索方向所使用的信息和方法的不同氣氛兩大類。一類方法是需要利用函數(shù)的一階偏導(dǎo)數(shù)甚至是二階偏導(dǎo)數(shù)都早搜索方向，如梯度法、牛頓法、變尺度法和共軛梯度法等。這種方法計算量大，但收斂較快，一般稱之為解析法。另一種方法是僅利用迭代點的函數(shù)值來構(gòu)造搜索方向，如坐標(biāo)輪換法、模式搜索法、方向加速法和單純形法。只需要計算函數(shù)值，無需求導(dǎo)，這類方法有突出的優(yōu)越性，一般稱之為直接法。3.1牛頓法牛頓法根本思想：求的極小值時，先將它在點附近作泰勒展開，取二次近似函數(shù)值，再求出這個二次函數(shù)的極小點，并一該極小點作為原目標(biāo)函數(shù)的極小點x的一次近似值；假設(shè)此值不滿足精度要求，那么可以此近似值作為下一次迭代的初始點，仿照上面的做法，求出二次近似值；照此方法迭代下去，直至所求出的近似極小點滿足精度要求為止。牛頓迭代法的公式是：牛頓法所采用的搜索方向為其中是海色矩陣，步長因子。3.2共軛方向法共軛方向的概念是在研究二次函數(shù)〔3.1〕時提出的，就是首先以3.1式的二次函數(shù)為目標(biāo)給出有關(guān)算法，然后再推廣到一般的目標(biāo)函數(shù)中去。共軛方向的性質(zhì)共軛方向有如下三個性質(zhì)：性質(zhì)1假設(shè)非零向量系是對共軛的，那么這m個向量是線性無關(guān)的。性質(zhì)2在n維空間中互相共軛的非零向量的個數(shù)不超過n。性質(zhì)3從任意初始點出發(fā)，順次沿n個G的共軛方向進行一維搜索，最多經(jīng)過n次迭代就可以找到上式所表示的二次函數(shù)極小點，此性質(zhì)說明這種迭代方法具有二次收斂性。Powell共軛方向法Powell法是一種求解無約束優(yōu)化問題的較為有效的方法。其根本原理是：首先采用坐標(biāo)輪換法進行第一輪迭代，然后以第一輪迭代的最末一個極小點和初始點，構(gòu)成一個新的方向，并以此新的方向作為最末一個方向，而去掉第一個方向，得到第二輪迭代的n個方向。仿此進行下去，直至求得問題的極小值。3.3不精確的一維搜索用于多維NLP計算過程中，其根本思想是：從出發(fā)，沿方向，移動一定的距離，求使有足夠的下降。3.4變尺度法〔DFP法〕其根本思想是利用牛頓法的迭代公式，然而并不直接計算，而是用一個對稱正定矩陣近似的代替。在迭代過程中，不斷改良，最后逼近。變尺度法的迭代公式為其中為變尺度法的搜索方向；為變尺度矩陣，在迭代過程中逐次形成并不斷修正。變尺度法的特點：變尺度法在最初的幾步迭代，與梯度法類似，函數(shù)值的下降是較快的而在最后的幾步迭代，變尺度法與牛頓法相近，可較快的收斂到極小點。因而變尺度法就克服了梯度法收斂慢的缺點，但卻保存了梯度法在最初幾步，函數(shù)值下降快的優(yōu)點；同時，變尺度法防止了計算海色矩陣及其逆矩陣，克服了牛頓法計算量大的缺點，但卻有較快的收斂速度。4.約束優(yōu)化問題工程優(yōu)化設(shè)計問題絕大多數(shù)屬于約束非線性優(yōu)化問題，它的一般數(shù)學(xué)表達式為其中、、都假定具有連續(xù)偏導(dǎo)數(shù)。求解這類問題的方法稱為約束優(yōu)化方法。起作用約束：假設(shè)在極小點附近，不等式約束變成了等式約束，那么該約束條件顯然是起作用約束，約束極值點必然存在于這些起作用約束條件的極值上。不起作用約束：在實際的工程優(yōu)化設(shè)計問題中，多數(shù)的不等式約束條件在極值點是不起作用的，因而，在某種條件下是可以忽略的。Kuhn-Tucker條件：對于一般約束優(yōu)化問題如果是上述優(yōu)化問題的最優(yōu)解，那么有滿足以上兩式的點為Kuhn—Tucker點。4.1懲罰函數(shù)法懲罰函數(shù)法是一種用來求解約束優(yōu)化問題的間接方法。根本思想是：將一個有約束的問題轉(zhuǎn)化為一系列的無約束的優(yōu)化問題來求解。其根據(jù)懲罰項的不同函數(shù)形式，分為外罰函數(shù)法、內(nèi)罰函數(shù)法和混合函數(shù)法。外罰函數(shù)法：其主要在特點是是懲罰函數(shù)定義在可行域的外部，從而在求解系列無約束優(yōu)化問題的過程中，從可行域的外部逐漸逼近原約束優(yōu)化問題的最優(yōu)解。內(nèi)罰函數(shù)法：內(nèi)罰函數(shù)法只可用來求解不等式約束優(yōu)化問題，而不能求解等式約束優(yōu)化問題。其主要特點是將懲罰函數(shù)定義在可行域的內(nèi)部，這樣在求解內(nèi)罰函數(shù)的序列無約束優(yōu)化問題的過程中，所求得的系列無約束優(yōu)化問題的解總是可行解，從而從可行域的內(nèi)部逐漸逼近原約束優(yōu)化問題的解?；旌狭P函數(shù)法：混合罰函數(shù)法的根本思想是：當(dāng)初始點給出后，對等式約束和不能滿足的那些不等式約束，用外函數(shù)法，而對所滿足的那些不等式約束，那么用內(nèi)函數(shù)法。4.2乘子法廣義乘子法既可以解決線性優(yōu)化問題，也可以解決非線性優(yōu)化問題，廣義乘子法所采取的根本策略與廣義乘子法沒有太大的不同，二者都是在原約束優(yōu)化問題的根底上，構(gòu)造一系列無約束優(yōu)化問題，并以這一系列無約束優(yōu)化問題的解去逼近原約束優(yōu)化問題的解，所不同的是，廣義乘子法不像外罰函數(shù)法那樣直接構(gòu)造原約束優(yōu)化問題的外罰函數(shù)作為無約束優(yōu)化子問題，而是先構(gòu)造原問題的的外罰函數(shù)代替原問題的目標(biāo)函數(shù)，得到一個增廣極值問題，然后再構(gòu)造增廣極值問題的拉格朗日函數(shù)作為原問題的無約束優(yōu)化子問題，并以此系列無約束優(yōu)化子問題的解去逼近原約束優(yōu)化子問題的解。理論和實踐證明，采用這樣的廣義乘子法時，只需要在罰因子充分大而無需趨近于無窮的情況下，調(diào)節(jié)拉格朗日乘子便可以逐次逼近原約束優(yōu)化問題的解。4.3Rosen梯度投影法定義：設(shè)p為n階矩陣，假設(shè)，那么稱p為投影矩陣。考慮問題其中是可微函數(shù)，A為矩陣，，E為矩陣。梯度投影法的根本思想仍然是從可行點出發(fā)，沿可行方向進行搜索。當(dāng)?shù)霭l(fā)點在可行域內(nèi)部時，沿負梯度方向進行搜索。當(dāng)?shù)霭l(fā)點在某些約束的邊界上時，將該點處的負梯度投影到M的零空間，M是以起作用約束或局部起作用約束的梯度行為構(gòu)造成的矩陣。4.4二次規(guī)劃二次規(guī)劃是非線性規(guī)劃中的一種特殊情形，它的目標(biāo)函數(shù)是二次實函數(shù)，約束是線性的。二次規(guī)劃法的根本原理是將原問題轉(zhuǎn)化為一系列二次規(guī)劃子問題。求解子間題，得到本次迭代的搜索方向，沿搜索方向?qū)?yōu)，最終逼近問題的最優(yōu)點，因此這種方法又稱序列二次規(guī)劃法。另外，算法是利用擬牛頓法(變尺度法)來近似構(gòu)造海賽矩陣，以建立二次規(guī)劃子問題，故又可稱約束變尺度法，這種方法被認為是目前最先進的非線性規(guī)