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

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

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

3、工廠的建設(shè)費用。又有n個零售商店銷售這種產(chǎn)品，對這種產(chǎn)品的需求量分別為，從第i個工廠運送一個單位產(chǎn)品到第j個零售商店的運費為cij。試決定應(yīng)修建哪個工廠，使得既滿足零售商店的需求，又使建設(shè)工廠和運輸?shù)目傎M用最小。（混合整數(shù)規(guī)劃問題）數(shù)學(xué)模型： 設(shè)第i個工廠運往第j個零售商店的產(chǎn)品數(shù)量為xij（i=1，m；j=1，n），且目標(biāo)函數(shù)：約束條件：整數(shù)規(guī)劃問題通?？捎梅种Χń绶ɑ蚋钇矫娣▉砬蠼?。例3 (投資計劃問題) 假設(shè)某一個生產(chǎn)部門在一段時間內(nèi)可用于投資的總金額為億元，可供選擇的項目總共有n個，分別記為1，2，n。并且已知對第j個項目的投資總數(shù)為億元，而收益額總數(shù)為億元。問如何使用資金億元，才能使

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

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

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

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

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

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

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

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

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

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

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

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

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

17、盾。3. 收斂速度定義1：設(shè)序列是線性賦范空間中的點列，若則稱序列收斂于，記為。定義2：設(shè)向量函數(shù)，若當(dāng)時，總有，則稱在點連續(xù)；若在內(nèi)每一點都連續(xù)，則稱在內(nèi)連續(xù)。特別地，m=1時，為數(shù)量函數(shù)，則定義3：設(shè)序列收斂于，若存在與無關(guān)的數(shù)和，使得當(dāng)從某個開始，都有則稱序列收斂的階為，或為階收斂。當(dāng)，且時，稱線性收斂或一階收斂；當(dāng)時，稱二階收斂；當(dāng)時，稱超線性收斂。4. 計算終止準(zhǔn)則計算終止準(zhǔn)則根據(jù)相繼兩次迭代的結(jié)果a. 根據(jù)相繼兩次迭代的絕對誤差（不常用），b. 根據(jù)相繼兩次迭代的相對誤差，c. 根據(jù)目標(biāo)函數(shù)梯度的模足夠小為給定的足夠小的正數(shù)。以上準(zhǔn)則統(tǒng)稱為Himmelblau計算終止準(zhǔn)則，簡稱H終

18、止準(zhǔn)則。第二章 線性規(guī)劃§2.1 數(shù)學(xué)模型一、線性規(guī)劃的標(biāo)準(zhǔn)型1. 繁寫形式：s.t. 其中，（否則，等式兩端同乘以“-1”）。2. 縮寫形式：s.t. 3. 向量形式：s.t. 其中，。4. 矩陣形式：s.t. 其中，：約束條件的系數(shù)矩陣，一般地，；：限定向量，一般地，；：價值向量；：決策向量，；通常，為已知，未知。二、任一模型化為標(biāo)準(zhǔn)型1. 極大化目標(biāo)函數(shù)：令，則問題轉(zhuǎn)化為2. 約束條件為不等式若約束為“”型，則“左端+松弛變量=右端”（松弛變量0）如：，引入松弛變量，化為若約束為“”型，則“左端-剩余變量=右端”（剩余變量0）如：，引入剩余弛變量，化為3. 若存在無非負(fù)要求的變

19、量（稱為自由變量）令，其中，代入目標(biāo)函數(shù)及約束條件即可。4. 某變量有上、下界若，即，令，有。用代替即可。若，即，令，有。用代替即可。例：§2.2 線性規(guī)劃解的性質(zhì)一、基本概念標(biāo)準(zhǔn)型（LP）： s.t. 可行解（容許解）：滿足約束（2）、（3）的解。最優(yōu)解：滿足（1）的容許解?；涸O(shè)的秩為，若是中的階可逆矩陣，稱是線性規(guī)劃問題（LP）的一個基?；蛄浚夯械囊涣校ǎ┘礊橐粋€基向量。（共個）非基向量：基之外的一列（）即為一個非基向量。（共個）基變量：與基向量相應(yīng)的變量。（共個）非基變量：與非基向量相應(yīng)的變量。（共個）基本解：令所有非基變量為0，求出的滿足約束（2）的解?；救菰S解：滿足

20、約束（3）的基本解。最優(yōu)基本容許解：滿足約束（1）的基本容許解。退化的基本解：若基本解中有基變量為0的基本解。退化的基本容許解：退化的最優(yōu)基本容許解：二、線性規(guī)劃問題的基本定理定理1 若線性規(guī)劃問題存在容許域，則其容許域是凸集。定理2 線性規(guī)劃問題的基本容許解對應(yīng)于容許域的頂點。定理3 若線性規(guī)劃問題存在有限最優(yōu)解，則其目標(biāo)函數(shù)最優(yōu)值一定可以在容許域的頂點達到。§2.3 單純形法一、單純形法原理單純形法的基本思路：根據(jù)問題的標(biāo)準(zhǔn)型，從容許域的一個基本容許解（一個頂點）開始，轉(zhuǎn)移到另一個基本容許解（頂點），并且使目標(biāo)函數(shù)值逐步下降；當(dāng)目標(biāo)函數(shù)達到最小值時，問題就得到了最優(yōu)解。二、單純形

21、法的步驟（以“大M法”為例）數(shù)學(xué)描述例（大M法）：s.t. 1. 構(gòu)造初始容許基初始容許基是一個單位矩陣，它相應(yīng)的基本解是容許的。1º引入附加變量，把數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。2º若約束條件中附加變量系數(shù)為“-1”，或原約束即為等式，則一般須引入人工變量。3º目標(biāo)函數(shù)中，附加變量系數(shù)為0，而人工變量系數(shù)為M（很大的正數(shù)）。人工變量系數(shù)為大M：只要人工變量>0，使前后約束條件不等價，但由于目標(biāo)函數(shù)的修改，同時也使所求的目標(biāo)函數(shù)最小值是一個很大的數(shù)，也是對“篡改”約束條件的一種懲罰，因此，M叫做罰因子，大M法也叫做罰函數(shù)法。若對極大化問題，目標(biāo)函數(shù)中人工變量系數(shù)為（-

22、M）。得到如下標(biāo)準(zhǔn)型：s.t. 其中，表示基變量；表示非基變量。2. 求出一個基本容許解1º用非基變量表示基變量和目標(biāo)函數(shù)。用非基變量表示基變量，即有用非基變量表示目標(biāo)函數(shù)，即其中，而稱為非基變量的檢驗數(shù)。上式中，規(guī)定各基變量的檢驗數(shù)為0。其中，是基變量的價值系數(shù)，隨基的改變而改變。2º求出一個基本容許解及相應(yīng)的目標(biāo)函數(shù)值。令非基變量=0即得初始基本容許解：，初始目標(biāo)函數(shù)值：3. 最優(yōu)性檢驗1º檢驗數(shù)：目標(biāo)函數(shù)式中，各非基變量的系數(shù)，即稱為各非基變量的檢驗數(shù)。2º最優(yōu)解判別定理：若在極小化問題中，對于某個基本容許解，所有檢驗數(shù)，且人工變量為0，則該基本容許解是最優(yōu)解。3º無窮多最優(yōu)解判別定理：若在極小化問題中，對于某個基本容許解，所有檢驗數(shù)，又存在某個非基變量的檢驗數(shù)為0，且人工變量為0，則該線性規(guī)劃問題有無窮多最優(yōu)解。4º無容許解判別定理：若在極小化問題中，對于某個基本容許解，所有檢驗數(shù)，