無約束優(yōu)化課件

參考書目：趙靜但琦－數(shù)學(xué)建模與數(shù)學(xué)實驗，高等教育出版社，2005無約束優(yōu)化數(shù)學(xué)建模西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院李偉引例標(biāo)準(zhǔn)形式：無約束優(yōu)化標(biāo)準(zhǔn)形式一些相關(guān)的概念:整體最優(yōu)解:設(shè)f(x)為目標(biāo)函數(shù),S為可行域x*∈S,若對任意x∈S成立f(x*)≤f(x),則稱x*為極小化問題的最優(yōu)解.局部最優(yōu)解:若存在x*的某鄰域，使得對該鄰域中的每個x成立f(x*)≤f(x)，則稱x*為極小化問題的局部最優(yōu)解。為f(x)

在點x處的Hesse矩陣（如果二階偏導(dǎo)數(shù)存在）梯度:稱向量為f(x)（如果一階偏導(dǎo)數(shù)存在）在點x處的梯度局部極小點的充分條件：設(shè)函數(shù)f(x)在點x*處二次可微，若梯度▽f(x*)=0，且Hesse矩陣正定，則x*是局部極小點。無約束問題的極值條件:一階必要條件:設(shè)函數(shù)f(x)在點x*處可微,若x*是局部極小點,則梯度▽f(x*)=0.二階必要條件:設(shè)函數(shù)f(x)在點x*處二次可微,若x*是局部極小點,則梯度▽f(x*)=0,且Hesse矩陣半正定。下降方向:設(shè)向量d是x*點的任一方向,若存在

>0,對每個實數(shù)

(0,

),都有f(x*+d)<f(x*),則稱d為函數(shù)f(x)在x*處的下降方向。如果f(x)是可微函數(shù),且▽▽f(x*)Td<0，則d為f(x)在x*處下降方向.可行方向:設(shè)xS,向量d是x點的某一方向,若存在

>0,對每個實數(shù)

(0,

),都有x*+d∈S,則稱d為x*點的一個可行方向。求解無約束最優(yōu)化問題的基本思想531搜索過程最優(yōu)點(11)初始點(-11)-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.900.0030.990.991E-40.9990.9981E-50.99970.99981E-8

最速下降法是一種最基本的算法，它在最優(yōu)化方法中占有重要地位.最速下降法的優(yōu)點是工作量小，存儲變量較少,初始點要求不高；缺點是收斂慢，最速下降法適用于尋優(yōu)過程的前期迭代或作為間插步驟，當(dāng)接近極值點時，宜選用別種收斂快的算法.

1．最速下降法（共軛梯度法）算法步驟：搜索算法－最速下降法--為了由xk產(chǎn)生xk+1，用二次函數(shù)Q(x)近似f(x)兩邊對x求導(dǎo)，則搜索算法－牛頓法Newton法的基本思想是用一個二次函數(shù)去近似目標(biāo)函數(shù)牛頓法算法步驟：

如果f是對稱正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過一次迭代就可達(dá)到最優(yōu)點,如不是二次函數(shù)，則牛頓法不能一步達(dá)到極值點，但由于這種函數(shù)在極值點附近和二次函數(shù)很近似,因此牛頓法的收斂速度還是很快的.

牛頓法的收斂速度雖然較快，但要求Hessian矩陣要可逆，要計算二階導(dǎo)數(shù)和逆矩陣，就加大了計算機計算量和存儲量.則極小點為：3．?dāng)M牛頓法Matlab優(yōu)化工具箱簡介1.MATLAB求解優(yōu)化問題的主要函數(shù)用Matlab解無約束優(yōu)化問題

其中（3）、（4）、（5）的等式右邊可選用（1）或（2）的等式右邊。函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。常用格式如下：（1）x=fminbnd(fun,x1,x2)（2）x=fminbnd(fun,x1,x2

，options)（3）[x，fval]=fminbnd（...）（4）[x，fval，exitflag]=fminbnd（...）（5）[x，fval，exitflag，output]=fminbnd（...）ToMatlab(wliti1)

主程序為wliti1.m:f='2*exp(-x).*sin(x)';fplot(f,[0,8]);%作圖語句

[xmin,ymin]=fminbnd(f,0,8)f1='-2*exp(-x).*sin(x)';[xmax,ymax]=fminbnd(f1,0,8)

命令格式為:（1）x=fminunc（fun,X0

）；或x=fminsearch（fun,X0

）（2）x=fminunc（fun,X0

，options）；或x=fminsearch（fun,X0

，options）（3）[x，fval]=fminunc（...）；或[x，fval]=fminsearch（...）（4）[x，fval，exitflag]=fminunc（...）；或[x，fval，exitflag]=fminsearch（5）[x，fval，exitflag，output]=fminunc（...）；或[x，fval，exitflag，output]=fminsearch（...）2、多元函數(shù)無約束優(yōu)化問題標(biāo)準(zhǔn)型為：minF(X)[3]fminunc為中型優(yōu)化算法的步長一維搜索提供了兩種算法，由options中參數(shù)LineSearchType控制：LineSearchType=’quadcubic’(缺省值)，混合的二次和三次多項式插值；LineSearchType=’cubicpoly’，三次多項式插使用fminunc和fminsearch可能會得到局部最優(yōu)解.說明:fminsearch是用單純形法尋優(yōu).fminunc的算法見以下幾點說明：[1]fminunc為無約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法。由options中的參數(shù)LargeScale控制：LargeScale=’on’(默認(rèn)值),使用大型算法LargeScale=’off’(默認(rèn)值),使用中型算法[2]fminunc為中型優(yōu)化算法的搜索方向提供了4種算法，由

options中的參數(shù)HessUpdate控制：HessUpdate=’bfgs’（默認(rèn)值），擬牛頓法的BFGS公式；HessUpdate=’dfp’，擬牛頓法的DFP公式；HessUpdate=’steepdesc’，最速下降法例3minf(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)ToMatlab(wliti3)1、編寫M-文件fun1.m:functionf=fun1(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

2、輸入M文件wliti3.m如下:x0=[-1,1];x=fminunc(‘fun1’,x0);y=fun1(x)

3、運行結(jié)果:x=0.5000-1.0000y=1.3029e-10

某廠生產(chǎn)一種產(chǎn)品有甲、乙兩個牌號，討論在產(chǎn)銷平衡的情況下如何確定各自的產(chǎn)量，使總利潤最大.所謂產(chǎn)銷平衡指工廠的產(chǎn)量等于市場上的銷量.實例產(chǎn)銷量的最佳安排基本假設(shè)1．價格與銷量成線性關(guān)系基本假設(shè)2．成本與產(chǎn)量成負(fù)指數(shù)關(guān)系

模型建立

若根據(jù)大量的統(tǒng)計數(shù)據(jù),求出系數(shù)b1=100,a11=1,a12=0.1,b2=280,a21=0.2,a22=2,r1=30,λ1=0.015,c1=20,r2=100,λ2=0.02,c2=30,則問題轉(zhuǎn)化為無約束優(yōu)化問題：求甲,乙兩個牌號的產(chǎn)量x1，x2，使總利潤z最大.

為簡化模型,先忽略成本,并令a12=0,a21=0,問題轉(zhuǎn)化為求:z1=(b1-a11x1-q1

)x1+(b2-a22x2-q2)x2

的極值.顯然其解為x1=b1/2a11=50,x2=b2/2a22=70,我們把它作為原問題的初始值.總利潤為：z(x1,x2)=(p1-q1)x1+(p2-q2)x2

模型求解1.建立M-文件fun.m:

functionf=fun(x)y1=((100-x(1)-0.1*x(2))-(30*exp(-0.015*x(1))+20))*x(1);y2=((280-0.2*x(1)-2*x(2))-(100*exp