最優(yōu)化問題的數(shù)學(xué)模型ppt課件.ppt

《最優(yōu)化問題的數(shù)學(xué)模型ppt課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、最優(yōu)化問題的數(shù)學(xué)模型一般形式其中為連續(xù)函數(shù)，通常還要求連續(xù)可微.根據(jù)實(shí)際問題的不同要求，最優(yōu)化模型有不同的形式，但經(jīng)過適當(dāng)?shù)淖儞Q都可以轉(zhuǎn)換成上述一般形式.決策變量目標(biāo)函數(shù)約束函數(shù)最優(yōu)化問題的分類最優(yōu)化問題無約束最優(yōu)化問題約束最優(yōu)化問題等式約束最優(yōu)化問題不等式約束最優(yōu)化問題混合約束優(yōu)化問題根據(jù)約束條件分類最優(yōu)化問題的分類最優(yōu)化問題連續(xù)最優(yōu)化：決策變量取值連續(xù)離散最優(yōu)化：決策變量取值離散光滑最優(yōu)化：函數(shù)連續(xù)可微非光滑最優(yōu)化：有一個(gè)非光滑線性規(guī)劃非線性最優(yōu)化根據(jù)決策變量的取值整數(shù)規(guī)劃，資源配置，郵路問題生產(chǎn)安排等最優(yōu)化問題無約束

2、最優(yōu)化問題約束最優(yōu)化問題線性規(guī)劃二次規(guī)劃二次罰函數(shù)線性搜索最速下降法，牛頓法，擬牛頓法，共軛方向法單純形法對偶單純形法有效約束集法可行方向法最小二乘法定義設(shè)集合若對于任意兩點(diǎn)及實(shí)數(shù)都有：則稱集合為凸集．換句話說，如果任意兩點(diǎn)則連接x與y的直線段上的所有點(diǎn)都在D內(nèi)。定義:設(shè)實(shí)數(shù)則稱為的凸組合．定理：D是凸集的充分必要條件是D中任意有限個(gè)點(diǎn)的凸組合仍然在D中。例：證明超球?yàn)橥辜C明：設(shè)為超球中的任意兩點(diǎn)，則有：即點(diǎn)屬于超球所以超球?yàn)橥辜Ｒ姷耐辜嚎占?，整個(gè)歐氏空間注：超平面：開半空間：閉半空間：由有限個(gè)閉半空間的交組成的

3、集合叫多面集，其中是非零向量，是數(shù)。多面集是一個(gè)閉凸集。是多面集嗎？是多面集嗎？yesyes凸集的性質(zhì)(１)有限個(gè)凸集的交集為凸集．(２)設(shè)是凸集，是一實(shí)數(shù)，則是凸集.(３)設(shè)是凸集，則的和(差)集是凸集.注：和集和并集有很大的區(qū)別，凸集的并集未必是凸集，而凸集的和集是凸集．定義設(shè)為兩非空凸集，若存在非零向量和實(shí)數(shù)使得：則稱超平面分離了集合和如果則稱集合H嚴(yán)格分離和定理設(shè)為非空閉凸集，則存在非零向量和實(shí)數(shù)使得：即存在超平面嚴(yán)格分離點(diǎn)與凸集注：點(diǎn)與閉凸集的分離定理。Dy.定理設(shè)是非空凸集，則存在非零向量使成立閉包:D的閉包是

4、所有包含D的閉凸集的交.(點(diǎn)與凸集的分離定理)定理設(shè)是的兩個(gè)非空凸集，則存在超平面分離和即存在非零向量使得(兩個(gè)凸集的分離定理)且投影定理設(shè)是非空閉凸集，但則：(１)存在唯一的點(diǎn)使得集合到點(diǎn)的距離最小，即：(２)是點(diǎn)到集合的最短距離點(diǎn)的充要條件為：DY...Farkas引理設(shè)為矩陣，則下述兩組方程中有且僅有一組有解：其中Farkas引理在最優(yōu)化理論研究中起重要作用Farkas引理的另一種形式設(shè)l.l’是兩個(gè)非負(fù)整數(shù)，a0,ai(i=1,…,l)和bi(i=1,…,l’)是Rn中的向量，則線性方程組和不等式組無解當(dāng)且僅當(dāng)存在

5、實(shí)數(shù)使得凸函數(shù)定義設(shè)函數(shù)定義在凸集定義在凸集上，若對任意的及任意的都有：則稱函數(shù)為凸集上的凸函數(shù)．定義嚴(yán)格凸函數(shù)注：將上述定義中的不等式反向，可以得到凹函數(shù)的定義．xyf(x)f(y)例：設(shè)試證明在上是嚴(yán)格凸函數(shù)．證明:設(shè)且都有：因此在上是嚴(yán)格凸函數(shù)．例：試證線性函數(shù)是證明:設(shè)上的凸函數(shù)．則所以是凸函數(shù)．類似可以證明是凹函數(shù)．例：二次函數(shù)是Rn上的嚴(yán)格凸函數(shù)當(dāng)且僅當(dāng)G是正定矩陣.證明：嚴(yán)格凸f(x)嚴(yán)格凸G正定.二次函數(shù)G不定f(x)既不是凸函數(shù)也不是凹函數(shù)G正定f(x)是嚴(yán)格凸函數(shù)G負(fù)正半定f(x)是凹函數(shù)G負(fù)定f(x)

6、是嚴(yán)格凹函數(shù)G正半定f(x)是凸函數(shù)性質(zhì)(１)設(shè)(２)設(shè)函數(shù)，是凸集上的凸函數(shù)，實(shí)數(shù)則也是上的凸函數(shù)．是凸集上的凸則也是上的凸函數(shù)．(３)設(shè)是凸集上的凸函數(shù)，則則也是上的凸函數(shù).(4）設(shè)是凸集上的凸函數(shù)，也是上的凸函數(shù),其中凸規(guī)劃定義可行域是凸集，目標(biāo)函數(shù)是凸函數(shù)的最優(yōu)化問題稱為凸規(guī)劃問題定理(1)局部最優(yōu)解也是全局最優(yōu)解.(2)如果目標(biāo)函數(shù)是嚴(yán)格凸的，則是唯一的全局最優(yōu)解.設(shè)是凸規(guī)劃問題的一個(gè)局部最優(yōu)解，則如果每一個(gè)約束函數(shù)都是凹函數(shù)，則可行域F是凸集.如果每一個(gè)約束函數(shù)都是凸函數(shù)，則可行域F是凸集.如果每一個(gè)約束函數(shù)即

7、是凸函數(shù)又是凹函數(shù)，則可行域F是凸集.凸函數(shù)的判定定理函數(shù)是上凸函數(shù)的充分必要條件是對任意的單變量函數(shù)是關(guān)于的凸函數(shù).一階條件定理設(shè)上的可微函數(shù),則是上凸函數(shù)的充要條件是是嚴(yán)格凸函數(shù)的充要條件：是定義在非空凸集(1)（2）二階條件定理設(shè)在開凸集內(nèi)二階可微，則(1)是內(nèi)的凸函數(shù)的充要條件為，在內(nèi)任一點(diǎn)處，的Hesse矩陣正半定,(2)如果的Hesse矩陣（二階導(dǎo)數(shù)矩陣）在D上正定,則是D上的嚴(yán)格凸函數(shù);反之，如果是D上的的嚴(yán)格凸函數(shù),則在D上正半定.與凸函數(shù)關(guān)系密切的是水平集定理設(shè)是非空凸集,f是定義在D上的凸函數(shù),是任一個(gè)

8、實(shí)數(shù),則水平集是一個(gè)凸集.定理設(shè)f是非空凸集上的連續(xù)凸函數(shù),則水平集是閉凸集.定理設(shè)f是非空凸集上二次連續(xù)可微,且存在常數(shù)使得則水平集是有界閉凸集.初始點(diǎn)的選取依賴于方法的收斂性能.一個(gè)算法稱為收斂的，如果算法產(chǎn)生的序列滿足一個(gè)算法如果對于任意給定的初始點(diǎn)都能夠收斂，就說這個(gè)方法全局收斂或總體收斂.有些