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