第四講---多變量優(yōu)化模型

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

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

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

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

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

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

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

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

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

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

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

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