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

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

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

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

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

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

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

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