第四講---多變量?jī)?yōu)化模型

1、 第四講: 多變量?jī)?yōu)化模型 -雷達(dá)信號(hào)處理國(guó)防科技重點(diǎn)實(shí)驗(yàn)室數(shù)學(xué)建?；A(chǔ)14.1 多變量?jī)?yōu)化建模舉例一家彩色電視制造商計(jì)劃推出19-英寸和21英寸兩款LCD平板電視機(jī), 制造商建議零售價(jià)格(MSRP)分別是$339/臺(tái)和$399/臺(tái). 制造商給銷售公司的價(jià)格是每臺(tái)$195和$225,附加$400,000的固定費(fèi)用(代理費(fèi)). 市場(chǎng)環(huán)境對(duì)銷售影響 (1) 對(duì)于每款電視機(jī)，每多買一臺(tái)該款電視機(jī)平均銷售價(jià)格降1美分; (2) 21寸的每買一臺(tái),19寸的平均售價(jià)減小0.3美分; (3) 19寸的每買一臺(tái),21寸的平均售價(jià)減小0.4美分;問(wèn)題: 制造商兩款電視機(jī)應(yīng)該各生產(chǎn)多少臺(tái)？ 19英寸LCD電視機(jī)2

2、1英寸LCD電視機(jī)銷售商獲利最大24.1 多變量?jī)?yōu)化建模舉例符號(hào)化(變量)基本假設(shè)(變量間相互關(guān)系)s-19寸TV售出臺(tái)數(shù)t-21寸TV售出臺(tái)數(shù)p-19寸售出價(jià)格q-21寸售出價(jià)格C-獲得這些電視機(jī)的成本R-銷售這些電視機(jī)的總收入P-銷售這些電視機(jī)的總利潤(rùn)黑色變量-決策/優(yōu)化變量藍(lán)色變量-中間變量紅色變量-優(yōu)化變量34.1 多變量?jī)?yōu)化建模舉例優(yōu)化模型目標(biāo)函數(shù)的圖像目標(biāo)函數(shù)的等高線44.2 多元函數(shù)極值點(diǎn)的判斷準(zhǔn)則設(shè) 是一個(gè)至少二階可微分的n元函數(shù) (充分條件:所有的二階偏導(dǎo)數(shù)存在且連續(xù)),f(x)的梯度向量和Hessian矩陣定義為:54.2 多元函數(shù)極值點(diǎn)的判斷準(zhǔn)則二階泰勒展開 對(duì)于一個(gè)對(duì)稱

3、的nn的方陣A,如果對(duì)于任何的非零向量x, , 矩陣稱作正定的 , 矩陣稱作非負(fù)定的 , 矩陣稱作負(fù)定的 ,矩陣稱作非正定的 滿足的點(diǎn)稱作函數(shù)f(x)駐點(diǎn).按照二階泰勒展開,在駐點(diǎn)的附件,函數(shù)值滿足:64.2 多元函數(shù)極值點(diǎn)判斷極大值點(diǎn)與極小值點(diǎn)條件 74.2 多元函數(shù)極值點(diǎn)判斷模型求解 求解線性方程組最優(yōu)的生產(chǎn)方案是:19寸生產(chǎn)4735臺(tái),21寸生產(chǎn)7043臺(tái), 最大利潤(rùn)為 553641(美元)這種求多變量?jī)?yōu)化問(wèn)題的解析方法(解線性方程組)僅在目標(biāo)函數(shù)是優(yōu)化變量的二次函數(shù)時(shí)有效. 對(duì)于復(fù)雜函數(shù)必須采用專門的優(yōu)化算法求解問(wèn)題.84.3 無(wú)約束優(yōu)化問(wèn)題的求解方法f(x)是可微分的n-元函數(shù)目標(biāo)函

4、數(shù)是二次函數(shù)的情況n=1情況(1) a0, 拋物線開口向上, (2) a0, 拋物線開口向下, n1情況函數(shù)存在唯一的駐點(diǎn)對(duì)稱矩陣(1) A是正定矩陣 (2) A是負(fù)定矩陣 (3) A既有正特征值,也有負(fù)特征值 ,x*是一個(gè)鞍點(diǎn), 函數(shù)沒(méi)有最大值點(diǎn),也沒(méi)有最小值點(diǎn).94.3 無(wú)約束優(yōu)化問(wèn)題的求解方法最速下降法基本思想: 從一個(gè)初始點(diǎn)出發(fā), 沿著函數(shù)值下降最快的負(fù)梯度方向搜達(dá)到該方向上的最小值點(diǎn), 從這點(diǎn)出發(fā) 重復(fù)迭代搜索直到滿終止條件. 單步搜索過(guò)程描述最速下降方向, 搜索方向迭代格式, 步長(zhǎng)待定步長(zhǎng)的單變量函數(shù)確定最優(yōu)搜索步長(zhǎng)更新搜索起點(diǎn)算法流程初始化: 計(jì)算: 輸出 Yesno104.3

5、無(wú)約束優(yōu)化問(wèn)題的求解方法函數(shù)圖像極小值點(diǎn)注1: 最速下降方法總是收斂到一個(gè)駐點(diǎn),收斂到哪一個(gè)駐點(diǎn)于初始點(diǎn) 的位置有關(guān).等高線圖12114.3 無(wú)約束優(yōu)化問(wèn)題的求解方法等高線圖注2: 最速下降法在接近極小值點(diǎn)是會(huì)出現(xiàn)震蕩現(xiàn)象,收斂速度很慢.注3: 在每個(gè)極小值附近,函數(shù)的性態(tài)可以用拋物面近似,等值線近似于同心橢圓,橢圓的中心是極值點(diǎn).等值線橢圓偏心率越大,最速下降法收斂越慢. 迭代過(guò)程示意圖124.3 無(wú)約束優(yōu)化問(wèn)題的求解方法牛頓迭代法基本思想: 在每個(gè)迭代點(diǎn)上,把函數(shù)在這點(diǎn)進(jìn)行二階泰勒展開,用展開的二次函數(shù)的極小值點(diǎn)進(jìn)行更新.在 點(diǎn)計(jì)算函數(shù)的梯度和Hessian矩陣, 函數(shù)在 附近用二次函數(shù)近

6、似134.3 無(wú)約束優(yōu)化問(wèn)題的求解方法牛頓迭代算法流程初始化: 計(jì)算: 輸出 yesno等高線圖12紅色區(qū)域是Newton法收斂的初始點(diǎn)選擇區(qū)域,它一般比最速下降法收斂的初始點(diǎn)選擇區(qū)域小得多. 在極小值點(diǎn),目標(biāo)的Hessian矩陣是正定的, 因此在它的某個(gè)鄰域內(nèi)Hessian矩陣也是正定的, Newton法在這鄰域內(nèi)選初始點(diǎn)一般是收斂的.最速下降法+Newton法 開始階段接近極小值點(diǎn)時(shí)其它解無(wú)約束非線性規(guī)劃的方法 共軛梯度方法 各種修正的Newton法144.3 無(wú)約束優(yōu)化問(wèn)題的求解方法函數(shù)的梯度函數(shù)和Hessian矩陣函數(shù)是否可利用初始點(diǎn)Matlab庫(kù)函數(shù)及其使用說(shuō)明x, FVAL, EX

7、ITFLAG, OUTPUT, GRAD, HESSIAN =fminunc(FUN,x,options,varargin)極小值點(diǎn)迭代過(guò)程終止的原因：梯度模小于容忍值 優(yōu)化變量?jī)纱蔚牟钚∮谌萑讨?兩次鄰近迭代函數(shù)值小于容忍值極小值迭代次數(shù)等信息最優(yōu)點(diǎn)梯度最優(yōu)點(diǎn)Hessian矩陣目標(biāo)函數(shù)名注：函數(shù)的自變量必須是向量形式的標(biāo)量函數(shù)優(yōu)化向量的范圍限制154.4 等式約束的多變量?jī)?yōu)化問(wèn)題問(wèn)題描述的一般形式約束條件目標(biāo)函數(shù)優(yōu)化向量, 決策向量可行解集合一般情況下等式約束的數(shù)目要小于優(yōu)化向量的維數(shù),否則可行解集合可能是空集,優(yōu)化問(wèn)題無(wú)解.16n+m個(gè)方程，n+m個(gè)未知數(shù)，適定方程組4.4 等式約束的

8、多變量?jī)?yōu)化問(wèn)題拉格朗日乘子法駐點(diǎn)拉格朗日方程組Edwards, 1973在 是線性獨(dú)立向量的情況下， 是目標(biāo)函數(shù) 在S上的極值點(diǎn)，那么它必然是Largrange方程組的解。 17求函數(shù) 在橢圓 上的最大值4.4 等式約束的多變量?jī)?yōu)化問(wèn)題拉格朗日乘子法算例輔助函數(shù)拉格朗日方程組最小值點(diǎn)最大值點(diǎn)18兩顆行星圍繞恒星在各自的橢圓軌道上運(yùn)行，軌道位于同一平面，各自的運(yùn)行周期(一年的時(shí)間）分別為 和 ， 和 是不可約的，求兩顆行星之間的最短和最常距離。4.4 等式約束的多變量?jī)?yōu)化問(wèn)題行星最近距離的優(yōu)化建模與求解 在行星軌道平面上建立直角坐標(biāo)系，橢圓中心為坐標(biāo)原點(diǎn)，中心與恒星的連線為x軸XOY；伴隨地建立

9、極坐標(biāo)系(O, ).基本假設(shè)與建模準(zhǔn)備 軌道方程19 T1和T2不可約是指不存在非負(fù)的正整數(shù)對(duì)(m,n),使得 4.4 等式約束的多變量?jī)?yōu)化問(wèn)題基本假設(shè)與建模準(zhǔn)備(續(xù)）1(t)和2(t)是滿足：的連續(xù)函數(shù)。模型1：無(wú)約束建模t的高度非線性函數(shù)204.4 等式約束的多變量?jī)?yōu)化問(wèn)題這樣一個(gè)優(yōu)化問(wèn)題雖然形式上是無(wú)約束優(yōu)化，但存在太多的局部極值點(diǎn)，發(fā)現(xiàn)最大值和最小值異常困難。例如參數(shù)滿足：目標(biāo)函數(shù)隨時(shí)間變化的曲線如下：214.4 等式約束的多變量?jī)?yōu)化問(wèn)題對(duì)于行星1軌道上的任意一點(diǎn)A ,行星經(jīng)過(guò)這點(diǎn)的時(shí)刻是：模型2：約束優(yōu)化模型在這些時(shí)刻行星2在軌道上的位置是:由于兩個(gè)周期是不可約的，上述集合在行星2的

10、軌道上是稠密的，因此行星1在軌道上A點(diǎn)，到行星2的最短距離是：224.4 等式約束的多變量?jī)?yōu)化問(wèn)題行星1到行星2的最小距離為帶兩個(gè)等式約束的優(yōu)化問(wèn)題，優(yōu)化變量是四維的。234.4 等式約束的多變量?jī)?yōu)化問(wèn)題拉格朗日乘子法拉格朗日方程求解非線性方程組參數(shù)化方法無(wú)約束優(yōu)化問(wèn)題244.4 等式約束的多變量?jī)?yōu)化問(wèn)題254.5 不等式約束的多變量?jī)?yōu)化問(wèn)題一家彩色電視制造商計(jì)劃推出19-英寸和21英寸兩款LCD平板電視機(jī), 制造商建議零售價(jià)格(MSRP)分別是$339/臺(tái)和$399/臺(tái). 制造商給銷售公司的價(jià)格是每臺(tái)$195和$225,附加$400,000的固定費(fèi)用(代理費(fèi)). 市場(chǎng)環(huán)境對(duì)銷售影響 (1)

11、對(duì)于每款電視機(jī)，每多買一臺(tái)該款電視機(jī)平均銷售價(jià)格降1美分; (2) 21寸的每買一臺(tái),19寸的平均售價(jià)減小0.3美分; (3) 19寸的每買一臺(tái),21寸的平均售價(jià)減小0.4美分; 生產(chǎn)商生產(chǎn)能力限制 由于產(chǎn)品更新?lián)Q代,生產(chǎn)能力有限,19寸年產(chǎn)不超過(guò)5000臺(tái)，21寸年產(chǎn)不超過(guò)8000臺(tái)，19寸和21寸年產(chǎn)總量不超過(guò)10000臺(tái)。 問(wèn)題: 制造商兩款電視機(jī)應(yīng)該各生產(chǎn)多少臺(tái)？ 264.5 不等式約束的多變量?jī)?yōu)化問(wèn)題優(yōu)化模型目標(biāo)函數(shù)是雙變量二次函數(shù)，約束條件由5個(gè)線性 不等式約束構(gòu)成-約束二次規(guī)劃 最大值點(diǎn) 可行解區(qū)域274.5 不等式約束的多變量?jī)?yōu)化問(wèn)題不等式約束的多變量?jī)?yōu)化問(wèn)題通過(guò)適當(dāng)處理轉(zhuǎn)化成

12、無(wú)約束優(yōu)化問(wèn)題進(jìn)行求解 最速下降法 牛頓迭代法 共軛梯度法 修正牛頓迭代法 284.5 不等式約束的多變量?jī)?yōu)化問(wèn)題懲罰函數(shù)方法引進(jìn)一個(gè)輔助函數(shù) 其中 和 是正數(shù)，稱作等式約束和不等式約束的懲罰因子。懲罰項(xiàng)可行解集合 當(dāng)一個(gè)點(diǎn)不在可行解集合中時(shí)，R個(gè)等式約束和S個(gè)不等式約束中至少有一個(gè)不成立。這種情況下，懲罰項(xiàng)將是正的。該點(diǎn)偏離可行解集越遠(yuǎn)，懲罰項(xiàng)越大。因此，懲罰項(xiàng)的存在傾向于在可行解集上或可行解集附近尋找輔助函數(shù)的最小值。294.5 不等式約束的多變量?jī)?yōu)化問(wèn)題懲罰函數(shù)的作用標(biāo)準(zhǔn)化 輔助函數(shù)304.5 不等式約束的多變量?jī)?yōu)化問(wèn)題最大值點(diǎn) 可行解區(qū)域314.5 不等式約束的多變量?jī)?yōu)化問(wèn)題求解無(wú)約束優(yōu)化 問(wèn)題驗(yàn)證約束條件是否近似成立 初始化：懲罰函數(shù)方法算法流程所有約束滿足324.5 不等式約束的多變量?jī)?yōu)化問(wèn)題拉格朗日乘子方法前面的拉格朗日乘子方法主要用于等式約束的情況。對(duì)于具有不等式約束的優(yōu)化問(wèn)題，使用拉格朗日乘子方法的關(guān)鍵在于如何把不等式約束轉(zhuǎn)化為等式約束。不等式約束等價(jià)于 存在某個(gè)數(shù) 使得等式成立334.5 不等式約束的多變量?jī)?yōu)化問(wèn)題n維空間中帶不等式約束的優(yōu)化問(wèn)題n+S維空間中全等式約束的優(yōu)化問(wèn)題344.5