最優(yōu)化方法教案

1、第一章 最優(yōu)化問題與數(shù)學預備知識最優(yōu)化分支：線性規(guī)劃，整數(shù)規(guī)劃，幾何規(guī)劃，非線性規(guī)劃，動態(tài)規(guī)劃。又稱規(guī)劃論。應用最優(yōu)化方法解決問題時一般有以下幾個特點：1. 實用性強2. 采用定量分析的科學手段3. 計算量大，必須借助于計算機4. 理論涉及面廣應用領域：工業(yè)，農業(yè)，交通運輸，能源開發(fā)，經濟計劃，企業(yè)管理，軍事作戰(zhàn)。§1.1 最優(yōu)化問題實例最優(yōu)化問題：追求最優(yōu)目標的數(shù)學問題。經典最優(yōu)化理論：（1） 無約束極值問題： （或）其中，是定義在n維空間上的可微函數(shù)。解法（求極值點）：求駐點，即滿足并驗證這些駐點是否極值點。（2） 約束極值問題：s.t. 解法：采用Lagrange乘子法，即將問

2、題轉化為求Lagrange函數(shù)的無約束極值問題。近代最優(yōu)化理論的實例：例1 (生產計劃問題) 設某工廠有3種資源B1，B2，B3，數(shù)量各為b1，b2，b3，要生產10種產品A1，A10 。每生產一個單位的Aj需要消耗Bi的量為aij，根據(jù)合同規(guī)定，產品Aj的量不少于dj，再設Aj的單價為cj 。問如何安排生產計劃，才能既完成合同，又使總收入最多？（線性規(guī)劃問題）數(shù)學模型：設Aj的計劃產量為，z為總收入。目標函數(shù)：約束條件： 線性規(guī)劃問題通常采用單純形法來求解。例2 (工廠設址問題) 要在m個不同地點計劃修建m個規(guī)模不完全相同的工廠，他們的生產能力分別是（為簡便起見，假設生產同一種產品），第i個

3、工廠的建設費用。又有n個零售商店銷售這種產品，對這種產品的需求量分別為，從第i個工廠運送一個單位產品到第j個零售商店的運費為cij。試決定應修建哪個工廠，使得既滿足零售商店的需求，又使建設工廠和運輸?shù)目傎M用最小。（混合整數(shù)規(guī)劃問題）數(shù)學模型： 設第i個工廠運往第j個零售商店的產品數(shù)量為xij（i=1，m；j=1，n），且目標函數(shù)：約束條件：整數(shù)規(guī)劃問題通常可用分枝定界法或割平面法來求解。例3 (投資計劃問題) 假設某一個生產部門在一段時間內可用于投資的總金額為億元，可供選擇的項目總共有n個，分別記為1，2，n。并且已知對第j個項目的投資總數(shù)為億元，而收益額總數(shù)為億元。問如何使用資金億元，才能使

4、單位投資獲得的收益最大。（非線性規(guī)劃問題）數(shù)學模型：設目標函數(shù)：約束條件： 非線性規(guī)劃問題的求解方法很多，是本課的重點。動態(tài)規(guī)劃是解決“多階段決策過程”的最優(yōu)化問題的一種方法，基于“Bellman最優(yōu)性原理”，例如：資源分配問題，生產與存儲問題。例4 (多參數(shù)曲線擬合問題)已知熱敏電阻依賴于溫度的函數(shù)關系為 （*）其中，是待定的參數(shù)，通過實驗測得和的15組數(shù)據(jù)列表如下，如何確定參數(shù)？i12345678505560657075808534.7828.6123.6519.6316.3713.7211.549.744i910111213141590951001051101151208.2617.03

5、6.0055.1474.4273.823.307建立數(shù)學模型：測量點與曲線對應的點產生“偏差”，即得如下無約束最優(yōu)化問題：通常采用最小二乘法。§1.2 最優(yōu)化問題的數(shù)學模型一、 最優(yōu)化問題的數(shù)學模型1. 定義1：設向量.若，則記或；若，則記或。2一般模型： ， （1）s.t. 其中，；，是關于變量的實值連續(xù)函數(shù)，一般可假定它們具有二階連續(xù)偏導數(shù)。3向量模型： ， （1）s.t. 其中，稱為目標函數(shù)； ，。，稱為約束函數(shù)；滿足約束條件（2），（3）的點稱為容許解或容許點（或可行解）；容許解的全體稱為容許域（或可行域），記為R；滿足（1）的容許點稱為最優(yōu)點或最優(yōu)解（或極?。ù螅c），記為

6、；稱為最優(yōu)值；不帶約束的問題稱為無約束問題，帶約束的問題稱為約束問題；若目標函數(shù)，約束函數(shù)，都是線性函數(shù)，則稱為線性規(guī)劃；若其中存在非線性函數(shù)，則稱為非線性規(guī)劃；若變量只取整數(shù)，稱為整數(shù)規(guī)劃；若變量只取0，1，稱為01規(guī)劃。注：因，則最優(yōu)化問題一般可寫成二、 最優(yōu)化問題的分類§1.3 二維問題的圖解法例1. 解：1. 由全部約束條件作圖，求出可行域R：凸多邊形OABC2. 作出一條目標函數(shù)的等值線：設，作該直線即為一條目標函數(shù)的等值線，并確定在可行域內，這條等值線向哪個方向平移可使值增大。3. 平移目標函數(shù)等值線，做圖求解最優(yōu)點，再算出最優(yōu)值。頂點是最優(yōu)點，即最優(yōu)解，最優(yōu)值。分析：

7、線性規(guī)劃問題解的幾種情況（1） 有唯一最優(yōu)解（上例）；（2） 有無窮多組最優(yōu)解：目標函數(shù)改為（3） 無可行解：增加約束，則。（4） 無有限最優(yōu)解（無界解）：例 結論：（1）線性規(guī)劃問題的可行域為凸集，特殊情況下為無界域或空集。（2）線性規(guī)劃問題若有最優(yōu)解，一定可在其可行域的頂點上得到。例2. 解：目標函數(shù)等值線：C為最優(yōu)點，得定義2：在三維及三維以上的空間中，使目標函數(shù)取同一常數(shù)的點集稱為等值面。§1.4 預備知識（一） 線性代數(shù)一、 n維向量空間1. 向量的內積：設，則內積為2. 向量的范數(shù)（或長度或模）：設，若實數(shù)具有以下性質：（1）當且僅當時；（2）；（3）.則稱為上的向量的范

8、數(shù)，簡記為。規(guī)定了向量范數(shù)的線性空間稱為線性賦范空間,記為.3. 常見的向量范數(shù)向量的范數(shù)：，三個重要的向量范數(shù)：，注：若無特殊說明，本書中的指的是。4. 間的距離：5. 與正交：若非零向量組，的向量兩兩正交，稱它們是正交向量組。6. 標準正交基：，是n個正交的單位向量，即二、 特征值和特征向量定義：設為n階方陣，存在數(shù)和非零向量，使，則稱為矩陣的特征值，非零向量為矩陣屬于特征值的特征向量。三、 正定矩陣定義：設為n階實對稱方陣，若對任意非零向量，均有，則稱為正定二次型，為正定矩陣，記。；若，半正定二次型，為半正定矩陣，記。類似有負定（半負定）二次型，負定（半負定）矩陣的概念。性質：實對稱方陣

9、為正定矩陣（負）的特征值均為正（負）的各階順序主子式均為正（奇數(shù)階為負，偶數(shù)階為正）實對稱方陣為半正定矩陣的特征值均非負的各階順序主子式均為非負（二） 數(shù)學分析一、 梯度和海色（Hesse）矩陣1. 多元函數(shù)的可微性可微定義：設，若存在維向量，對，總有 （1）則稱函數(shù)在點處可微。式（1）等價于 （2）其中，是的高階無窮小。 定理1：（可微的必要條件）若函數(shù)在點處可微，則在該點關于各個變量的偏導數(shù)存在，且2. 梯度（1）概念梯度：令則稱為n元函數(shù)在處的梯度（或記為）。又稱為關于的一階導數(shù)。注：式（2）等價于 （3）等值面：在三維和三維以上的空間中，使目標函數(shù)取同一數(shù)值的點集稱為等值面（曲面）。方

10、向導數(shù)：設在點處可微，向量，是方向上的單位向量，則極限稱為函數(shù)在點處沿方向的方向導數(shù)，記作。方向導數(shù)的幾何解釋：方向導數(shù)表示函數(shù)在點處沿方向的的變化率。函數(shù)的下降（上升）方向：設是連續(xù)函數(shù)，點，為一方向，若存在，對于，都有（）則稱方向是函數(shù)在點處的下降（上升）方向；結論1：若方向導數(shù)，則方向是在點處的下降方向；若方向導數(shù)，則方向是在點處的上升方向；（2）性質【性質1】：梯度為等值面在點處的切平面的法矢（向）量。【性質2】：梯度方向是函數(shù)具有最大變化率的方向。定理2：設在點處可微，則方向導數(shù)其中，是方向上的單位向量，為梯度與的夾角。結論2：1）與梯度方向成銳角的方向是上升方向；與梯度方向成鈍角的

11、方向是下降方向；2）梯度方向是函數(shù)值上升最快的方向，稱為最速上升方向；負梯度方向是函數(shù)值下降最快的方向，稱為最速下降方向。（3）幾種特殊函數(shù)的梯度公式（1），為常數(shù)；（2），其中；（3）；（4）若是對稱方陣，則.例3. 泰勒（Taylor）公式與Hesse矩陣性質1：設具有一階連續(xù)偏導數(shù)，則 （*）其中，即介于與之間。性質2：設具有二階連續(xù)偏導數(shù)，則 （* ）其中為函數(shù)關于的二階導數(shù)，稱為的海色（Hesse）矩陣。結論1：當時，（即海色矩陣對稱）。注1：1) 設向量函數(shù)時，稱為向量函數(shù)在點處的導數(shù)（梯度）。2) 向量函數(shù)在點處可微是指所有分量都在點處可微。關于向量函數(shù)常見的梯度：（1

12、），；（2），；（3）（4）設，其中，則，例：（三） 極小點的判定條件（求）一、 基本概念1. 點的鄰域：2. 局部極小點：設. 若存在點和數(shù)，對 都有，則稱為在上的（非嚴格）局部極小點；若（），則稱為在上的嚴格局部極小點。3. 全局極小點：設. 若存在點，對于 都有，則稱為在上的（非嚴格）全局極小點；若（），則稱為在上的嚴格全局極小點。 性質：全局極小點必是局部極小點；但局部極小點不一定是全局極小點。類似有極大點的概念。因，本書主要給出極小問題。4. 駐點：設可微，若，則稱點為的駐點或臨界點。 二、 極值的條件定理1（一階必要條件）設具有一階連續(xù)偏導數(shù)，是的內點，若是的局部極小點，則定理2（

13、二階必要條件）設具有二階連續(xù)偏導數(shù)，若是的內點且為的局部極小點，則是半正定的，即對恒有例定理3（二階充分條件）設具有二階連續(xù)偏導數(shù)，為的內點，且，若正定，則為的嚴格局部極小點。（四）凸函數(shù)與凸規(guī)劃一、凸集1. 凸集的定義：一個n維向量空間的點集中任意兩點的連線仍屬于這個集合，即對，有則稱該點集為凸集。2. 凸集的性質：（1）凸集的交集仍是凸集；（2）數(shù)乘凸集仍是凸集；（3）凸集的和集仍是凸集特別規(guī)定，空集是凸集。3. 超平面：設且，則集合稱為中的超平面，稱為該超平面的法向量，即；（是凸集）半空間：集合稱為中的一個半空間。超球：。4. 凸組合：設為中的個點，若存在且，使得則稱為的凸組合。若均為正

14、，則稱為嚴格凸組合。5. 頂點（或極點）：設是凸集，若不能用內不同兩點和的凸組合表示，即，則稱為的頂點。二、凸函數(shù)1. 凸函數(shù)：設，是凸集，若對及，都有則稱為凸集上的凸函數(shù)；若則稱為凸集上的嚴格凸函數(shù)。類似有凹函數(shù)的定義。2.幾何意義：函數(shù)圖形上連接任意兩點的線段處處都在函數(shù)圖形的上方。3. 性質性質1：為凸集上的凸函數(shù)，則也為上的凸函數(shù)。性質2：兩個凸函數(shù)的和仍是凸函數(shù)。推論1：凸集上有限個凸函數(shù)的非負線性組合仍為上的凸函數(shù)。性質3：若為凸集上的凸函數(shù)，則對，的水平集是凸集。性質4：為凸集上的凹函數(shù)為凸集上的凸函數(shù)。4. 凸函數(shù)的充分必要條件定理1（一階條件）設可微，是凸集，則（1）為凸函數(shù)

15、對，恒有（2）為嚴格凸函數(shù)對，恒有定理2（二階條件）設具有二階連續(xù)偏導數(shù)，為開凸集，則 （1）在內為凸函數(shù)對，是半正定的；（2）若正定，則在內為嚴格凸函數(shù)。特殊地，元二次函數(shù)為（為對稱矩陣）；若正定，則稱為正定二次函數(shù)。性質：正定二次函數(shù)是嚴格凸函數(shù)。（因為）5. 凸函數(shù)的極值凸規(guī)劃問題：非空凸集上的凸函數(shù)的極小化問題。定理3 設為凸集上的凸函數(shù)，則（1）的任一局部極小點為全局極小點；（2）若可微，且存在，使，則為在上的全局極小點；（3）若為嚴格凸函數(shù)，且全局極小點存在，則必唯一?？紤]如下特殊的凸規(guī)劃問題：（1）對于正定二次函數(shù)，有，得唯一駐點為唯一的全局極小點。（2）考慮凸規(guī)劃問題：， (1

16、)s.t. 其中，為上的凹函數(shù)，為上的線性函數(shù)，為凸集，為上的凸函數(shù)。注：線性函數(shù)既可視為凸函數(shù)，又可視為凹函數(shù)。（3）二次規(guī)劃： s.t. 其中，半正定或正定。注：關于凸函數(shù)的極值的性質（即定理3）即是凸規(guī)劃問題的性質 （五）下降迭代算法1. 下降迭代算法的步驟（1）選擇一個初始點，令k：=0（2）檢驗是否最優(yōu)？若是，則停止迭代；若不是，則（3）確定一個下降方向：存在，對，使得（4）從點出發(fā)，沿方向進行直線搜索（一維搜索），即求步長使（5）計算，令k：=k+1，轉（2）2. 直線搜索及其性質（1）簡記： 表示從點出發(fā)，沿方向進行直線搜索，得到極小點。（2）定理：設目標函數(shù)具有一階連續(xù)偏導數(shù)，

17、若，則證明：（反正法）設，則1），此時是點的下降方向；2），此時是點的下降方向；與矛盾。3. 收斂速度定義1：設序列是線性賦范空間中的點列，若則稱序列收斂于，記為。定義2：設向量函數(shù)，若當時，總有，則稱在點連續(xù)；若在內每一點都連續(xù)，則稱在內連續(xù)。特別地，m=1時，為數(shù)量函數(shù)，則定義3：設序列收斂于，若存在與無關的數(shù)和，使得當從某個開始，都有則稱序列收斂的階為，或為階收斂。當，且時，稱線性收斂或一階收斂；當時，稱二階收斂；當時，稱超線性收斂。4. 計算終止準則計算終止準則根據(jù)相繼兩次迭代的結果a. 根據(jù)相繼兩次迭代的絕對誤差（不常用），b. 根據(jù)相繼兩次迭代的相對誤差，c. 根據(jù)目標函數(shù)梯度的模

18、足夠小為給定的足夠小的正數(shù)。以上準則統(tǒng)稱為Himmelblau計算終止準則，簡稱H終止準則。第二章 線性規(guī)劃§2.1 數(shù)學模型一、線性規(guī)劃的標準型1. 繁寫形式：s.t. 其中，（否則，等式兩端同乘以“-1”）。2. 縮寫形式：s.t. 3. 向量形式：s.t. 其中，。4. 矩陣形式：s.t. 其中，：約束條件的系數(shù)矩陣，一般地，；：限定向量，一般地，；：價值向量；：決策向量，；通常，為已知，未知。二、任一模型化為標準型1. 極大化目標函數(shù)：令，則問題轉化為2. 約束條件為不等式若約束為“”型，則“左端+松弛變量=右端”（松弛變量0）如：，引入松弛變量，化為若約束為“”型，則“左端

19、-剩余變量=右端”（剩余變量0）如：，引入剩余變量，化為3. 若存在無非負要求的變量（稱為自由變量）令，其中，代入目標函數(shù)及約束條件即可。4. 某變量有上、下界若，即，令，有。用代替即可。若，即，令，有。用代替即可。例：§2.2 線性規(guī)劃解的性質一、基本概念標準型（LP）： s.t. 可行解（容許解）：滿足約束（2）、（3）的解。最優(yōu)解：滿足（1）的容許解。基：設的秩為，若是中的階可逆矩陣，稱是線性規(guī)劃問題（LP）的一個基。 若基是單位矩陣稱為標準基?；蛄浚夯械囊涣校ǎ┘礊橐粋€基向量。（共個）非基向量：基之外的一列（）即為一個非基向量。（共個）基變量：與基向量相應的變量。（共個）

20、非基變量：與非基向量相應的變量。（共個）基本解：令所有非基變量為0，求出的滿足約束（2）的解。基本容許解：滿足約束（3）的基本解。最優(yōu)基本容許解：滿足約束（1）的基本容許解。容許基：若是基，且存在關于的基本容許解，稱是容許基。 若容許基是單位矩陣稱為標準容許基。非容許基：退化的基本解：若基本解中有基變量為0的基本解。退化的基本容許解：退化的最優(yōu)基本容許解：二、線性規(guī)劃問題的基本定理定理1 若線性規(guī)劃問題存在容許域，則其容許域是凸集（也是凸多面體）。定理2 線性規(guī)劃問題的基本容許解對應于容許域的頂點。定理3 若線性規(guī)劃問題存在有限最優(yōu)解，則其目標函數(shù)最優(yōu)值一定可以在容許域的頂點達到。§

21、2.3 單純形法一、單純形法原理單純形法的基本思路：根據(jù)問題的標準型，從容許域的一個基本容許解（一個頂點）開始，轉移到另一個基本容許解（頂點），并且使目標函數(shù)值逐步下降；當目標函數(shù)達到最小值時，問題就得到了最優(yōu)解。二、單純形法的步驟（以“大M法”為例）數(shù)學描述例（大M法）：s.t. 1. 構造初始容許基初始容許基是一個單位矩陣，它相應的基本解是容許的，即標準容許基。1º引入附加變量，把數(shù)學模型化為標準型。2º若約束條件中附加變量系數(shù)為“-1”，或原約束即為等式，則一般須引入人工變量。3º目標函數(shù)中，附加變量系數(shù)為0，而人工變量系數(shù)為M（很大的正數(shù)）。人工變量系數(shù)為

22、大M：只要人工變量>0，使前后約束條件不等價，但由于目標函數(shù)的修改，同時也使所求的目標函數(shù)最小值是一個很大的數(shù)，也是對“篡改”約束條件的一種懲罰，因此，M叫做罰因子，大M法也叫做罰函數(shù)法。若對極大化問題，目標函數(shù)中人工變量系數(shù)為（-M）。得到如下標準型：s.t. 其中，表示基變量；表示非基變量。2. 求出一個基本容許解1º用非基變量表示基變量和目標函數(shù)。用非基變量表示基變量，即有用非基變量表示目標函數(shù)，即其中，而稱為非基變量的檢驗數(shù)。上式中，規(guī)定各基變量的檢驗數(shù)為0。其中，是基變量的價值系數(shù)，隨基的改變而改變。2º求出一個基本容許解及相應的目標函數(shù)值。令非基變量=0即

23、得初始基本容許解：，初始目標函數(shù)值：3. 最優(yōu)性檢驗1º檢驗數(shù)：目標函數(shù)式中，各非基變量的系數(shù)，即稱為各非基變量的檢驗數(shù)。2º最優(yōu)解判別定理：若在極小化問題中，對于某個基本容許解，所有檢驗數(shù)，且人工變量為0，則該基本容許解是最優(yōu)解。3º無窮多最優(yōu)解判別定理：若在極小化問題中，對于某個基本容許解，所有檢驗數(shù)，又存在某個非基變量的檢驗數(shù)為0，且人工變量為0，則該線性規(guī)劃問題有無窮多最優(yōu)解。4º無容許解判別定理：若在極小化問題中，對于某個基本容許解，所有檢驗數(shù)，但人工變量不為0，則該線性規(guī)劃問題無容許解。4. 基變換1º基本容許解的改進定理：已知一個非退化的基本容許解具有目標函數(shù)值，設某一個非基變量，其，則存在一個可行解具有目標函數(shù)