重慶工商大學(xué)數(shù)學(xué)模型與數(shù)學(xué)實驗課件第11講 無約束優(yōu)化

1、大學(xué)數(shù)學(xué)實驗Experiments in Mathematics實驗7 無約束優(yōu)化數(shù)學(xué)建模與數(shù)學(xué)實驗- 李煥榮 實 驗 7學(xué)習(xí)并不是人生的全部。但，既然連人生的一部分學(xué)習(xí)也無法征服，還能做什么呢？ 最優(yōu)化是工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究、社會生活中經(jīng)常遇到的問題, 如:優(yōu)化模型和算法的重要意義結(jié)構(gòu)設(shè)計資源分配生產(chǎn)計劃運輸方案解決優(yōu)化問題的手段 經(jīng)驗積累，主觀判斷 作試驗，比優(yōu)劣 建立數(shù)學(xué)模型，求解最優(yōu)策略最優(yōu)化: 在一定條件下，尋求使目標(biāo)最大(小)的決策 實 驗 7 實 驗 7運籌學(xué)(OR: Operations/Operational Research)管理科學(xué)(MS: Management

2、Science)決策科學(xué) (DS: Decision Science)(最)優(yōu)化理論是運籌學(xué)的重要內(nèi)容無約束優(yōu)化OR/MS/DS優(yōu)化(Optimization), 規(guī)劃(Programming)線性規(guī)劃非線性規(guī)劃網(wǎng)絡(luò)優(yōu)化組合優(yōu)化整數(shù)規(guī)劃不確定規(guī)劃多目標(biāo)規(guī)劃目標(biāo)規(guī)劃動態(tài)規(guī)劃 實 驗 7 實 驗 7 優(yōu)化問題的數(shù)學(xué)模型 可行解（只滿足(2)）與最優(yōu)解（滿足(1),(2)） 無約束優(yōu)化（只有(1)）與約束優(yōu)化（(1),(2)） 實際問題一般總有約束，何時可用無約束優(yōu)化處理？ 實 驗 7 實 驗 74. 優(yōu)化工具箱的使用2. 無約束優(yōu)化的基本方法：梯度法，牛頓法，擬牛頓法1. 優(yōu)化問題的最優(yōu)解條件；算

3、法模式無約束優(yōu)化的主要內(nèi)容3. 非線性最小二乘法5. 實際問題中的無約束優(yōu)化模型 實 驗 7 實 驗 7實例1 產(chǎn)銷量安排假設(shè)A產(chǎn)銷平衡假設(shè)Bp隨x (兩種牌號)增加而減小，呈線性關(guān)系某廠生產(chǎn)兩個牌號的同一種產(chǎn)品，如何確定產(chǎn)量使利潤最大 實 驗 7 實 驗 7目標(biāo)利潤最大q隨x (本牌號)增加而減小，呈負(fù)指數(shù)關(guān)系假設(shè)C實例1 產(chǎn)銷量安排 實 驗 7 實 驗 7求解無約束優(yōu)化的基本思路基本思想在中某一點，確定一個搜索方向及沿該方向的移動步長，得到使目標(biāo)函數(shù)下降的新的點迭代步驟Step 1 初始化：初始點x0，終止準(zhǔn)則等Step 2 迭代改進(jìn)：方向d k，步長 kStep 3 終止檢驗：得到近優(yōu)解

4、或k+1k轉(zhuǎn)2選擇d k , k 使 f 下降更快 不同算法 實 驗 7 實 驗 7搜索方向的選擇1 最速下降法（梯度法） 下 降 方 向 最速下降方向迭代改進(jìn)格式算法特點初始階段改進(jìn)較快，最優(yōu)解附近改進(jìn)較慢暫不考慮搜索步長，可設(shè)k=1(負(fù)梯度方向) 實 驗 7 實 驗 72 Newton方法特點局部2階收斂;需計算Hessian陣,它可能病態(tài)或不正定將f(xk+1)在xk點作泰勒展開至二階項，用d替代dk 牛 頓 方 程 牛 頓 方 向迭 代 格 式比較求d使f(xk+1)極小右端對d導(dǎo)數(shù)為0 實 驗 7 實 驗 73 擬Newton方法目的不計算Hessian陣，克服病態(tài)、不正定、計算復(fù)雜

5、等缺陷，同時保持收斂較快的優(yōu)點回顧解方程組 F(x)=0的擬牛頓法思路優(yōu)化問題 實 驗 7 實 驗 7搜索步長的確定線性搜索(Line Search)確定步長方法問題給定xk和方向dk, 確定步長k, 使得優(yōu)化算法黃金分割(0.618)法、Fibonacci法、Newton切線法、割線法、2次或3次插值法等一維優(yōu)化問題 實 驗 7 實 驗 7非線性最小二乘(Least Square)擬合問題給定(t i, y i), i=1,n, 擬合一個函數(shù)y=f(t, x)， 其中x為待定的參數(shù)向量, f 對x非線性。優(yōu)化模型記誤差根據(jù)目標(biāo)函數(shù)是 r(x) 的二次函數(shù)的特點構(gòu)造簡單算法 實 驗 7 實 驗

6、 7優(yōu)化工具箱基本用法：x=fminbnd(f,lb,ub)x=fminunc(f,x0)x=fminunc(f,x0,options,P1,P2,.)x=fminsearch(f,x0,options,P1,P2,.)f.m f(x)的m文件名x0 初始點; x 最優(yōu)解P1,P2, 傳給fun的參數(shù)中間輸入項缺省用 占位 實 驗 7 實 驗 7非線性最小二乘法x,resnorm,res,exitf,out,lambda,jacob=lsqnonlin(fun,x0,lb,ub,options,P1,P2,)輸入的用法與fminunc類似，但注意：f.mf(x)的m文件名: function

7、y=f(x,t)fun.mr(x)的m文件名: function r=fun(x,t,y)輸出 resnom=r(x)T*r(x), res=r(x)(誤差向量)x,resnorm,res,exitf,out,lambda,jacob=lsqcurvefit(f,x0,t,y,lb,ub,options,P1,P2,) 實 驗 7 實 驗 7非線性最小二乘法t0.250.511.523468c19.2118.1515.3614.1012.899.327.455.243.01例3 用下面一組數(shù)據(jù)擬合系數(shù)r, k : 實 驗 7 實 驗 7實例1 產(chǎn)銷量安排已知數(shù)據(jù)原問題 實 驗 7 實 驗 7命令和最優(yōu)解x