第一部分最優化方法基礎知識

最優化問題與數學預備知識凸性最優性條件第一章最優化問題與數學預備知識

實例與模型數學預備知識最優化的基本術語最優化的計算軟件第一章最優化問題與數學預備知識

最優化是一門應用十分廣泛的學科，它研究在有限種或無限種可行方案中挑選最優方案，構造尋求最優解的計算方法。達到最優目標的方案，稱為最優方案，搜索最優方案的方法，稱為最優化方法。這種方法的數學理論，稱為最優化理論。第一章最優化問題與數學預備知識最優化方法已廣泛應用于空間技術、軍事科學、電子工程、通訊工程、自動控制、系統識別、資源分配、計算數學、經濟管理等等領域。 最優化方法包括的內容很廣泛，如線性規劃、非線性規劃、整數規劃、動態規劃、多目標規劃、組合優化等等。本課程重點介紹非線性規劃。實例與模型實例1—配棉問題棉紡廠的主要原料是棉花，一般要占總成本的70%左右.棉花的品種、等級不同，價格也不同.因此，若采用品種好、等級高、價格貴的棉花來紡成一種質量要求一般的棉紗，勢必提高成本.所謂配棉問題就是要根據棉紗的質量指標，采用各種價格不同的棉花，按一定比例配制成紗，使其達到質量指標，又使總成本最低.實例1—配棉問題一個年紡紗能力15000錠的小廠在采用最優化方法配棉前，某一種產品32D純棉紗的棉花配比、質量指標及單價如下：有關部門對32D純棉紗規定的質量指標為棉結不多于70粒，品質指標不少于2900.試制定出該廠的最佳配棉方案以使總成本最低.原料品名單價(元/t)混合比棉結粒品質指標混棉單價(元/t)國棉1318400

256038002100國棉2297500356535002625國棉3276700408025002680平均合計1007031757405實例與模型實例與模型實例1—配棉問題分析：首先建立數學模型，然后采用相應的最優化方法求解.令分別為國棉131，229，327的棉花配比，則該問題的數學模型為實例與模型實例2—資金使用問題設有400萬元資金，要求4年內使用完，若在一年內使資金x萬元，則可得到效益x1/2萬元(效益不能再使用)，當年不用的資金可存入銀行，年利率為10%.試制訂出資金的使用規劃，以使4年內效益之總和最大.分析：令xi(i=1,2,3,4)分別表示第i年所使用的資金數.目標函數：約束條件：所受到的約束即為每年的使用額既不能為負數又不能超過當年資金擁有數，即實例與模型實例2—資金使用問題第一年：第二年：第三年：第四年：實例與模型實例2—資金使用問題則數學模型為實例與模型實例3—二曲線之間距離問題已知二曲線C1:

y1=2sin(x)與C2:y2=x2+2無交點，試求C1與C2之間的最短距離d.分析：令(x1,y1)為C1上的點,(x2,y2)為C2上的點.目標函數：約束條件：令y1=x3,y2=x4,則數學模型為實例與模型實例3—二曲線之間距離問題令y1=x3,y2=x4,則數學模型為實例與模型實例4—數據擬合問題在生產實踐和科技活動中，人們常常從實驗或測量中得到數據：xi=x1,x2,…,xm;yi=y1,y2,…,ym稱為原始數據，而由原始數據所確定的點列P(xi,yi),i=1,2,…,m,稱為原始點列.人們希望將這些數據或點列所蘊含的客觀規律用一個函數y=f(x)近似地表示出來.在一般情況下通常將f(x)取為代數多項式的形式，即取y=f(x)=a0+a1x1+a2x2+…+anxn.分析：如果測量數據不很準確(即含有較大的測量誤差)，但測得數據或點列較多(m>>n).在此條件下，人們往往采用擬合的辦法，即是去求一組系數(a0,a1,a2,…,an)使得下式取值最小實例與模型實例4—數據擬合問題則數學模型為實例與模型實例5—結構設計問題結構設計師的傳統工作在于力圖提出這樣的設計，該設計能夠安全地承受作設計的載荷，最有性的概念僅僅隱含在設計的標準規范和設計師的經驗之中.但是現在有了計算機的幫助，復雜的結構設計如航空空間結構的設計，對最優性的要求更明顯了.以兩桿對稱桁架的極小重量設計為例.考慮下圖所示的平面桁架，它由兩根鋼管構成，頂點為兩桿的共同端點，兩桿的另兩個支點固定.已知桁架的跨度為2L,承受負荷為2P,鋼管的厚度T,材料比重為ρ，縱向彈性模數為E,容許力為σ.要確定鋼管的平均直徑d和桁架高度h,使桁架重量最小.實例與模型實例5—結構設計問題d(b)鋼管剖面圖2L(a)桁架示意圖實例與模型分析：

這里決策變量為d和h,目標函數為實例5—結構設計問題(1)鋼管內壓應力不超過容許極限，即約束條件包括：(2)為保證在負荷2P的作用下鋼管不發生彎曲，要求壓應力不超過臨界應力σl，由材料力學知實例與模型實例5—結構設計問題(3)設計變量d和h有界.則數學模型為實例與模型實例6—政治區劃問題假設m個基本人口單元(如縣、社團等)按某種政治需要可以得到n個政區組合.設cj為選取政區j的費用或不可接受性的度量.問怎樣把這m個人口單元分成K個政區,使總的費用(或不可接受性)最小?分析：

令實例與模型實例6—政治區劃問題則數學模型為最優化問題的數學模型一般形式為：（目標函數）（等式約束）（不等式約束）其中實例與模型決策變量約束條件實例與模型無約束最優化問題UnconstrainedOptimizationProblem

根據數學模型中有無約束函數分為無約束的最優化問題和有約束的最優化問題。等式約束最優化問題OptimizationProblemwithEqualityConstraints實例與模型實例與模型不等式約束最優化問題OptimizationProblemwithInequalityConstraints實例與模型線性規劃：LP當目標函數和約束函數均為變量x的線性函數時，模型(1.1)-(1.3)稱為線性規劃問題.非線性規劃：NLP當目標函數和約束函數中至少有一個為變量x的線性函數時，模型(1.1)-(1.3)稱為非線性規劃問題.根據決策變量、目標函數和約束條件的不同，最優化還可分為二次規劃、整數規劃、動態規劃、網絡優化、非光滑優化、隨機規劃、幾何規劃、目標規劃、模糊規劃、全局最優化等若干分支.定義范數：

在維向量空間中，定義實函數使其滿足以下三個條件：在（１）對任意有當且僅當時（２）對任意及實數有（３）對任意有則稱函數為上的向量范數。數學預備知識---向量的范數(Norm)兩類比較常見的范數：

P-范數：其中最常用的是2-范數，即：范數：Euclid范數數學預備知識---向量的范數(Norm)性質(向量范數的等價性)：設||.||A和||.||B是定義于Rn中的兩種向量范數，則總存在正數c1和c2，使對一切x∈Rn,有數學預備知識---向量的范數(Norm)范數的兩個重要不等式：

(1)三角不等式：(2)Cauchy不等式：其中等式成立當且僅當數學預備知識---向量的范數(Norm)矩陣的譜半徑數學預備知識---矩陣的條件數(ConditionNumber)矩陣的奇異值矩陣的條件數稱A的最大奇異值與最小非零奇異值之商為A的條件數,記為κ(A),即性質1數學預備知識---矩陣的條件數(ConditionNumber)即正定矩陣的條件數等于它的最大特征值與最小特征值之商.性質2數學預備知識---矩陣的條件數(ConditionNumber)即滿秩矩陣的條件數等于它的最大奇異值與最小奇異值之商.病態：數學預備知識---矩陣的條件數(ConditionNumber)如果一個n階滿秩矩陣A的n個列向量之間存在著近似線性關系，則稱A為病態的.此時A的最小奇異值就會很小，相應的條件數就會很大.因此，條件數可以用來度量矩陣的病態程度.例相應地，A趨于奇異矩陣，也就是說，A的病態程度愈來愈來嚴重.可微、微分：數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式式(1.2.3)可以寫成下述等價形式梯度：數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式定理1.2.1方向導數(directionalderivative)：數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式方向導數處沿方向d的變化率.為函數f(x)在點數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式由于故當且僅當即負梯度方向是函數值下降最快的方向，也稱作最速下降方向.定理1.2.2數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式即梯度方向是函數值上升最快的方向.數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式Hesse矩陣數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式Jacobi矩陣數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式例1.2.1例1.2.2數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式例1.2.3例1.2.4數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式定理1.2.4二階Taylor展式一階Taylor展式數學預備知識---多元函數的梯度(Gradient)、Hesse矩陣及Taylor公式逼近函數線性逼近函數二次逼近函數最優化的基本術語定義１.3.1可行解滿足約束條(1.2)和(1.3)的x稱為可行解，也稱為可行點或容許點。定義１.3.2可行域全體可行解構成的集合稱為可行域，也稱為容許集，記為D,即：定義１.3.3全局最優解若：

對于一切則稱恒有為最優化問題的全局最優解。若：恒有則稱為最優化問題的嚴格全局最優解。最優化的基本術語GlobalMinimizer

定義１.3.4局部最優解

若：

存在的某鄰域使得對于一切恒有則稱為最優化問題的局部最優解，其中同樣有定義：嚴格局部最優解。最優化的基本術語LocalMinimizer

(2)局部最優解不一定是整體最優解。

(1)全局最優解一定是局部最優解；注意：

最優化的基本術語嚴格l.opt.嚴格g.opt.l.opt.最優化的基本術語

求解最優化問題，實際上是求可行域

D上的全局最優解。

但是，在一般情況下，整體最優解是很難求出的，最優化中的大多數方法是求局部最優解。最優化的基本術語迭代算法：選取一個初始可行點由這個初始可行點出發，依次產生一個可行點列：記為使得恰好是問題的一個最優解，或者該點列收斂到問題的一個最優解。下降算法：在迭代算法中一般要求：最優化的基本術語IterativeAlgorithm

DescentAlgorithm定義1.3.5下降方向：在點處，對于方向若存在實數使得任意的有：成立，則稱為函數在點處的一個下降方向。最優化的基本術語DescentDirection

當具有連續的一階偏導數，令由Taylor公式：當時，有所以（充分小時）是在處的一個下降方向。最優化的基本術語最優化的基本術語幾何意義：通常稱滿足：的方向為在處的下降方向。定義1.3.6可行方向：已知區域對于向量若存在實數使得任意的有：則稱為點處關于區域的可行方向。下降方向關于區域D可行，則稱為可行下降方向.最優化的基本術語FeasibleDirection

可行下降點列的產生在處求得一個方向（可行下降方向）在射線上求一點：使得其中稱為步長。最優化的基本術語最優化問題的算法的一般迭代格式給定初始點令步1確定處的可行下降方向步2

確定步長使得：步3令步4若滿足某種終止準則，則停止；否則令轉步1.

最優化的基本術語initialpoint

StepLength

最優化的基本術語搜索步長確定方法：稱為最優步長，且有...收斂性(Convergence) 如果一個算法只有當初始點充分接近最優解時，產生的點列才收斂，則稱該算法為具有局部收斂的算法。 如果對任意的初始點，由算法產生的點列都收斂，則稱該算法為具有全局收斂的算法。 具有全局收斂性的算法才有實用意義。但對算法的局部收斂性分析，在理論上是重要的，因為它是全局收斂性分析的基礎。最優化的基本術語收斂速度(RateofConvergence)定義1.8設序列收斂于而且：若則稱序列為線性收斂的，稱為收斂比；若則稱序列為超線性收斂的。最優化的基本術語定義1.9設序列收斂于若對則稱序列為有：p階收斂的。特別當：時稱為二階收斂的。最優化的基本術語收斂速度(RateofConvergence)終止準則(Termination)對于一種算法，應該有某種終止準則，當某次迭代滿足終止準則時，就停止迭代。常用的終止準則有：（１）或（２）或（３）其中是預先給定的。最優化的基本術語

評價一個算法的好壞，通常注意以下幾個方面：最優化的基本術語

通用性(Generality)

可求解問題的廣度，越大越好.可靠性(Reliability)

指以合理的精度，求解設計的這個算法時，針對要解決那個問題的能力。