1.引論
1.1應用介紹
最優化理論與演算法是乙個重要的數學分支，它所研究的問題是討論在眾多的方案中什麼樣的方案最優以及怎樣找出最優方案。這類問題普遍存在。例如，工程設計中怎樣選擇設計引數，使得設計方案滿足設計要求，又能降低成本；資源分配中，怎樣分配有限資源，使得分配方案既能滿足各方面的基本要求，又能獲得好的經濟效益；生產評價安排中，選擇怎樣的計畫方案才能提高產值和利潤；原料配比問題中，怎樣確定各種成分的比例，才能提高質量，降低成本；城建規劃中，怎樣安排工廠、機關、學校、商店、醫院、住戶和其他單位的合理布局，才能方便群眾，有利於城市各行各業的發展；農田規劃中，怎樣安排各種農作物的合理布局，才能保持高產穩產，發揮地區優勢；軍事指揮中，怎樣確定最佳作戰方案，才能有效地消滅敵人，儲存自己，有利於戰爭的全域性；在人類活動的各個領域中，諸如此類，不勝列舉。
最優化這一數學分支，正是為這些問題的解決，提供理論基礎和求解方法，它是一門應用廣泛、實用性強的學科。
1.2優化的問題的基本概念
工程設計問題一般都可以用數學模型來描述，即轉化為數學模型。優化設計的數學模型通常包括設計變數、目標函式和約束條件。三個基本要素。
設計變數的個數決定了設計空間的維數。確定設計變數的原則是：在滿足設計基本要求的前提下，將那些對設計目標影響交大的而引數選為設計變數，而將那些對設計目標影響不大的引數作為設計變數，並根據具體情況，賦以定值，以減少設計變數的個數。
用來評價和追求最優化設計方案的函式就稱為目標函式，目標函式的一般表示式為。
優化設計的目的，就是要求所選擇的設計變數使目標函式達到最佳值。所謂最佳值就是極大值或極小值。在設計空間中，雖然有無數個設計點，即可能的設計方案，但是一般工程實際問題對設計變數的取值總是有一些限制的，這些限制條件顯然是設計變數的函式，一般稱之為優化設計問題的約束條件或約束函式。
在優化設計問題中，約束條件有兩種表現形式，一種是不等式約束，其一般表示式為：，另一種是等式約束，即。
由設計變數、目標函式和約束條件三個基本要素所組成的工程優化設計數學模型所表達的意思是：在滿足一定的約束以偶案件下，尋求一組設計變數，使得目標函式取得極小值或極大值。
在設計空間中，每乙個不等式約束條件都把設計空間劃分成兩部分，一部分是滿足不等式約束條件的，另一部分是不滿足約束條件的，兩部分的分介面就是所形成的曲面，稱為約束面。在二維設計空間中約束面是一條曲線或直線，在三維設計空間中則是乙個曲面或超曲面。乙個優化設計問題的所有不等式約束的邊界將組成乙個復合約束邊界。
滿足約束條件的區域稱為可行域，而不滿足約束條件的區域稱為非可行域。可行域內的點稱為可行點。
1.3分類：
若工程優化設計問題的數學模型中只有目標函式而沒有約束條件，則稱之為無約束優化問題。無約束優化問題的目標函式如果是一元函式，，則稱之為一維優化問題，他的求解方法稱之為一維搜尋方法。對於約束優化問題，課按其目標函式和約束函式的特性，分為線性規劃問題和非線性規劃問題。
如果目標函式和所有的約束函式都是線性函式，則稱之為線性規劃問題；否則稱之為非線性規劃問題。對於目標函式是二次函式而約束函式都是線性函式這一類問題，一般稱之為二次規劃問題。另外，還有整數規劃、幾何規劃和多目標規劃等。
線性規劃和非線性規劃是數學規劃中歐偶那個的兩個重要的分支，在工程實際問題中均得到了廣泛的應用。
1.4凸函式、凸規劃：
工程優化設計問題大多是非線性規劃問題，其數學本質是多元非線性函式求極值問題，如果函式在整個區域有兩個或兩個以上的極值點，則稱每乙個極值點為區域性極值點。在整個可行域中，比較所有的區域性極值點，可得到乙個最小或最大的區域性極值點，稱為全域性極值點。但基於數學規劃的工程優化設計方法一般只能求得為題的區域性極值點，只有當函式具有凸性的情況下，區域性極值點才是全域極值點。
對於一元函式來說，在某區間內，如果函式的曲線是下凸的，即在刺區間內，一元函式曲線上任意兩點間相連的弦線，總不會位於這兩點間函式曲線的下面，則稱此一元函式具有凸性，或稱此函式為凸函式；反之，若函式曲線上任意兩點間相連的弦線，總不會位於這兩點間的函式曲線的上面，則稱此函式具有下凸性，或稱此函式為凹函式。
如果約束優化問題中的目標函式是凸函式，所有的不等式約束也都是凸函式，則稱此約束優化問題為凸規劃。凸規劃具有乙個重要特性，這就是：凸規劃的區域性極小值一定是全域極小值。
對於凸規劃問題，只要求出乙個區域性極小值，它就是全域極小值。所以，優化理論與方法常限於討論凸規劃問題，故稱為凸規劃理論。應強調指出的是。
實際工程優化問題往往不是凸規劃問題。所以，採用常用的優化方法，求得的最優解往往是區域性最優解。凸規劃的可行域是凸集。
2.線性規劃問題：
2.1線性規劃的標準形式
線性規劃即目標函式和約束函式都是線性的約束最優化問題。線性規劃在理論和計算方法上都很成熟。他在工程管理和經濟管理中，應用都和廣泛。
它的解法在理論上和方法上都很成熟。雖然大多數工程設計是非線性的，但是也有採用線性逼近方法求解非線性問題的。此外，線性規劃方法還常被用作解決非線性問題的子問題的工具，如在可行方向法中可行方向的尋求就是採用線性規劃方法。
當然，對於真正的線性優化問題，線性規劃方法就更有用了。
線性規劃的標準形式：
n為線性規劃的維數，m為線性規劃的階數，一般m2.1.1一般形式化成標準形式的方法：
⑴ 如果目標函式為極大化，則可轉化為極小化，因為在同樣的約束條件下， max z與min（-z）有相同的最優解，故以後常限於討論極小化的情況。
⑵ 在約束條件中，如果有不等式約束：
則可加上新的變數，把他們全變為等式約束，即
如果有不等式約束
則可以減去新的變數，把他們全部變為等是約束，即
以上這些引進來的新變數叫做鬆弛變數，鬆弛變數並不出現在目標函式中，也不影響問題的解。因此可把所有的約束條件化為統一的等式形式。
⑶ 當在某些問題中，實際情況並不要求某一變數為非負時，可另，其中，，並將其帶入目標函式和約束方程中去。
2.1.2線性規劃的幾個基本概念
⑴ 可行解凡同時滿足標準形式中目標函式和約束條件的任何乙個解，稱為線性問題的可行解。所有可行解的集合稱為可行域。
⑵ 基本解另標準形式中某（n-m）個變數等於零，如果剩餘的m個變數構成的m個線性方程有唯一的解，則稱由此得到的n個變數的解為基本解。
⑶ 基本可行解凡滿足非負條件的基本解為基本可行解，即既是基本解又是可行解。
⑷ 最優解滿足目標函式的可行解是線性規劃的最優解（即目標函式達到最小值的可行解叫最優解）。當乙個線性規劃的值無窮大時，則稱這樣的線性規劃是無界的。
⑸基本變數和非基本變數基本可行解中大於零的分量稱為基本變數，其餘變數稱為非基本變數。基本變數和非基本變數是相對於基本可行解來說的。
⑹ 基向量與基基本變數所對應的係數稱為基向量。
線性規劃有如下兩個基本性質：
⑴ 線性規劃可行解的集合構成乙個凸集，且這個凸集是凸多面體。它的每乙個定點對應乙個基本可行解。
⑵ 線性規劃的最優解如果存在，必然在凸集的某個頂點上達到。
2.2解線性規劃的單純形法：
求解思路：單純形法是從乙個初始基本可行解出發，尋找使目標函式有較大下降的乙個新的基本可行解代替原來的基本可行解，如此完成乙個迭代。經過判斷，如果沒達到最優點，則繼續迭代下去。
基本可行解的個數是有限的，所以經過有限次迭代，一定能達到最優解。
採用單純形法求解線性規劃，主要解決以下三個問題：
⑴ 如何確定基本可行解；
⑵ 如何由乙個基本可行解迭代出另乙個基本可行解，並使目函式值獲得較大的下降方向；
⑶如何判斷乙個基本可行解是否為最優解。
3. 無約束優化方法
無約束優化問題的一般數學表示式為
求解這類問題的方法，稱為無約束優化方法。若為一元函式，求解這類為題的無約束優化方法稱為一維搜尋方法。求解優化問題的迭代演算法是按迭代格式
求解的，即從已知點出發，沿給定的方向搜尋，以得到目標函式沿方向的極小點，其實質是求的乙個最優步長因子使
和是已確定的，所以上述表示式所表達的問題就是以為設計變數的一維優化為題，因而一維搜尋方法是優化方法的基礎。
一維搜尋方法有：分數法、**分割法、二次插值法和三次插值法。多元函式的無約束優化方法，可按其確定搜尋方向所使用的資訊和方法的不同氛圍兩大類。
一類方法是需要利用函式的一階偏導數甚至是二階偏導數都早搜尋方向，如梯度法、牛頓法、變尺度法和共軛梯度法等。這種方法計算量大，但收斂較快，一般稱之為解析法。另一種方法是僅利用迭代點的函式值來構造搜尋方向，如座標輪換法、模式搜尋法、方向加速法和單純形法。
只需要計算函式值，無需求導，這類方法有突出的優越性，一般稱之為直接法。
3.1牛頓法
牛頓法基本思想：求的極小值時，先將它在點附近作泰勒展開，取二次近似函式值，再求出這個二次函式的極小點，並一該極小點作為原目標函式的極小點x的一次近似值；若此值不滿足精度要求，則可以此近似值作為下一次迭代的初始點，仿照上面的做法，求出二次近似值；照此方法迭代下去，直至所求出的近似極小點滿足精度要求為止。牛頓迭代法的公式是：
牛頓法所採用的搜尋方向為其中是海色矩陣，步長因子。
3.2 共軛方向法
共軛方向的概念是在研究二次函式
（3.1）
時提出的，就是首先以3.1式的二次函式為目標給出有關演算法，然後再推廣到一般的目標函式中去。
3.2.1 共軛方向的性質
共軛方向有如下三個性質：
性質1 若非零向量系是對共軛的，則這m個向量是線性無關的。
性質2 在n維空間中互相共軛的非零向量的個數不超過n。
性質3 從任意初始點出發，順次沿n個g的共軛方向進行一維搜尋，最多經過n次迭代就可以找到上式所表示的二次函式極小點，此性質表明這種迭代方法具有二次收斂性。
3.2.2 powell共軛方向法
powell法是一種求解無約束優化問題的較為有效的方法。其基本原理是：首先採用座標輪換法進行第一輪迭代，然後以第一輪迭代的最末乙個極小點和初始點，構成乙個新的方向，並以此新的方向作為最末乙個方向，而去掉第乙個方向，得到第二輪迭代的n個方向。
仿此進行下去，直至求得問題的極小值。
最優化理論與方法
課程報告 學生姓名 學號院系專業二 一二年十一月十日 最優化方法是近幾十年形成的，它主要運用數學方法研究各種系統的優化途徑及方案，為決策者提供科學決策的依據。最優化方法的主要研究物件是各種管理問題及其生產經營活動。最優化方法的目的在於針對所研究的系統，求得乙個合理運用人力 物力和財力的最佳方案，發揮...
最優化計算方法
考試時間 120 分鐘 號試題班級學號姓名 一 20分 解釋下列概念 1 凸集，凸規劃 2 線性規劃的基和基本解 3 無約束優化演算法的下降搜尋方向，舉出兩種搜尋方向 4 約束最優化問題的可行解集合或容許解集合 5 共軛方向。二 10分 解答下列問題 1 判斷函式為凸函式或凹函式或嚴格凸函式或嚴格凹...
最優化方法習題一
習題一一 考慮二次函式f x 1 寫出它的矩陣 向量形式 f x 2 矩陣q是不是奇異的?3 證明 f x 是正定的 4 f x 是凸的嗎?5 寫出f x 在點 處的支撐超平面 即切平面 方程解 1 f x 其中 x q b 2 因為q 所以 q 8 0 即可知q是非奇異的3 因為 2 0,8 0 ...