【正文】 的慢收斂性，又避免了牛頓法的計算量大和局部收性的缺點．（３）算法簡單，易于編程，需存儲空間小等優(yōu)點，是求解大規(guī)模問題的主要方法．共軛方向及其性質(zhì)定義 1: 設 是 中任一組非零向量， 如果：則稱 是關于 共軛的．注： 若 則是正交的，因此共軛是正交的推廣．定理 1: 設 為 階正定陣， 非零向量組關于 共軛， 則必線性無關．推論 1: 設 為 階正定陣， 非零向量組關于 共軛， 則向量構成的一組基．推論 2: 設 為 階正定陣， 非零向量組關于 共軛， 若向量 與關于 共軛， 則求 的極小點的方法共軛方向法算法Step1: 給出計算 和初始下降方向Step2: 如果 停止迭代．Step3: 計算 使得Step4: 采用某種共軛方向法計算 使得：Step5: 令 轉(zhuǎn) Step2.共軛方向法基本定理定義 2: 設 維向量組 線性無關，向量集合為 與 生成的 維超平面．引理 1: 設 是連續(xù)可微的嚴格凸函數(shù)，維向量組 線性無關，則： 是 在 上唯一極小點的充要條件是：定理 2: 設 為 階正定陣， 向量組關于 共軛， 對正定二次函數(shù)由任意 開始， 依次進行 次精確線搜索：則：（１）（２） 是 在 上的極小點．推論 : 當 時， 為正定二次函數(shù)在上的極小點．共軛梯度法記：左乘 并使 得：（ HestenesStiefel公式）?。骸?是一種特殊的共軛方向法共軛梯度法基本性質(zhì)定理 3: 對于正定二次函數(shù)， 采用精確線搜索的共軛梯度法在 步后終止， 且對成立下列關系式：（共軛性）（正交性）（下降條件）系數(shù)的其他形式（１） FR公式（ 1964）（ 2） PRP公式（ 1969）FR共軛梯度法算法Step1: 給出Step2: 如果 停．Step5: 轉(zhuǎn) Step2.計算Step4:Step3: 由精確線搜索求計算例 4： 用 FR共軛梯度法求解：解： 化成 形式(1)(2)例 5： 用 FR共軛梯度法求解：解： 化成 形式(1)(2)注意： FR方法中初始搜索方向必須取最速下降方向，才滿足二次終止性。FR共軛梯度法收斂定理定理 4:假定 在有界水平集上連續(xù)可微， 且有下界， 那么采用精確線搜索下的FR共軛梯度法產(chǎn)生的點列 至少有一個聚點是駐點，即：(1) 當 是有窮點列時， 其最后一個點是的駐點．(2)當 是無窮點列時， 它必有聚點， 且任一聚點都是 的駐點．再開始 FR共軛梯度法算法Step1: 給出Step2: 計算 如果 停，Step4:否則Step3: 由精確線搜索求 并令：計算 若令 轉(zhuǎn) Step2。如果 停 .Step5: 若 令 轉(zhuǎn) step2.Step6: 計算Step7: 如果 令 轉(zhuǎn) step2,否則 轉(zhuǎn) step3.作　業(yè)用 FR共軛梯度法求解：多維約束最優(yōu)化方法n 懲罰函數(shù)法 SUMT:序列無約束極小化方法 (Sequential Unconstrained Minimization Technique) n 乘子法外點法（二次罰函數(shù)方法） 內(nèi)點法（內(nèi)點障礙罰函數(shù)法） 罰函數(shù)法基本思想設法將約束問題求解轉(zhuǎn)化為無約束問題求解．具體說： 根據(jù)約束的特點，構造某種懲罰函數(shù)，然后把它加到目標函數(shù)中去，將約束問題的求解化為一系列無約束問題的求解．　　懲罰策略 ： 企圖違反約束的迭代點給予很大的　　目標函數(shù)值． 迫使一系列無約束問題的極小點或者無限地靠近可行域，或者一直保持在可行域內(nèi)移動，直到收斂到極小點．外罰函數(shù)法（外點法）引例： 求解等式約束問題 :解:圖解法求出最優(yōu)解構造：但是 性態(tài)極壞， 無法用有效的無約束優(yōu)化算法求解．設想構造：其中 是很大的正數(shù)．求解此無約束問題得：當 時， 有：等式約束問題構造：其中 為參數(shù)，稱為罰因子．分析：當 不是可行解時， 越大，懲罰越重． 因此當 充分大時， 應充分小．即 的極小點應充分逼近可行域， 進而逼近 (1)的最優(yōu)解．不等式約束問題構造：分析：當 不是可行解時， 越大，懲罰越重． 因此當 充分大時， 應充分?。?的極小點應充分逼近可行域， 進而逼近 (2)的最優(yōu)解．一般約束問題構造：其中：例 1： 用外罰函數(shù)法求解：解：即：因此：令：得：最優(yōu)值：當 時：注： (1) 往往不滿足約束條件， 都是從可行域外部趨向于 的． 因此叫外罰函數(shù)法．(2)通過求解一系列無約束最優(yōu)化問題來求解約束最優(yōu)化問題的方法， 又稱為序列無約束極小化技術 ,又稱 SUMT外點法．外罰函數(shù)法算法步驟Step1: 給出 (可是不可行點 )，罰因子 放大系數(shù)Step2:以 為初始點求無約束問題：得Step3: 若 則 停； 否則轉(zhuǎn) step4Step4: 令 轉(zhuǎn) step2.例 2： 用 SUMT外點法求解：取求解迭代過程見下表：１ (,) ２ 1 (,) ３ 10 (,) ４ 100 (,) 收斂性分析引理 1： 對于由 SUMT外點法產(chǎn)生的點列則有：設收斂性分析定理 1： 設約束問題 (3)和無約束問題 (4)的整體最優(yōu)解為 和 對正數(shù)序列且 則由 SUMT外點法產(chǎn)生的點列 的任何聚點 必是 (3)的整體最優(yōu)解．證： 不妨設因為 和 分別為 (3)和 (4)的整體最優(yōu)解，且 所以有：為單調(diào)有界序列， 設其極限為亦為單調(diào)有界序列， 設其極限為且 連續(xù)； 即 為可行解為最優(yōu)解；連續(xù)；即 為 (3)的整體最優(yōu)解．外罰函數(shù)法評價(1) 如果有了求解無約束問題的好算法，利用外罰函數(shù)法求解約束問題很方便．(2)每個近似解 往往不是可行解，這是某些實際問題所無法接受的． 內(nèi)罰函數(shù)法可以解決．(3)由收斂性定理 取越大越好， 而 越大將造成增廣目標函數(shù) 的 Hesse陣條件數(shù)越大，趨于病態(tài)，給無約束問題求解增加很大困難，甚至無法求解．乘子法可解決這個問題．內(nèi)罰函數(shù)法懲罰策略： 在可行域的邊界上筑起一道很高的“圍墻 ”，當?shù)c靠近邊界時，目標函數(shù)值陡然增大，以示懲罰，阻止迭代點穿越邊界，這樣就可以把最優(yōu)解 “擋 ”在可行域內(nèi)了．注： 懲罰策略只適合于不等式約束問題，并且要求可行域的內(nèi)點集非空．不等式約束問題構造：其中： 或分析： 為可行域的內(nèi)點時， 為有限正數(shù)，幾乎不受懲罰； 接近邊界時， 趨于無窮大，施以很重的懲罰； 迫使極小點落在可行域內(nèi)，最終逼近極小點．例 3： 用內(nèi)罰函數(shù)法求解：解：令：所以當 時，注： 一般 最優(yōu)解很難用解析法求出，需采用序列無約束最優(yōu)化方法．內(nèi)罰函數(shù)法算法Step1: 給出 (要求是可行點 )，罰因子 縮小系數(shù)Step2: 以 為初始點求無約束問題：得Step3: 若 則 停； 否則轉(zhuǎn) step4Step4: 令 轉(zhuǎn) step2.例 4： 用 SUMT內(nèi)點法求解：取迭代結果見下表：１ 10 (,) ２ 1 (,) ３ (,) ４ (,) ５ (,) 收斂性分析引理 2： 對于由 SUMT內(nèi)點法產(chǎn)生的點列總有：定理 2： 設可行域 的內(nèi)點集非空， 在 上存在極小點 對嚴格單減正數(shù)列且 則由 SUMT外點法產(chǎn)生的點列的任何聚點 是約束問題 (2)的最優(yōu)解．證： 由于由引理 2知 單調(diào)減少且下有界，于是它有極限，記作 即：若能證明： 則可得：再由 的連續(xù)性，可得：即 是 (2)的最優(yōu)解．再證：由 的連續(xù)性知， 對于任意小的正數(shù) 存在取滿足 的 使得：由 知， 對于同一個 存在 當 時又因為乘子法引例： 求解等式約束問題 :解: 最優(yōu)解分析：對于任何 關于 的極小點是不存在的．正因為如此，才引進外罰函數(shù)法的．問題： 能否找到某個 使 恰好是的無約束極小呢？回答是否定的．設想： 能否在不改變最優(yōu)解的前提下， 以某個在最優(yōu)解 處梯度為零的函數(shù)來取代 呢？啟發(fā)： (增廣 Lagrange函數(shù))通過求解增廣 Lagrange函數(shù)的序列無約束問題來獲得原約束問題的解．等式約束問題的乘子法其中 和二階連續(xù)可微．設 為 Lagrange乘子向量， 則對應 Lagrange 函數(shù)為：設 是 的極小點， 是相應的乘子向量 ．(1)可等價為：啟發(fā)： 采用外罰函數(shù)法．構造：我們將證明： 適當大時， 是 極小點．但 是未知的， 在求 的同時， 采用迭代法求出這是乘子法的基本思想．定理３： 設 與 滿足 為問題 (1)的嚴格局部極小點的二階充分條件， 則存在 使對所有為 的嚴格局部極小點；反之， 若 且 對某個 是無約束問題(5)的局部極小點， 則 是約束問題 (1)的局部極小點 .算法構造采用迭代法求點列 使設已有 和 則由一階最優(yōu)性條件有：要求 和 且采用：或：例 5： 用乘子法求解：解： 增廣 Lagrange函數(shù)為：令：得：所以： 乘子迭代公式為：即：?。核裕涸O 對上式取極限有：得：得：也可不取特定值，直接對上式求極限等式約束的乘子法 (PH算法 )Step1: 給出Step2: 以 為初始點求無約束問題：得Step3: 若 則 停； 否則轉(zhuǎn) step4Step4: 當及放大系數(shù)轉(zhuǎn) step5。否則 ,轉(zhuǎn) step5。Step5: 令 轉(zhuǎn) step2.作　業(yè)(1)用外罰函數(shù)法求解：(2)用內(nèi)罰函數(shù)法求解：第四專題 動態(tài)規(guī)劃n 動態(tài)規(guī)劃（ Dynamic Programming，簡稱 DP） 解決多階段決策過程最優(yōu)化的一種有用的數(shù)學方法。n 動態(tài)規(guī)劃的產(chǎn)生 1951年，美國數(shù)學家貝爾曼（ ）等人，根據(jù)一類多階段決策問題的特點， 把多階段決策問題表示為一系列單階段問題， 即把一個 N變量問題作為一系列的 N個單變量問題而逐個加以解決，提出了解決這類問題的 “ 最優(yōu)化原理 ” ，并將其應用于很多實際問題的研究，從而建立了運籌學的一個分支 —— 動態(tài)規(guī)劃。 n 動態(tài)規(guī)劃的應用領域n 最優(yōu)路徑問題n 資源分配問題n 生產(chǎn)計劃和庫存問題n 投資問題n 裝載問題n 排序問題n 生產(chǎn)過程的最優(yōu)控制等 在處理某些優(yōu)化問題時，常比線性規(guī)劃或非線性規(guī)劃方法更有效。 動態(tài)規(guī)劃研究內(nèi)容n 動態(tài)規(guī)劃問題及相關概念和理論n 動態(tài)規(guī)劃的解法n 動態(tài)規(guī)劃的應用 動態(tài)規(guī)劃研究對象n 多階段決策問題 多階段決策過程 是指這樣一類特殊的活動過程，他們可以 按時間 （或空間） 順序分解成若干相互聯(lián)系的階段，在每個階段都要做出決策，全部過程的決策是一個決策序列 ，所以多階段決策過程也稱為 序貫決策過程 。 這種問題就稱為多階段決策問題。 動態(tài)規(guī)劃問題實例n 時間階段的例子 設備負荷分配問題 （書 P167例 ）n 空間階段的例子 最短路問題（書 P166例 ） 動態(tài)規(guī)劃法窮舉法A B階段 1 C D2 3 4 E F5 G6動態(tài)規(guī)劃問題的模型建立n 動態(tài)規(guī)劃方法的基本思想 將問題的過程分成幾個相互聯(lián)系的階段， 通過恰當?shù)倪x取變量（包括狀態(tài)變量及決策變量）并定義最優(yōu)值函數(shù) ， 從而把 一個大問題轉(zhuǎn)化成一組同類型的子問題 ， 從邊界條件開始，逐段遞推尋優(yōu)， 在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結果，最后 一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。 n 動態(tài)規(guī)劃問題的基本特征 問題具有 多階段決策 的特征；每一階段都有 相應的 “狀態(tài) ”與之對應；每一階段都面臨 一個決策 ，選擇不同的決策將會導致下一階段不同的狀態(tài)；每一階段的最優(yōu)解問題可以 遞歸地歸結 為下一階段各個可能狀態(tài)的最優(yōu)解問題，各子問題與原問題具有 完全相同 的結構。 動態(tài)規(guī)劃的基本概念n 階段 n 狀態(tài) n 決策 n 策略 n 狀態(tài)轉(zhuǎn)移方程 n 指標函數(shù)和最優(yōu)值函數(shù) n 最優(yōu)策略和最優(yōu)軌線 n 邊界條件 書 P170173動態(tài)規(guī)劃的基本理論n 最優(yōu)性原理 （貝爾曼最優(yōu)化原理） 無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構成最優(yōu)子策略。 也就是說，一個最優(yōu)策略的子策略也是最優(yōu)的。 n 基本方程（或泛函方程） 書 P174176逆序遞推 順序遞推