最優化理論算法及工程應用第1頁，共26頁，2023年，2月20日，星期五第一章預備知識最優化問題01方向導數與極值問題0304泰勒級數問題02凸集、凸函數與凸優化問題05算法概述第2頁，共26頁，2023年，2月20日，星期五1.最優化問題最優化定義:最優化是從所有可能方案中選擇最合理方案以達到最優目標的一門學科。最優化問題：尋求某些變量的取值使其符合某些限制條件，并使某個目標函數達到最大值或最小值的問題。最優化方法包括:線性規劃、非線性規劃、整數規劃、動態規劃、多目標規劃、組合優化等等。第3頁，共26頁，2023年，2月20日，星期五1.最優化問題的發展

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

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

隨著計算機技術的發展，各種最優化算法應運而生。

第4頁，共26頁，2023年，2月20日，星期五最優化問題的數學模型一般形式其中（目標函數）（等式約束）（不等式約束）第5頁，共26頁，2023年，2月20日，星期五2.n元函數的Taylor公式一元函數的泰勒展開式：設函數在定義域內連續可微，則有凸集、凸函數與凸優化問題其中第6頁，共26頁，2023年，2月20日，星期五二元函數的Taylor展式：其中第7頁，共26頁，2023年，2月20日，星期五3.函數的方向導數與極值問題目標函數的等值面（線）對于簡單的問題，可用等值線或等值面來描述函數的變化趨勢，還可以直觀地給出極值點的位置。

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

第8頁，共26頁，2023年，2月20日，星期五函數的方向導數與極值問題2）當n=2時，該點集是設計平面中的一條直線或曲線。例1：目標函數f(x)＝一60x1一120x2的等值線族。這是一組相互平行的直線，函數值沿箭頭所指方間逐漸下降。如圖所示。凸集、凸函數與凸優化問題第9頁，共26頁，2023年，2月20日，星期五函數的方向導數與極值問題3）當n=3時，該點集是設計空間中的一個平面或曲面。例2函數的圖形(旋轉拋物面)，以及用平面f(X)＝c切割該拋物面所得交線在設計空間中的投影。如圖所示。4）當n大于3時，該點集是設計空間中的一個超曲面。第10頁，共26頁，2023年，2月20日，星期五函數的方向導數與極值問題方向導數討論函數在一點P沿某一方向的變化率問題。如果函數在點是可微分的，那末函數在該點沿任意方向L的方向導數都存在，且有

其中為x軸到方向L的轉角第11頁，共26頁，2023年，2月20日，星期五函數的方向導數與極值問題梯度函數在一點的梯度是這樣一個向量,它的方向與取得最大方向導數的方向一致,而它的模為方向導數的最大值。以的n個偏導數為分量的向量稱為在處的梯度，記為梯度也可以稱為函數關于向量的一階導數。第12頁，共26頁，2023年，2月20日，星期五Hesse矩陣（其中）第13頁，共26頁，2023年，2月20日，星期五函數的方向導數與極值問題梯度與方向導數之間的關系(1)若，則P的方向是函數在點處的下降方向；(2)若，則P的方向是函數在點處的上升方向。方向導數的正負決定了函數值的升降，而升降的快慢就由它的絕對值大小決定．絕對值越大，升降的速度就越快第14頁，共26頁，2023年，2月20日，星期五結論：(1)梯度方向是函數值的最速上升方向；(2)函數在與其梯度正交的方向上變化率為零；(3)函數在與其梯度成銳角的方向上是上升的，而在與其梯度成鈍角的方向上是下降的；(4)梯度反方向是函數值的最速下降方向．第15頁，共26頁，2023年，2月20日，星期五函數的方向導數與極值問題可行方向定義設

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

滿足：當

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

在點

若下降方向關于區域D可行，則稱為可行下降方向。第16頁，共26頁，2023年，2月20日，星期五函數的方向導數與極值問題無約束優化極值問題

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

為

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

在二次可微；（1）函數（2）第17頁，共26頁，2023年，2月20日，星期五凸集、凸函數與凸優化問題

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

凸集：設集合，如果中任意兩點的凸組合仍然屬于,則稱為凸集。第18頁，共26頁，2023年，2月20日，星期五凸集、凸函數與凸優化問題

設，任取如果有，有則稱為上的（嚴格）凸函數。凸函數凹函數第19頁，共26頁，2023年，2月20日，星期五凸函數的判斷條件（1）一階導數向量法是凸集上的凸函數的充要條件是，有

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

第20頁，共26頁，2023年，2月20日，星期五凸規劃

設有規劃

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