最優(yōu)化理論算法及工程應用課件

最優(yōu)化理論算法及工程應用最優(yōu)化理論算法及工程應用第一章預備知識最優(yōu)化問題01方向?qū)?shù)與極值問題0304泰勒級數(shù)問題02凸集、凸函數(shù)與凸優(yōu)化問題05算法概述第一章預備知識最優(yōu)化問題01方向?qū)?shù)與極值問題0304泰1.最優(yōu)化問題最優(yōu)化定義:最優(yōu)化是從所有可能方案中選擇最合理方案以達到最優(yōu)目標的一門學科。最優(yōu)化問題：尋求某些變量的取值使其符合某些限制條件，并使某個目標函數(shù)達到最大值或最小值的問題。最優(yōu)化方法包括:線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、多目標規(guī)劃、組合優(yōu)化等等。1.最優(yōu)化問題1.最優(yōu)化問題的發(fā)展

最優(yōu)化問題可以追溯至17世紀法國數(shù)學家拉格朗日關(guān)于一個函數(shù)在一組等式約束條件下的極值問題(求解多元函數(shù)極值的Lagrange乘數(shù)法)。19世紀柯西引入了最速下降法求解非線性規(guī)劃問題。2020世紀三、四十年代線性規(guī)劃(LP)理論的引入使得優(yōu)化理論的研究出現(xiàn)了重大進展。

1951年庫恩和塔克給出了非線性規(guī)劃(NLP)的最優(yōu)性條件。

隨著計算機技術(shù)的發(fā)展，各種最優(yōu)化算法應運而生。

1.最優(yōu)化問題的發(fā)展最優(yōu)化問題可以追溯至17世紀最優(yōu)化問題的數(shù)學模型一般形式其中（目標函數(shù)）（等式約束）（不等式約束）最優(yōu)化問題的數(shù)學模型一般形式其中（目標函數(shù)）（等式2.n元函數(shù)的Taylor公式一元函數(shù)的泰勒展開式：設函數(shù)在定義域內(nèi)連續(xù)可微，則有凸集、凸函數(shù)與凸優(yōu)化問題其中2.n元函數(shù)的Taylor公式一元函數(shù)的泰勒展開式：凸集、凸二元函數(shù)的Taylor展式：其中二元函數(shù)的Taylor展式：其中3.函數(shù)的方向?qū)?shù)與極值問題目標函數(shù)的等值面（線）對于簡單的問題，可用等值線或等值面來描述函數(shù)的變化趨勢，還可以直觀地給出極值點的位置。

1）目標函數(shù)的等值面，其數(shù)學表達式為f(x)=c。在這種線或面上所有點的函數(shù)值均相等，因此，這種線或面就稱為函數(shù)的等值線或等值面。當c取一系列不同的常數(shù)值時，可以得到一組形態(tài)相似的等值線或等值面，稱為函數(shù)的等值線簇或等值面簇。

3.函數(shù)的方向?qū)?shù)與極值問題目標函數(shù)的等值面（線）函數(shù)的方向?qū)?shù)與極值問題2）當n=2時，該點集是設計平面中的一條直線或曲線。例1：目標函數(shù)f(x)＝一60x1一120x2的等值線族。這是一組相互平行的直線，函數(shù)值沿箭頭所指方間逐漸下降。如圖所示。凸集、凸函數(shù)與凸優(yōu)化問題函數(shù)的方向?qū)?shù)與極值問題2）當n=2時，該點集是設計平面中的函數(shù)的方向?qū)?shù)與極值問題3）當n=3時，該點集是設計空間中的一個平面或曲面。例2函數(shù)的圖形(旋轉(zhuǎn)拋物面)，以及用平面f(X)＝c切割該拋物面所得交線在設計空間中的投影。如圖所示。4）當n大于3時，該點集是設計空間中的一個超曲面。函數(shù)的方向?qū)?shù)與極值問題3）當n=3時，該點集是設計空間中的函數(shù)的方向?qū)?shù)與極值問題方向?qū)?shù)討論函數(shù)在一點P沿某一方向的變化率問題。如果函數(shù)在點是可微分的，那末函數(shù)在該點沿任意方向L的方向?qū)?shù)都存在，且有

其中為x軸到方向L的轉(zhuǎn)角函數(shù)的方向?qū)?shù)與極值問題方向?qū)?shù)函數(shù)的方向?qū)?shù)與極值問題梯度函數(shù)在一點的梯度是這樣一個向量,它的方向與取得最大方向?qū)?shù)的方向一致,而它的模為方向?qū)?shù)的最大值。以的n個偏導數(shù)為分量的向量稱為在處的梯度，記為梯度也可以稱為函數(shù)關(guān)于向量的一階導數(shù)。函數(shù)的方向?qū)?shù)與極值問題梯度Hesse矩陣（其中）Hesse矩陣（其中）函數(shù)的方向?qū)?shù)與極值問題梯度與方向?qū)?shù)之間的關(guān)系(1)若，則P的方向是函數(shù)在點處的下降方向；(2)若，則P的方向是函數(shù)在點處的上升方向。方向?qū)?shù)的正負決定了函數(shù)值的升降，而升降的快慢就由它的絕對值大小決定．絕對值越大，升降的速度就越快函數(shù)的方向?qū)?shù)與極值問題梯度與方向?qū)?shù)之間的關(guān)系結(jié)論：(1)梯度方向是函數(shù)值的最速上升方向；(2)函數(shù)在與其梯度正交的方向上變化率為零；(3)函數(shù)在與其梯度成銳角的方向上是上升的，而在與其梯度成鈍角的方向上是下降的；(4)梯度反方向是函數(shù)值的最速下降方向．最優(yōu)化理論算法及工程應用ppt課件函數(shù)的方向?qū)?shù)與極值問題可行方向定義設

是規(guī)劃（NP）一個可行點,若非零向量

滿足：當

時，則稱為集處的一個可行方向（feasibledirection）。合

在點

若下降方向關(guān)于區(qū)域D可行，則稱為可行下降方向。函數(shù)的方向?qū)?shù)與極值問題可行方向定義設是規(guī)劃（NP）一函數(shù)的方向?qū)?shù)與極值問題無約束優(yōu)化極值問題

定理3.1(一階必要條件)在一次可微；(2)

為

的局部極值點，則（1）函數(shù)定理3.2.(充分條件)（3）Hesse矩陣（）。則為的嚴格局部極小值點（極大值）

在二次可微；（1）函數(shù)（2）函數(shù)的方向?qū)?shù)與極值問題無約束優(yōu)化極值問題定理3.1(一凸集、凸函數(shù)與凸優(yōu)化問題

凸組合：已知，任取k個點，如果存在常數(shù)，使得則稱為的凸組合。

凸集：設集合，如果中任意兩點的凸組合仍然屬于,則稱為凸集。凸集、凸函數(shù)與凸優(yōu)化問題

凸組合：已知，任取k個凸集、凸函數(shù)與凸優(yōu)化問題

設，任取如果有，有則稱為上的（嚴格）凸函數(shù)。凸函數(shù)凹函數(shù)凸集、凸函數(shù)與凸優(yōu)化問題

凸函數(shù)凹函數(shù)凸函數(shù)的判斷條件（1）一階導數(shù)向量法是凸集上的凸函數(shù)的充要條件是，有

(2)二階導數(shù)矩陣法設在凸集X上有二階連續(xù)偏導數(shù)，則是凸函數(shù)的充要條件是，有半正定。

凸函數(shù)的判斷條件凸規(guī)劃

設有規(guī)劃

設P為凸規(guī)劃，則：當為凸函數(shù)時，稱規(guī)劃P為凸規(guī)劃。（1）規(guī)劃P的可行解集為為凸集（2）規(guī)劃P的最優(yōu)解集為（3）規(guī)劃P的任何局部極小點都是全局極小值點（全局最優(yōu)解）為凸集凸規(guī)劃當為凸函