【正文】 Step1: 給出Step2: 計(jì)算 如果 停．Step3: 否則計(jì)算Step4: 令 轉(zhuǎn)步２ .并且求解方程得出例 1： 用牛頓法求解：解：牛頓法收斂定理定理 1: 設(shè) 二次連續(xù)可微， 是 的局部極小點(diǎn)， 正定． 假定 的海色陣滿足 Lipschitz條件，即存在使得對(duì)于所有 有：其中 是海色陣 的 元素． 則當(dāng)充分靠近 時(shí)， 對(duì)于一切 牛頓迭代有意義，迭代序列 收斂到 并且具有二階收斂速度．牛頓法優(yōu)點(diǎn)(1)(2) 對(duì)正定二次函數(shù)，迭代一次就可以得到極小點(diǎn)．如果 正定且初始點(diǎn)選取合適， 算法二階收斂．牛頓法缺點(diǎn)(1)(2)對(duì)多數(shù)問題算法不是整體收斂的．每次都需要計(jì)算 計(jì)算量大．(3) 每次都需要解方程組有時(shí)奇異或病態(tài)的， 無法確定或 不是下降方向．(4) 收斂到鞍點(diǎn)或極大點(diǎn)的可能性并不?。枘崤ｎD法算法Step1: 給出Step2: 計(jì)算 如果 停．Step3: 否則計(jì)算Step4: 沿并且求解方程得出進(jìn)行線搜索， 得出Step5: 令 轉(zhuǎn) Step2.阻尼牛頓法收斂定理定理 2: 設(shè) 二階連續(xù)可微， 又設(shè)對(duì)任意的存在常數(shù) 使得 在上滿足：則在精確線搜索條件下， 阻尼牛頓法產(chǎn)生的點(diǎn)列滿足：(1)當(dāng) 是有限點(diǎn)列時(shí)， 其最后一個(gè)點(diǎn)為的唯一極小點(diǎn)．(2)當(dāng) 是無限點(diǎn)列時(shí)， 收斂到 的唯一極小點(diǎn)．阻尼牛頓法收斂定理定理 3: 設(shè) 二階連續(xù)可微， 又設(shè)對(duì)任意的存在常數(shù) 使得 在上滿足：則在 Wolfe不精確線搜索條件下， 阻尼牛頓法產(chǎn)生的點(diǎn)列 滿足：且 收斂到 的唯一極小點(diǎn)．例 2： 用阻尼牛頓法求解：解：顯然 不是正定的， 但：于是，沿方向 進(jìn)行線搜索，得其極小點(diǎn) 從而迭代不能繼續(xù)下去．帶保護(hù)的牛頓法算法給出Step1: 若 為奇異的，轉(zhuǎn) Step8，否則，Step2: 令Step3: 若為奇異的，轉(zhuǎn) ，否則，則轉(zhuǎn) Step8，否則，Step4: 若 則轉(zhuǎn) Step9，否則，Step5: 沿方向 進(jìn)行線搜索， 求出并令Step6: 若 停；Step7: 令 轉(zhuǎn) Step1；Step8: 令 轉(zhuǎn) Step5；Step9: 令 轉(zhuǎn) Step5.例 3： 用帶保護(hù)的牛頓法求解：解：顯然 不是正定的， 但：于是，因?yàn)椋?故令，沿 進(jìn)行線搜索得：第二次迭代：而：使 故令沿 進(jìn)行線搜索， 得出于是 :此時(shí) :問題 1: 如何建立有效的算法？從二次模型到一般模型問題 2: 什么樣的算法有效呢？二次終止性 (經(jīng)過有限次迭代必達(dá)到極小點(diǎn)的性質(zhì)）共軛梯度法算法特點(diǎn)（１）建立在二次模型上，具有二次終止性．（２）有效的算法，克服了最速下降法的慢收斂性，又避免了牛頓法的計(jì)算量大和局部收性的缺點(diǎn)．（３）算法簡(jiǎ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方法中初始搜索方向必須取最速下降方向，才滿足二次終止性。Step5: 令 轉(zhuǎn) step2.作　業(yè)(1)用外罰函數(shù)法求解：(2)用內(nèi)罰函數(shù)法求解：第四專題 動(dòng)態(tài)規(guī)劃n 動(dòng)態(tài)規(guī)劃（ Dynamic Programming，簡(jiǎn)稱 DP） 解決多階段決策過程最優(yōu)化的一種有用的數(shù)學(xué)方法。 這種問題就稱為多階段決策問題。 也就是說，一個(gè)最優(yōu)策略的子策略也是最優(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)。 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ī)劃方法更有效。如果 停 .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)槿绱?，才引進(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à)為：?jiǎn)l(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ù)為：令：得：所以： 乘