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

1、優(yōu)化原理與方法第 1 講主講人：劉國華1優(yōu)化原理與方法優(yōu)化原理與方法參考書：參考書： 汪樹玉、劉國華汪樹玉、劉國華 等，等， 系統(tǒng)分析（第五章系統(tǒng)分析（第五章 優(yōu)化方法）優(yōu)化方法），浙江大學(xué)出版社；浙江大學(xué)出版社； 汪樹玉汪樹玉 等，等， 優(yōu)化原理、方法與工程應(yīng)用，浙江大學(xué)出優(yōu)化原理、方法與工程應(yīng)用，浙江大學(xué)出版社；版社； 甘應(yīng)愛甘應(yīng)愛 等，等， 運(yùn)籌學(xué)，清華大學(xué)出版社。運(yùn)籌學(xué)，清華大學(xué)出版社。期末考核方式：閉卷考試期末考核方式：閉卷考試2 優(yōu)化優(yōu)化 VS 優(yōu)選、方案比選優(yōu)選、方案比選 優(yōu)化理論：數(shù)學(xué)規(guī)劃、運(yùn)籌學(xué)優(yōu)化理論：數(shù)學(xué)規(guī)劃、運(yùn)籌學(xué)1.1 優(yōu)化問題的數(shù)學(xué)模型優(yōu)化

2、問題的數(shù)學(xué)模型例1.1 生產(chǎn)安排問題有色磚有色磚 無色磚無色磚資源限制資源限制產(chǎn)品利潤產(chǎn)品利潤300200機(jī)時(shí)機(jī)時(shí)2110人工人工3324顏料顏料208008224331022112121xxxxxxx在滿足，、尋找 21xx）趨極大下，使（21200300 xx 21xx、無色磚產(chǎn)量為設(shè)有色磚產(chǎn)量為3（一）設(shè)計(jì)變量（一）設(shè)計(jì)變量設(shè)計(jì)變量設(shè)計(jì)變量x：需要通過優(yōu)化過程選定的基本參數(shù)。優(yōu)化的目的是尋找這些參數(shù)值的最優(yōu)組合。n個(gè)設(shè)計(jì)變量 x =x1,x2,xi ,xnTn維問題優(yōu)化計(jì)算量隨著問題維數(shù)n的增加而顯著增加 多項(xiàng)式算法 又稱 簡單算法 非多項(xiàng)式算法 又稱 復(fù)雜算法 一般的優(yōu)化算法 屬于 復(fù)

3、雜算法 維數(shù)災(zāi)難xk代表第k個(gè)迭代點(diǎn)； xik 代表xk中的第i個(gè)分量4（二）目標(biāo)函數(shù)（二）目標(biāo)函數(shù)目標(biāo)函數(shù)目標(biāo)函數(shù) f(x)：衡量一個(gè)設(shè)計(jì)或一種解決方案優(yōu)劣程度的標(biāo)準(zhǔn)或指標(biāo)，亦稱評價(jià)函數(shù)。求目標(biāo)函數(shù)極大化，記為 max. f(x)；求目標(biāo)函數(shù)極小化，記為 min. f(x)； max. f(x) 等價(jià)于等價(jià)于 -min. - f(x)；本課程統(tǒng)一采用“求極小”的形式： min. f(x)優(yōu)化目標(biāo)標(biāo)準(zhǔn)式；優(yōu)化目標(biāo)標(biāo)準(zhǔn)式；優(yōu)化目標(biāo)轉(zhuǎn)換優(yōu)化目標(biāo)轉(zhuǎn)換5（三）約束條件（三）約束條件約束條件約束條件：衡量一個(gè)設(shè)計(jì)或一種解決方案是否可行的限制條件。一般利用約束函數(shù)，通過等式約束和不等式約束表示：優(yōu)化的數(shù)學(xué)

4、模型lrhmjgrj,1,2, 0)(,1,2, 0)(xxlrhmjgfxxxrjTn,1,2, 0)( ,1,2, 0)( t. . s )( .min , 21xxxx尋求優(yōu)化數(shù)學(xué)模型三要素：設(shè)計(jì)變量目標(biāo)函數(shù)約束條件約束條件標(biāo)準(zhǔn)式；約束條件標(biāo)準(zhǔn)式；約束條件轉(zhuǎn)換約束條件轉(zhuǎn)換6（四）優(yōu)化問題分類（四）優(yōu)化問題分類（1）按目標(biāo)函數(shù)的個(gè)數(shù)分）按目標(biāo)函數(shù)的個(gè)數(shù)分單目標(biāo)優(yōu)化 / 多目標(biāo)優(yōu)化（2）按有無約束條件分）按有無約束條件分無約束優(yōu)化問題 / 有約束優(yōu)化問題（3）按目標(biāo)與約束函數(shù)的類型分）按目標(biāo)與約束函數(shù)的類型分線性規(guī)劃 / 非線性規(guī)劃二次規(guī)劃、幾何規(guī)劃（4）按變量的性質(zhì)分）按變量的性質(zhì)分連續(xù)變

5、量優(yōu)化/0-1規(guī)劃/整數(shù)規(guī)劃/離散變量優(yōu)化/組合優(yōu)化/ 分布參數(shù)優(yōu)化(設(shè)計(jì)變量為待定函數(shù)，目標(biāo)和約束函數(shù)為泛函)（5）按優(yōu)化階段的可分性分）按優(yōu)化階段的可分性分(靜態(tài))優(yōu)化 / 動(dòng)態(tài)規(guī)劃（6）按設(shè)計(jì)變量與參數(shù)的確定性分）按設(shè)計(jì)變量與參數(shù)的確定性分(確定性)優(yōu)化 / 隨機(jī)規(guī)劃 / 模糊優(yōu)化7（五）優(yōu)化技術(shù)應(yīng)用的工作步驟（五）優(yōu)化技術(shù)應(yīng)用的工作步驟（1）將實(shí)際問題抽象為優(yōu)化數(shù)學(xué)模型）將實(shí)際問題抽象為優(yōu)化數(shù)學(xué)模型（2）運(yùn)用優(yōu)化方法求解該模型，獲得優(yōu)化結(jié)果）運(yùn)用優(yōu)化方法求解該模型，獲得優(yōu)化結(jié)果（3）對結(jié)果進(jìn)行分析評估，必要時(shí)進(jìn)一步完善模型重新求解）對結(jié)果進(jìn)行分析評估，必要時(shí)進(jìn)一步完善模型重新求解（4）

6、解決優(yōu)化應(yīng)用問題的關(guān)鍵）解決優(yōu)化應(yīng)用問題的關(guān)鍵 解決優(yōu)化問題首先需要塑造合適的優(yōu)化數(shù)學(xué)模型： 所選取優(yōu)化三要素應(yīng)能夠體現(xiàn)問題的實(shí)質(zhì)； 簡繁適度； 充分考慮擬選優(yōu)化方法的特點(diǎn)和要求 鑒于優(yōu)化的理論、方法及相應(yīng)軟件已有很好的進(jìn)展，工程應(yīng)用專家需要做的工作是根據(jù)問題的特點(diǎn)選擇合適的優(yōu)化方法和算法的參數(shù)，評估優(yōu)化的成果81.2 設(shè)計(jì)空間、可行域與目標(biāo)等值線設(shè)計(jì)空間、可行域與目標(biāo)等值線 設(shè)計(jì)空間：n個(gè)設(shè)計(jì)變量x=x1, x2, , xnT所張成的n維空間 可行點(diǎn)：設(shè)計(jì)空間中滿足所有約束條件的設(shè)計(jì)點(diǎn)： 可行域：設(shè)計(jì)空間中所有可行點(diǎn)構(gòu)成的集合： 目標(biāo)等值線(/面) 優(yōu)化問題簡潔表達(dá)： 或 或 無約束優(yōu)化：l

7、rhmjgErjn,1,2, 0)( ,1,2, 0)( ,|xxxx；,1,2, 0)( ,1,2, 0)( ,|lrhmjgESrjnxxxx；)(.min)(*xxxxffS：)(.minxxfS)(.minxxfnE91.3 全局最優(yōu)解與局部最優(yōu)解全局最優(yōu)解與局部最優(yōu)解 全局極小點(diǎn)(/最優(yōu)點(diǎn)) x*： 局部極小點(diǎn)(/最優(yōu)點(diǎn)) x*： 其中 嚴(yán)格全局極小點(diǎn)(/最優(yōu)點(diǎn)) x*： 嚴(yán)格局部極小點(diǎn)(/最優(yōu)點(diǎn)) x*： 最優(yōu)解 通常指：x*，f ( x*) ， 有時(shí)僅指 x* 尋優(yōu)之難 對于許多實(shí)際應(yīng)用問題，常存在局部極小點(diǎn)。一般的優(yōu)化方法，成功獲得局部極小點(diǎn)已屬不易；欲獲取全局極小點(diǎn)，則難上加

8、難！ 研究全局最優(yōu)問題需要對優(yōu)化模型進(jìn)行凸分析 Sffxxx )()(*)( )()(*xxxxNSff0, |)(*xxxx-N*, )()(xxxxxSff*),( )()(xxxxxxNSff101.4 凸集與凸函數(shù)凸集與凸函數(shù)（一）凸集（一）凸集 凸集的定義：設(shè)n維歐氏空間(En)中的子集S，如果對于 則稱S為凸集。 凸集的幾何含義：在凸集中任取兩點(diǎn)，連接這兩點(diǎn)的線段必亦屬于該集合。凸集的內(nèi)部無“空洞”，邊界不向內(nèi)凹。 凸集的簡單例子 (1) 圓域：(2) 平面：(3) 半空間：10 21，、SxxS21)1 ( xx有22221214|, ExxSTxx332132172|, Exx

9、xSTxxx332132172|, ExxxSTxxxSx1x211凸組合 凸集的性質(zhì)：(1) 兩個(gè)凸集的交集仍為凸集： 若S1、S2為凸集，則S1S2亦為凸集(2) 凸集的數(shù)乘仍為凸集 若S1為凸集，則S= S1 =x| xS1亦為凸集(3) 分離定理、支撐定理（二）凸函數(shù)（二）凸函數(shù) 凸函數(shù)定義：設(shè)f (x)是定義在凸集S En上的函數(shù)，如果對于 則稱f (x)為凸函數(shù)。 若改為，則為嚴(yán)格凹函數(shù)。1) 0( 21，、Sxx)()1 ()()1 ( 2121xxxxfff有 f(x)xx1+(1- ) x2x2x1f(x1)f(x2)f(x1)+(1- ) f(x2)f(x1+(1- )x2)凸函數(shù)凸函數(shù)12f(x)x凹函數(shù)凹函數(shù)Sf(x)x非凸非凹函數(shù)非凸非凹函數(shù)S 凸函數(shù)性質(zhì)：(1) 凸函數(shù)在定義域內(nèi)部是連續(xù)函數(shù)；(2) 多個(gè)凸函數(shù)的非負(fù)線性組合所得到的函數(shù)是凸函數(shù)。 凸函數(shù)判別：(1) 若函數(shù)一階可微，凸函數(shù)的充要條件：(2) 若函數(shù)二階可微，凸函數(shù)的充分條件： 正半定