最優(yōu)化理論與方法

1、最優(yōu)化理論與方法綜述李超雄最優(yōu)化方法是近幾十年形成的，它主要運用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)。最優(yōu)化方法的主要研究對象是各種管理問題及其生產(chǎn)經(jīng)營活動。最優(yōu)化方法的目的在于針對所研究的系統(tǒng)，求得一個合理運用人力、物力和財力的最佳方案，發(fā)揮和提高系統(tǒng)的效能及效益，最終達到系統(tǒng)的最優(yōu)目標。實踐表明，隨著科學(xué)技術(shù)的日益進步和生產(chǎn)經(jīng)營的日益發(fā)展，最優(yōu)化方法已成為管理科學(xué)的重要理論基礎(chǔ)和不可缺少的方法，被人們廣泛地應(yīng)用到公共管理、經(jīng)濟管理、工程建設(shè)、國防等各個領(lǐng)域，發(fā)揮著越來越重要的作用。這就是我理解的整個課程的流程。在這整個學(xué)習(xí)的過程當(dāng)中，當(dāng)然也會遇到很多的問題，不論

2、是從理論上的還是從實際將算法編寫出程序來解決一些問題。下面給出學(xué)習(xí)該課程的必要性及結(jié)合老師講解以及在作業(yè)過程中遇到的問題來闡述自己對該課程的理解。20世紀40年代以來，由于生產(chǎn)和科學(xué)研究突飛猛進地發(fā)展，特別是電子計算機日益廣泛應(yīng)用，使最優(yōu)化問題的研究不僅成為一種迫切需要，而且有了求解的有力工具。因此最優(yōu)化理論和算法迅速發(fā)展起來，形成一個新的學(xué)科。至今已出現(xiàn)線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、幾何規(guī)劃、動態(tài)規(guī)劃、隨機規(guī)劃、網(wǎng)絡(luò)流等許多分文。最優(yōu)化理論與算法包括線性規(guī)劃單純形方法、對偶理論、靈敏度分析、運輸問題、內(nèi)點算法、非線性規(guī)劃K-T條件、無約束最優(yōu)化方法、約束最優(yōu)化方法、參數(shù)線性規(guī)劃、運輸問題、

3、線性規(guī)劃路徑跟蹤法、信賴域方法、二次規(guī)劃路徑跟蹤法、整數(shù)規(guī)劃和動態(tài)規(guī)劃等內(nèi)容。最優(yōu)化理論所研究的問題是討論在眾多的方案中什么樣的方案最優(yōu)以及怎樣找出最優(yōu)方案。這類問題普遍存在。例如，工程設(shè)計中怎樣選擇設(shè)計參數(shù)，使得設(shè)計方案滿足設(shè)計要求，又能降低成本；資源分配中，怎樣分配有限資源，使得分配方案既能滿足各方面的基本要求，又能獲得好的經(jīng)濟效益；生產(chǎn)評價安排中，選擇怎樣的計劃方案才能提高產(chǎn)值和利潤；原料配比問題中，怎樣確定各種成分的比例，才能提高質(zhì)量，降低成本；城建規(guī)劃中，怎樣安排基本單位的合理布局，才能方便群眾，有利于城市各行各業(yè)的發(fā)展；農(nóng)田規(guī)劃中，怎樣安排各種農(nóng)作物的合理布局，才能保持高產(chǎn)穩(wěn)產(chǎn)，發(fā)

4、揮地區(qū)優(yōu)勢；軍事指揮中，怎樣確定最佳作戰(zhàn)方案，才能有效地消滅敵人，保存自己，有利于戰(zhàn)爭的全局；在人類活動的各個領(lǐng)域中，諸如此類，不勝枚舉。最優(yōu)化這一數(shù)學(xué)分支，正是為這些問題的解決，提供理論基礎(chǔ)和求解方法，它是一門應(yīng)用廣泛、實用性強的學(xué)科。l=J最優(yōu)化，在熱工控制系統(tǒng)中應(yīng)用非常廣泛。為了達到最優(yōu)化目的所提出的各種求解方法。從數(shù)學(xué)意義上說，最優(yōu)化方法是一種求極值的方法，即在一組約束為等式或不等式的條件下，使系統(tǒng)的目標函數(shù)達到極值，即最大值或最小值。從經(jīng)濟意義上說，是在一定的人力、物力和財力資源條件下，使經(jīng)濟效果達到最大，或者在完成規(guī)定的生產(chǎn)或經(jīng)濟任務(wù)下，使投入的人力、物力和財力等資源為最少。通過老

5、師的講解，我們了解不同類型的最優(yōu)化問題可以有不同的最優(yōu)化方法，即使同一類型的問題也可有多種最優(yōu)化方法。反之,某些最優(yōu)化方法可適用于不同類型的模型。最優(yōu)化問題的求解方法一般可以分成解析法、直接法。1、直接法當(dāng)目標函數(shù)較為復(fù)雜或者不能用變量顯函數(shù)描述時，無法用解析法求必要條件。此時可采用直接搜索的方法經(jīng)過若干次迭代搜索到最優(yōu)點。這種方法常常根據(jù)經(jīng)驗或通過試驗得到所需結(jié)果。對于一維搜索（單變量極值問題），一維搜索介紹了黃金分割法即為0.618法（前提是存在單峰區(qū)間（所以在此時要提出使用進退法來得到該單峰區(qū)間）、二分法（效率最高，但是必須求取函數(shù)的導(dǎo)數(shù)不好求）、拋物線法（不推薦）；對于多維搜索問題（多

6、變量極值問題）。 黃金分割法是一維搜索方法，只針對一元函數(shù)來求解。黃金分割法的局限性在于要求是單峰函數(shù)，所以要先用進退法找到一個函數(shù)的其中一個單峰。步驟就是在區(qū)間a,b中取點xl二a+0.382（b-a）,x2二a+0.618（b-a）,如果f（xl）f（x2）,說明選取的步長太小，要擴大，令a=x1，x1=x2,再求新的x2;如果f（x1）=f（x2），步長選取過大，縮小步長，令b=x2,x2=x1,再求新的xl,循環(huán)。這樣做每次可將搜索區(qū)間縮小0.382倍或0.618倍，直至縮為最小點。該算法為收斂速度很快的一維搜索方法。前提是要先利用進退法選擇一個下降的單峰區(qū)間（即黃金分割法的單峰搜索區(qū)

7、間）。 進退法用進退法來確定下單峰區(qū)間，即黃金分割法的搜索區(qū)間。2、線性規(guī)劃問題單純形法對于一般形式的線性規(guī)劃問題，引入松弛變量或者剩余變量來化為標準型，可以將引入的變量作為初始基變量，該基變量對應(yīng)的單位陣可以作為一個初始基可行解，然后進行單純形法求解過程。如果線性規(guī)劃是非退化的,則按照進基,離基迭代一次后,目標函數(shù)值有所下降.經(jīng)過有限次迭代之后,一定可以得到一個基可行解,使得其所有判別數(shù)非負（得到最優(yōu)解）,或者其有一個判別數(shù)是負的,但對應(yīng)列向量的所有分量非正（線性規(guī)劃無最優(yōu)解）。而對于一般標準型的線性規(guī)劃問題，約束方程組的系數(shù)矩陣中不包含單位陣，從而需要引入人工變量，構(gòu)造一個單位矩陣，得到初

8、始基可行解的方法。而利用單純形法求解問題最關(guān)鍵的環(huán)節(jié)是初始基可行解的求解，因為單純形法的迭代過程是在已有一個初始基可行解的前提下進行的，而常用的方法有兩種，一是大M法，二是兩階段法。 大M單純形法，其中M定義為一個比較大的數(shù)，通常比系數(shù)矩陣中的系數(shù)大一個數(shù)量級，與引入的人工變量結(jié)合構(gòu)造輔助線性規(guī)劃問題，從而也在系數(shù)矩陣中構(gòu)造出了單位陣對應(yīng)的變量值作為一組初始基可行解進行單純形法的迭代運算。在取得的最優(yōu)解中人工變量全為零，即M的引入不影響目標函數(shù)的最優(yōu)解。 對偶單純形法，單純形法與對偶單純形法是對偶的可以互相轉(zhuǎn)換可以簡化求解過程,而對偶之間只有最優(yōu)解是相等的。單純形法保證解可行，而對偶單純形法保

9、證對偶規(guī)劃解可行。不同點在于對偶單純形法的最優(yōu)性判別是已知線性規(guī)劃問題的基矩陣B及它所對應(yīng)的基解的所有的判別數(shù)非負（即XB=B-lb=O）時有最優(yōu)解。對偶單純形法并不是解對偶線性規(guī)劃問題的單純形法，而是根據(jù)對偶原理求解原線性規(guī)劃問題的另一種單純形法。3、無約束最優(yōu)化問題解析法只適用于目標函數(shù)有明顯的解析表達式的情況。求解方法是：先求出最優(yōu)的必要條件，得到一組方程或不等式，再求解這組方程或不等式，一般是用求導(dǎo)數(shù)的方法求出必要條件，通過必要條件將問題簡化，因此也稱間接法。這種方法針對的是無約束最優(yōu)化，主要考慮下降算法包括最速下降法、newton法、共軛梯度法、擬newton法等。最速下降法是求梯度

10、的方法中效率最低的方法，它所提供的下降方向只是眼前下降最快的方向，用圖形表示是一種鋸齒形的路線，收斂速度慢，但是迭代計算量小、算法簡單它的原理就是沿著負梯度方向就是下降速度最快的方向，主要步驟就是取初值以及允許誤差，求取函數(shù)的負梯度，若梯度范數(shù)小于允許誤差，此時得到最優(yōu)解。反之，得到此時的xk再用一維搜索求取合適的步長滿足最小函數(shù)值方程，計算下一個xk+1值，求出梯度，循環(huán)計算最小函數(shù)值找到最優(yōu)解。最速下降法基本思想：最速下降法是應(yīng)用目標函數(shù)的負梯度方向作為每一步迭代的搜索方向，因為每一步都取負梯度方向的最優(yōu)步長。使用條件：目標函數(shù)在迭代點處必須可微，且導(dǎo)數(shù)不為0。特點：沿負梯度方向?qū)?yōu)的最優(yōu)

11、梯度法，其搜索路徑實際上是成直角的鋸齒形前進的它是在某一點附近的最速下降方向，是一局部性質(zhì)，開始時步長較大，收斂速度較快，但越接近極小點，步長越小，收斂速度越慢。Newton法有很快的收斂速度，但它只是局部收斂的。所以提出共軛梯度法。如果在共軛方向法中初始的共軛向量恰好取為初始點X0處的負梯度-go,而以下各共軛方向Pk由第k迭代點Xk處的負梯度-gk與已經(jīng)得到的共軛向量Pk-1的線性組合來確定，那么就構(gòu)成了一種具體的共軛方向法。因為每一個共軛向量都是依賴于迭代點處的負梯度而構(gòu)造出來的，所以稱為共軛梯度法。產(chǎn)生的N個共軛方向pk+1k+1II2+Bp,k=0,1，,n2,kk,k=0,1,.,

12、n一2.Newton法，算法流程如下：（l）取初始點x，置精度要求£，置k二1如果|vf（xk）|<£，則停止計算（x（k）作為無約束問題的解）；否則求解線性方程組v2f（x（k）d二Vf（x（k），得到d（k）（3）置x（k+1）=x（k）+d（k），k二k+1，轉(zhuǎn)（2）牛頓迭代法是求方程根的重要方法之一。約束最優(yōu)化方法包括：Kuhn-Tucker條件，既約梯度法及凸單純行法，罰函數(shù)法及乘子法。罰函數(shù)法包括簡單罰函數(shù)法、內(nèi)點罰函數(shù)法和乘子法。約束最優(yōu)化方法：問題minf（x）s.t.g（x）<0h（x）二0約束集S=xlg（x）<0,h（x）=0共軛梯度

13、法的效果介于最速下降法和newton法之間，既能克服最速下降法的慢收斂性，又避免了newton法的計算量大和具有局部收斂性的缺點，因而是比較有效的算法。而且共軛方向法中的共軛梯度法，由于其存貯量小，可用來求解大規(guī)模（n較大）無約束優(yōu)化問題?；舅枷耄汗曹椞荻确ㄊ菍ψ钏傧陆捣ㄟM行了修正的一種尋優(yōu)方法，它是使搜索方向為共軛方向（將負梯度方向旋轉(zhuǎn)一個角度），即每步的搜索方向都要對該步的負梯度方向做一個修正。算法特點：共軛梯度法利用了各步搜索方向關(guān)于互為共軛的性質(zhì)，它是利用梯度信息尋找共軛方向的；共軛梯度法具有二次終結(jié)的性質(zhì)，這一點與共軛方向法相同，且其存儲量小，不需存儲矩陣，只需存儲向量，在大規(guī)模問

14、題中具有明顯優(yōu)勢；但在實踐中由于初始點選擇不當(dāng)或計算機的舍入誤差等原因，會出現(xiàn)二次終結(jié)時精度不高的情況。此時，可繼續(xù)迭代或重新開始新一輪共軛梯度法搜索或改用其他數(shù)值算法以滿足高精度的要求。無約束最優(yōu)化的直接法；單純形調(diào)優(yōu)法（與線性規(guī)劃中的不同，是針對非線性的問題的求解方法）。單純形法求解控制系統(tǒng)參數(shù)優(yōu)化。具體過程是給定尋優(yōu)參數(shù)初值，然后利用matlab優(yōu)化工具箱來構(gòu)造誤差目標函數(shù)（給定控制對象參數(shù)），再進行以下四步操作：反射，延伸，擴張和收縮。在此過程中有很多問題，開始不熟悉優(yōu)化工具箱，所以無法建立誤差目標函數(shù)；而且利用優(yōu)化工具箱無法加入延遲環(huán)節(jié)；確定各個計算公式的系數(shù)（反射、擴大、收縮、壓縮

15、）的值是個大問題，對最壞值的判斷很關(guān)鍵，什么條件下被取代的一系列的問題，最后得出最優(yōu)解（但是得到的參數(shù)PI都非常大），則在simulink搭建該仿真系統(tǒng)（不知道應(yīng)該如何建立被控對象的延遲環(huán)節(jié)的函數(shù)），將優(yōu)化后的參數(shù)帶入，觀察分析所得曲線卻能很好的滿足系統(tǒng)性能優(yōu)化。對于如此大的參數(shù)，在實際應(yīng)用中肯定是會造成該系統(tǒng)劇烈振蕩的不穩(wěn)定的。4、約束最優(yōu)化問題約束最優(yōu)化方法是指對于一般非線性規(guī)劃模型的求解方法。懲罰函數(shù)法（包括外罰函數(shù)法和閘函數(shù)法）是一種有效的求解方法。而在構(gòu)造罰函數(shù)的過程中，對于不等式約束和等式約束的構(gòu)造方式是不一樣的：對于不等式約束是用對數(shù)或者是倒數(shù)來構(gòu)造，而對于等式約束則是求平方和來構(gòu)造。步驟是：構(gòu)造罰函數(shù)是為了將約束問題改變?yōu)闊o約束的問題進行求解，將問題簡單化。內(nèi)罰函數(shù)的步驟選取初始數(shù)據(jù)，給定初始內(nèi)點（必須是可行的（即保證在可行域內(nèi)），這樣最終結(jié)