優(yōu)化原理與方法1

優(yōu)化原理與方法第1講主講人：劉國juliu@163.com1優(yōu)化原理與方法參考書：汪樹玉、劉國華等，系統(tǒng)分析（第五章優(yōu)化方法），浙江大學出版社；汪樹玉等，優(yōu)化原理、方法與工程應用，浙江大學出版社；甘應愛等，運籌學，清華大學出版社。期末考核方式：閉卷考試2§1基本知識優(yōu)化VS

優(yōu)選、方案比選

優(yōu)化理論：數(shù)學規(guī)劃、運籌學§1.1優(yōu)化問題的數(shù)學模型例1.1生產安排問題有色磚無色磚資源限制產品利潤300200機時2110人工3324顏料2083（一）設計變量設計變量x：需要通過優(yōu)化過程選定的基本參數(shù)。優(yōu)化的目的是尋找這些參數(shù)值的最優(yōu)組合。n個設計變量x

=[x1,x2,…xi,…,xn]T——n維問題優(yōu)化計算量隨著問題維數(shù)n的增加而顯著增加多項式算法又稱簡單算法非多項式算法又稱復雜算法一般的優(yōu)化算法屬于復雜算法維數(shù)災難xk代表第k個迭代點；xik

代表xk中的第i個分量4（二）目標函數(shù)目標函數(shù)f(x)：衡量一個設計或一種解決方案優(yōu)劣程度的標準或指標，亦稱評價函數(shù)。求目標函數(shù)極大化，記為max.f(x)；求目標函數(shù)極小化，記為min.f(x)；

max.f(x)

等價于-[min.-

f(x)]；本課程統(tǒng)一采用“求極小”的形式：

min.f(x)優(yōu)化目標標準式；優(yōu)化目標轉換5（三）約束條件約束條件：衡量一個設計或一種解決方案是否可行的限制條件。一般利用約束函數(shù)，通過等式約束和不等式約束表示：優(yōu)化的數(shù)學模型優(yōu)化數(shù)學模型三要素：設計變量目標函數(shù)約束條件約束條件標準式；約束條件轉換6（四）優(yōu)化問題分類（1）按目標函數(shù)的個數(shù)分單目標優(yōu)化/多目標優(yōu)化（2）按有無約束條件分無約束優(yōu)化問題/有約束優(yōu)化問題（3）按目標與約束函數(shù)的類型分線性規(guī)劃/非線性規(guī)劃二次規(guī)劃、幾何規(guī)劃（4）按變量的性質分連續(xù)變量優(yōu)化/0-1規(guī)劃/整數(shù)規(guī)劃/離散變量優(yōu)化/組合優(yōu)化/分布參數(shù)優(yōu)化(設計變量為待定函數(shù)，目標和約束函數(shù)為泛函)（5）按優(yōu)化階段的可分性分(靜態(tài))優(yōu)化/動態(tài)規(guī)劃（6）按設計變量與參數(shù)的確定性分(確定性)優(yōu)化/隨機規(guī)劃/模糊優(yōu)化7（五）優(yōu)化技術應用的工作步驟（1）將實際問題抽象為優(yōu)化數(shù)學模型（2）運用優(yōu)化方法求解該模型，獲得優(yōu)化結果（3）對結果進行分析評估，必要時進一步完善模型重新求解（4）解決優(yōu)化應用問題的關鍵解決優(yōu)化問題首先需要塑造合適的優(yōu)化數(shù)學模型：所選取優(yōu)化三要素應能夠體現(xiàn)問題的實質；簡繁適度；充分考慮擬選優(yōu)化方法的特點和要求鑒于優(yōu)化的理論、方法及相應軟件已有很好的進展，工程應用專家需要做的工作是根據問題的特點選擇合適的優(yōu)化方法和算法的參數(shù)，評估優(yōu)化的成果8§1.2設計空間、可行域與目標等值線設計空間：n個設計變量x=[x1,

x2,

…

,

xn]T所張成的n維空間可行點：設計空間中滿足所有約束條件的設計點：

可行域：設計空間中所有可行點構成的集合：目標等值線(/面)優(yōu)化問題簡潔表達：或或無約束優(yōu)化：9§1.3全局最優(yōu)解與局部最優(yōu)解全局極小點(/最優(yōu)點)

x*：局部極小點(/最優(yōu)點)x*：

其中嚴格全局極小點(/最優(yōu)點)

x*：嚴格局部極小點(/最優(yōu)點)

x*：最優(yōu)解通常指：{x*，f(x*)

}，有時僅指x*尋優(yōu)之難對于許多實際應用問題，常存在局部極小點。一般的優(yōu)化方法，成功獲得局部極小點已屬不易；欲獲取全局極小點，則難上加難！研究全局最優(yōu)問題需要對優(yōu)化模型進行凸分析10§1.4凸集與凸函數(shù)（一）凸集凸集的定義：設n維歐氏空間(En)中的子集S，如果對于則稱S為凸集。凸集的幾何含義：在凸集中任取兩點，連接這兩點的線段必亦屬于該集合。凸集的內部無“空洞”，邊界不向內凹。凸集的簡單例子

圓域：平面：半空間：Sx1x211凸組合凸集的性質：兩個凸集的交集仍為凸集：若S1、S2為凸集，則S1∩S2亦為凸集凸集的數(shù)乘仍為凸集若S1為凸集，則S=α

S1={αx|x∈S1}亦為凸集分離定理、支撐定理（二）凸函數(shù)凸函數(shù)定義：設f

(x)是定義在凸集S

En上的函數(shù)，如果對于則稱f

(x)為凸函數(shù)。

若≤改為<，則為嚴格凸函數(shù)；若≤改為≥，則為凹函數(shù)；若≤改為>，則為嚴格凹函數(shù)。f(x)xλx1+(1-λ)x2x2x1f(x1)f(x2)λf(x1)+(1-λ)

f(x2)f(λx1+(1-λ)x2)凸函數(shù)12f(x)x凹函數(shù)Sf(x)x非凸非凹函數(shù)S凸函數(shù)性質：凸函數(shù)在定義域內部是連續(xù)函數(shù)；多個凸函數(shù)的非負線性組合所得到的函數(shù)是凸函數(shù)。凸函數(shù)判別：若函數(shù)一階可微，凸函數(shù)的充要條件：若函數(shù)二階可微，凸函數(shù)的充分條件：正半定函數(shù)圖形位于切線之上f(x)x13S1