第九章經典最優(yōu)化方法

1、1第九章第九章經典最優(yōu)化方法經典最優(yōu)化方法9.1最優(yōu)化的基本概念最優(yōu)化的基本概念最優(yōu)化方法是一門古老而又年青的學科。這門學科的源頭可以追溯到17世紀法國數學家拉格朗日關于一個函數在一組等式約束條件下的極值問題（求解多元函數極值的Lagrange乘數法）。19世紀柯西引入了最速下降法求解非線性規(guī)劃問題。直到20世紀三、四十年代最優(yōu)化理論的研究才出現(xiàn)了重大進展，1939年前蘇聯(lián)的康托洛維奇提出了解決產品下料和運輸問題的線性規(guī)劃方法；1947

2、年美國的丹奇格提出了求解線性規(guī)劃的單純形法，極大地推動了線性規(guī)劃理論的發(fā)展。非線性規(guī)劃理論的開創(chuàng)性工作是在1951年由庫恩和塔克完成的，他們給出了非線性規(guī)劃的最優(yōu)性條件。隨著計算機技術的發(fā)展，各種最優(yōu)化算法應運而生。比較著名的有DFP和BFGS無約束變尺度法、HP廣義乘子法和WHP約束變尺度法。最優(yōu)化問題本質是一個求極值問題，幾乎所有類型的優(yōu)化問題都可概括為如下模型：給定一個集合（可行集）和該集合上的一個函數（目標函數），要計算此函數在

3、集合上的極值。通常，人們按照可行集的性質對優(yōu)化問題分類：如果可行集中的元素是有限的，則歸結為“組合優(yōu)化”或“網絡規(guī)劃”，如圖論中最短路、最小費用最大流等；如果可行集是有限維空間中的一個連續(xù)子集，則歸結為“線性或非線性規(guī)劃”；如果可行集中的元素是依賴時間的決策序列，則歸結為“動態(tài)規(guī)劃”；如果可行集是無窮維空間中的連續(xù)子集，則歸結為“最優(yōu)控制”。線性規(guī)劃與非線性規(guī)劃是最優(yōu)化方法中最基本、最重要的兩類問題。一般來說，各優(yōu)化分支有其相應的應用領

4、域。線性規(guī)劃、網絡規(guī)劃、動態(tài)規(guī)劃通常用于管理與決策科學；最優(yōu)控制常用于控制工程；非線性規(guī)劃更多地用于工程優(yōu)化設計。前面提到的算法是最優(yōu)化的基本方法，它們簡單易行，對于性態(tài)優(yōu)良的一般函數，優(yōu)化效果較好。但這些經典的方法是以傳統(tǒng)微積分為基礎的，不可避免地帶有某種局限性，主要表現(xiàn)為：①大多數傳統(tǒng)優(yōu)化方法僅能計算目標函數的局部最優(yōu)點，不能保證找到全局最優(yōu)解。對于多峰值函數，這些方法往往由于過分追求“下降”而陷于局部最優(yōu)解；②許多傳統(tǒng)優(yōu)化方法對目

5、標函數的光滑性、凹凸性等有較高的要求，對于離散型函數、隨機型函數基本上無能為力。3解：可將算子、理解為對向量函數的一階、二階導數，易得?2???bAXXf?????AXf??23、元函數的二階元函數的二階Tayl展式展式n一元函數的Tayl展式：????nnnRxnxfxxfxxfxfxxf??????????????!)(!2)()()()(0)(20000?其中??10)!1()(10)1(???????????nnnxnxxfR二

6、元函數的Tayl展式：)()()(000000yxfyyxxyxfyyxxf?????????????????????nnRyxfyyxxnyxfyyxx???????????????????????????????????)(!1)(!2100002?其中10)()!1(1001???????????????????????????yyxxfyyxxnRnn二元函數的二階Tayl展式：yyxfyxyxfxyxfyyxxf???????

7、??????)()()()(00000000????????????22002200200220022)()()()(!21Ryyxfyxyyxfxyyxyxfyxxyxfx?????????????????????????????若引入矩陣記號????0000XXXyxXyxXTT???????????????????????????????????????????????202020220202000)()()()()()()(yX