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

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

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

優(yōu)化理論：數(shù)學(xué)規(guī)劃、運籌學(xué)§1.1優(yōu)化問題的數(shù)學(xué)模型例1.1生產(chǎn)安排問題有色磚無色磚資源限制產(chǎn)品利潤300200機時2110人工3324顏料2083〔一〕設(shè)計變量設(shè)計變量x：需要通過優(yōu)化過程選定的根本參數(shù)。優(yōu)化的目的是尋找這些參數(shù)值的最優(yōu)組合。n個設(shè)計變量x=[x1,x2,…xi,…,xn]T——n維問題優(yōu)化計算量隨著問題維數(shù)n的增加而顯著增加多項式算法又稱簡單算法非多項式算法又稱復(fù)雜算法一般的優(yōu)化算法屬于復(fù)雜算法維數(shù)災(zāi)難xk代表第k個迭代點；xik代表xk中的第i個分量4〔二〕目標函數(shù)目標函數(shù)f(x)：衡量一個設(shè)計或一種解決方案優(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)化目標轉(zhuǎn)換5〔五〕優(yōu)化技術(shù)應(yīng)用的工作步驟〔1〕將實際問題抽象為優(yōu)化數(shù)學(xué)模型〔2〕運用優(yōu)化方法求解該模型，獲得優(yōu)化結(jié)果〔3〕對結(jié)果進行分析評估，必要時進一步完善模型重新求解〔4〕解決優(yōu)化應(yīng)用問題的關(guān)鍵解決優(yōu)化問題首先需要塑造適宜的優(yōu)化數(shù)學(xué)模型：所選取優(yōu)化三要素應(yīng)能夠表達問題的實質(zhì)；簡繁適度；充分考慮擬選優(yōu)化方法的特點和要求鑒于優(yōu)化的理論、方法及相應(yīng)軟件已有很好的進展，工程應(yīng)用專家需要做的工作是根據(jù)問題的特點選擇適宜的優(yōu)化方法和算法的參數(shù)，評估優(yōu)化的成果8§1.2設(shè)計空間、可行域與目標等值線設(shè)計空間：n個設(shè)計變量x=[x1,

x2,

…

,

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

可行域：設(shè)計空間中所有可行點構(gòu)成的集合：目標等值線(/面)優(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īng)用問題，常存在局部極小點。一般的優(yōu)化方法，成功獲得局部極小點已屬不易；欲獲取全局極小點，那么難上加難！研究全局最優(yōu)問題需要對優(yōu)化模型進行凸分析10§1.4凸集與凸函數(shù)〔一〕凸集凸集的定義：設(shè)n維歐氏空間(En)中的子集S，如果對于那么稱S為凸集。凸集的幾何含義：在凸集中任取兩點，連接這兩點的線段必亦屬于該集合。凸集的內(nèi)部無“空洞〞，邊界不向內(nèi)凹。凸集的簡單例子圓域：平面：半空間：Sx1x211凸組合凸集的性質(zhì)：兩個凸集的交集仍為凸集：假設(shè)S1、S2為凸集，那么S1∩S2亦為凸集凸集的數(shù)乘仍為凸集假設(shè)S1為凸集，那么S=αS1={αx|x∈S1}亦為凸集別離定理、支撐定理〔二〕凸函數(shù)凸函數(shù)定義：設(shè)f(x)是定義在凸集SEn上的函數(shù)，如果對于那么稱f(x)為凸函數(shù)。假設(shè)≤改為<，那么為嚴格凸函數(shù)；假設(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ù)性質(zhì)：凸函數(shù)在定義域內(nèi)部是連續(xù)函數(shù)；多個凸函數(shù)的非負線性組合所得到的函數(shù)是凸函數(shù)。凸函數(shù)判別：假設(shè)函數(shù)一階可微，凸函數(shù)的充要條件：假設(shè)函數(shù)二階可微，凸函數(shù)的充分條件：正半定函數(shù)圖形位于切線之上f(x)x13S1作業(yè)P4025.1