Matlab在求解優(yōu)化問題中的應(yīng)用

1、參考文獻:Matlab7.2優(yōu)化設(shè)計實例指導(dǎo)教程褚洪生、杜增吉、閻金華 等編著機械工業(yè)出版社，2007本本 講講 內(nèi)內(nèi) 容容l多目標規(guī)劃問題l最大最小化問題l半無限問題l整數(shù)規(guī)劃問題l大規(guī)模最優(yōu)化問題一、最優(yōu)化理論概述一、最優(yōu)化理論概述二、二、Matlab優(yōu)化工具箱簡介優(yōu)化工具箱簡介三、無約束優(yōu)化問題三、無約束優(yōu)化問題四、約束優(yōu)化問題四、約束優(yōu)化問題五、方程求解五、方程求解一、最優(yōu)化理論概述一、最優(yōu)化理論概述 最優(yōu)化是一門研究如何科學(xué)、合理、迅速地確定可行方案并找到其中最優(yōu)方案的學(xué)科。 最優(yōu)化方法就是專門研究如何從多個方案中科學(xué)合理地提出最佳方案的科學(xué)。（一）最優(yōu)化問題基本模型（一）最優(yōu)化問題

2、基本模型最優(yōu)化問題的一般形式：min( ),nf xxXR:nfXRR稱為目標函數(shù)，X稱為問題的可行域。min( ),.nf xxR無約束問題一般形式：約束問題一般形式：約束函數(shù)m in()fx.( )0,1,( )0,1, .ieiest c xiEmc xiImm 等式約束條件不等式約束條件可行域X為： ( )0,; ( )0, .iiXc xiE c xiI線性規(guī)劃二次規(guī)劃凸規(guī)劃此外還分成：整數(shù)規(guī)劃、動態(tài)規(guī)劃、網(wǎng)絡(luò)規(guī)劃、非光滑規(guī)劃、隨機規(guī)劃、幾何規(guī)劃、多目標規(guī)劃等。例例 數(shù)據(jù)擬合問題或無約束問題51( , )|()|iiif a byaxb2min( , ),( , ).Tf a ba

3、bR521( , )()iiif a byaxb例例 食譜問題線性規(guī)劃問題1minnjjjc x1. .,1,0,1, .nijjijjs ta xbimxjn1m inniiic x nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0.22112222212111212111線性規(guī)劃問題的標準型：minTc x 0.xbAxts記為記為。則線性規(guī)劃標準型可。則線性規(guī)劃標準型可記記nmijTnTmTnaAxxxxbbbbcccc )(,),(,),(,),(212121目目標標函函數(shù)數(shù)：)1(: maxTc x原 問 題 目 標 函 數(shù)minTc x約約束束

4、條條件件：)2(1 122( )iiinniia xa xa xb原問題條件： 02211iniinniniixbxxaxaxan ix稱為松弛變量1 122( )iiinniiia xa xa xb原問題條件： 02211iniinniniixbxxaxaxan ix稱為剩余變量()iiiix原問題：無非負約束，則令非標準型線性規(guī)劃問題過渡到標準型線性規(guī)劃問題的處理方法：iiiiix = u - vu ,v0例例 二次規(guī)劃問題1min2TTx Hxgx11. .,1,1,.nijjiejnijjiejs taxbimaxbimm 通過逐步二次規(guī)劃能使一般的非線性規(guī)劃問題的求解過程得到簡化，因

5、此，二次規(guī)劃迭代法也是目前求解最優(yōu)化問題時常用的方法。 由于二次規(guī)劃問題本身也是一大類實際應(yīng)用中經(jīng)常碰到的問題，所以，二次規(guī)劃問題在最優(yōu)化理論和應(yīng)用各方面都占有非常重要的地位。例例 最小二乘問題1( )( )( )2minnTxRfxr xr x( )0,1,irxim 如果r(x)是x的非線性函數(shù)，則問題稱為非線性最小二乘問題；如果r(x)是x的線性函數(shù)，則問題稱為線性最小二乘問題。 非線性最小二乘問題在數(shù)據(jù)擬合、參數(shù)估計和函數(shù)逼近等方面有廣泛應(yīng)用。 非線性最小二乘問題既可以看作為無約束極小化的特殊情形，又可以看作為解如下方程組：被稱為殘量函數(shù)（二）最優(yōu)化問題的實現(xiàn)（二）最優(yōu)化問題的實現(xiàn) 用

6、最優(yōu)化方法解決最優(yōu)化問題的技術(shù)稱為最優(yōu)化技術(shù)，它包含兩個方面的內(nèi)容：建立數(shù)學(xué)模型。建立數(shù)學(xué)模型。即用數(shù)學(xué)語言來描述最優(yōu)化問題。模型中的數(shù)學(xué)關(guān)系式反映了最優(yōu)化問題所要達到的目標和各種約束條件。數(shù)學(xué)求解。數(shù)學(xué)求解。數(shù)學(xué)模型建好以后，選擇合理的最優(yōu)化方法進行求解。 Matlab實現(xiàn) 由于最優(yōu)化問題在近些年來得到了廣泛的應(yīng)用， Matlab工具箱函數(shù)也同時有了飛速的發(fā)展。利用Matlab的優(yōu)化工具箱可以求解如下問題：線性、非線性最小化最大最小化二次規(guī)劃半無限問題線性、非線性方程（組）的求解線性、非線性的最小二乘問題 此外，該工具箱還提供了線性、非線性最小化，方程求解，曲線擬合，二次規(guī)劃等問題中大型課題

7、的求解方法，為優(yōu)化方法在工程中的實際應(yīng)用提供了更方便快捷的途徑。(1)目標函數(shù)最小化(2)約束非正(3)避免使用全局變量 使用Matlab的優(yōu)化工具箱時，由于優(yōu)化函數(shù)要求目標函數(shù)和約束條件滿足一定的格式，所以需要用戶在進行模型輸入時注意以下幾個問題： 優(yōu)化函數(shù)fminbnd、fminsearch、fminunc、fminicon、fgoalattain、fminmax和lsqnonlin都要求目標函數(shù)最小化，如果優(yōu)化問題要求目標函數(shù)最大化，可以通過使該目標函數(shù)的負值最小化即 -f (x) 最小化來實現(xiàn)。近似地，對于quadprog 函數(shù)提供 -H 和 -f，對于linprog函數(shù)提供 -f。

8、優(yōu)化工具箱要求非線性不等式約束的形式為Ci(x) 0,通過對不等式取負可以達到使大于零的約束形式變?yōu)樾∮诹愕牟坏仁郊s束形式的目的，如 Ci(x) 0形式的約束等價于-Ci(x) 0 ；Ci(x) b形式的約束等價于-Ci(x) +b0。二、二、Matlab優(yōu)化工具箱簡介優(yōu)化工具箱簡介（一）優(yōu)化工具箱中的函數(shù)（一）優(yōu)化工具箱中的函數(shù)優(yōu)化工具箱中的函數(shù)包括下面幾類： 函數(shù)函數(shù) 描述描述fminsearch, fminunc無約束非線性最小化fminbnd有邊界的標量非線性最小化fmincon有約束的非線性最小化linprog線性規(guī)劃quadprog二次規(guī)劃fgoalattain多目標規(guī)劃fmini

9、max最大最小化fseminf半無限問題1. 最小化函數(shù)最小化函數(shù)2. 最小二乘問題最小二乘問題 函數(shù)函數(shù) 描述描述 線性最小二乘lsqnonlin非線性最小二乘lsqnonneg非負線性最小二乘lsqlin有約束線性最小二乘lsqcurvefit非線性曲線擬合3. 方程求解函數(shù)方程求解函數(shù) 函數(shù)函數(shù) 描述描述 線性方程求解fzero標量非線性方程求解fsolve非線性方程求解u 中型問題方法演示函數(shù)中型問題方法演示函數(shù)4. 演示函數(shù)演示函數(shù) 函數(shù)函數(shù) 描述描述tutdemo教程演示optdemo演示過程菜單officeassign求解整數(shù)規(guī)劃goaldemo目標達到舉例dfildemo過濾器

10、設(shè)計的有限精度u 大型問題方法演示函數(shù)大型問題方法演示函數(shù) 函數(shù)函數(shù) 描述描述molecule用無約束非線性最小化進行分子組成求解circustent馬戲團帳篷問題二次規(guī)劃問題optdeblur用有邊界線性最小二乘法進行圖形處理（二）優(yōu)化函數(shù)的變量（二）優(yōu)化函數(shù)的變量 在Matlab的優(yōu)化工具箱中，定義了一系列的標準變量，通過使用這些標準變量，用戶可以使用Matlab來求解在工作中碰到的問題。主要有如下三類：1. 輸入變量輸入變量 調(diào)用 Matlab 優(yōu)化工具箱，需要首先給出一些輸入變量，優(yōu)化工具箱函數(shù)通過對這些輸入變量的處理得到用戶需要的結(jié)果。輸入變量大體上分成輸入系數(shù)和輸入?yún)?shù)兩類：變量名

11、變量名 作用和含義作用和含義 主要的調(diào)用函數(shù)主要的調(diào)用函數(shù)A, bA矩陣和b向量分別為線性不等式約束的系數(shù)矩陣和右端項fgoalattain, fmincon, fminimax, fseminf, linprog, lsqlin, quadprogAeq, beqAeq矩陣和beq向量分別為線性方程約束的系數(shù)矩陣和右端項fgoalattain, fmincon, fminimax, fseminf, linprog, lsqlin, quadprogC, d矩陣C和向量d分別為超定或不定線性系統(tǒng)方程組的系數(shù)矩陣和進行求解的右端項lsqlin, lsqnonnegf線性方程或二次方程中線性項的

12、系數(shù)向量linprog, quadprogH二次方程中二次項的系數(shù)quadprogub, lb變量的上下界fgoalattain, fmincon, fminimax, fseminf, linprog, lsqlin, quadprog,lsqcurvefit, lsqnonlinfun待優(yōu)化的函數(shù)fgoalattain, fminbnd, fmincon, fminimax, fminsearch, fminunc, fseminf, fzero, fsolve, lsqcurvefit, lsqnonlinnonlcon計算非線性不等式和等式fgoalattain, fmincon, f

13、minimaxseminfcon計算非線性不等式約束、 等式約束和半無限約束的函數(shù)fseminf輸入系數(shù)表輸入系數(shù)表變量名變量名 作用和含義作用和含義 主要的調(diào)用函數(shù)主要的調(diào)用函數(shù)goal目標試圖達到的值fgoalattainntheta半無限約束的個數(shù)fseminfoptions優(yōu)化選項參數(shù)結(jié)構(gòu)所有P1,P2,傳給函數(shù)fun,變量nonlcon,變量seminfcon的其它變量fgoalattain, fminbnd, fmincon, fminimax, fsearch, fminunc, fseminf, fzero, fsolve, lsqcurvefit, lsqnonlinweig

14、ht控制對象未達到或超過的加權(quán)向量fgoalattainxdata,ydata擬合方程的輸入數(shù)據(jù)和測量數(shù)據(jù)lsqcurvefitx0初始點除fminbnd所有x1,x2函數(shù)最小化的區(qū)間fminbnd輸入?yún)?shù)表輸入?yún)?shù)表2. 輸出變量輸出變量變量名變量名 作用和含義作用和含義x由優(yōu)化函數(shù)求得的解fval解x處的目標函數(shù)值exitflag退出條件output包含優(yōu)化結(jié)果信息的輸出結(jié)構(gòu)lambda解x處的Lagrange乘子grad解x處函數(shù)fun的梯度值hessian解x處函數(shù)fun的Hessian矩陣jacobian解x處函數(shù)fun的Jacobian矩陣maxfval解x處函數(shù)的最大值attai

15、nfactor解x處的達到因子residual解x處的殘差值resnorm解x處殘差的平方范數(shù) 調(diào)用 Matlab 優(yōu)化工具箱函數(shù)后，給出一系列輸出變量，提供給用戶相應(yīng)的輸出信息。3. 優(yōu)化參數(shù)優(yōu)化參數(shù)參數(shù)名參數(shù)名 含義含義Derivativecheck對自定義的解析導(dǎo)數(shù)與有限差分導(dǎo)數(shù)進行比較Diagnostics打印進行最小化或求解的診斷信息DiffMaxChange有限差分求導(dǎo)的變量最大變化DiffMinChange有限差分求導(dǎo)的變量最小變化Display值為off時,不顯示輸出;為iter時,顯示迭代信息;為final時,只顯示結(jié)果在新版本中,notify,當函數(shù)不收斂時輸出GoalsE

16、xactAchieve精確達到的目標個數(shù)GradConstr用戶定義的非線性約束的梯度GradObj用戶定義的目標函數(shù)的梯度Hessian用戶定義的目標函數(shù)的Hessian矩陣HessPattern有限差分的Hessian矩陣的稀疏模式HessUpdateHessian矩陣修正結(jié)構(gòu)參數(shù)名參數(shù)名 含義含義Jacobian用戶定義的目標函數(shù)的Jacobian矩陣JacobPattern有限差分的Jacobian矩陣的稀疏模式LargeScale使用大型算法(如果可能的話)Levenberg-Marquardt用Levenberg-Marquardt方法代替Gauss-Newton方法LineSea

17、rchType一維搜索算法的選擇MaxFunEvals允許進行函數(shù)評價的最大次數(shù)MaxIter允許進行迭代的最大次數(shù)MaxPCGIter允許進行PCG迭代的最大次數(shù)MeritFunction使用多目標函數(shù)MinAbsMax最小化最壞個案例絕對值的f(x)的個數(shù)PrecondBandWidthPCG前提的上帶寬TolCon違背約束的終止容限TolFun函數(shù)值的終止容限TolPCGPCG迭代的終止容限TolXX處的終止容限TypicalX典型x值（三）參數(shù)設(shè)置（三）參數(shù)設(shè)置 對于優(yōu)化控制，Matlab 提供了18個參數(shù)。利用optimset 函數(shù)，可以創(chuàng)建和編輯參數(shù)結(jié)構(gòu)；利用optimget 函數(shù)

18、，可以獲得 options 優(yōu)化參數(shù)。這些參數(shù)的具體意義如下：參數(shù)名參數(shù)名 含義含義options(1)參數(shù)顯示控制(默認值為0),等于1時顯示一些結(jié)果options(2)優(yōu)化點x的精度控制(默認值為1e-4)options(3)優(yōu)化函數(shù)F的精度控制(默認值為1e-4)options(4)違反約束的結(jié)束標準(默認值為1e-6)options(5)算法選擇，不常用options(6)優(yōu)化程序方法選擇，為0則為BFCG算法，為1則采用DFP算法options(7)線性插值算法選擇，為0則為混合插值算法，為1則采用立方插值算法options(8)函數(shù)值顯示(多目標規(guī)劃問題中的Lambda)optio

19、ns(9)若需要檢測用戶提供的梯度,則設(shè)為1options(10)函數(shù)和約束估值的數(shù)目options(11)函數(shù)梯度估值的個數(shù)options(12)約束估值的數(shù)目options(13)等式約束條件的個數(shù)options(14)函數(shù)估值的最大次數(shù)(默認值為100變量個數(shù))options(15)用于多目標規(guī)劃問題中的特殊目標options(16)優(yōu)化過程中變量的最小有限差分梯度值options(17)優(yōu)化過程中變量的最大有限差分梯度值options(18)步長設(shè)置(默認為1或更小)1. 參數(shù)值參數(shù)值2. optimset 函數(shù)函數(shù) optimset 函數(shù)的功能是創(chuàng)建或編輯優(yōu)化選項參數(shù)結(jié)構(gòu)。具體的調(diào)用

20、格式為：options=optimset( param1,value1, param2, value2, )options=optimset( oldopts,param1, value1, ) 功能：功能：創(chuàng)建一個稱為options 的優(yōu)化選項參數(shù)，其中指定的參數(shù)具有指定值。所有未指定的參數(shù)都設(shè)置為空矩陣 （將參數(shù)設(shè)置為 表示當options傳遞給優(yōu)化函數(shù)時給參數(shù)賦默認值賦默認值）。賦值時只要輸入?yún)?shù)前面的字母就行了。 功能：功能：創(chuàng)建一個oldopts的復(fù)制，用指定的數(shù)值修改參數(shù)。options=optimset ( oldopts,newopts ) 功能：功能：將已經(jīng)存在的選項結(jié)構(gòu) o

21、ldopts 與新的選項結(jié)構(gòu)newopts 進行合并。 newopts 參數(shù)中的所有元素將覆蓋oldopts 參數(shù)中的所有對應(yīng)元素。optimset 功能：功能：沒有任何輸入輸出參數(shù)，將顯示一張完整的帶有有效值的參數(shù)列表如左：Display: off | on | iter | notify | final MaxFunEvals: positive scalar MaxIter: positive scalar TolFun: positive scalar TolX: positive scalar FunValCheck: off | on OutputFcn: function | B

22、ranchStrategy: mininfeas | maxinfeas DerivativeCheck: on | off Diagnostics: on | off DiffMaxChange: positive scalar | 1e-1 DiffMinChange: positive scalar | 1e-8 GoalsExactAchieve: positive scalar | 0 options=optimset ( with no input arguments ) 功能：功能：創(chuàng)建一個選項結(jié)構(gòu)options，其中所有的元素被設(shè)置為 。optimset( optimfunct

23、ion ) 功能：功能：創(chuàng)建一個含有所有參數(shù)名和與優(yōu)化函數(shù)optimfun相關(guān)的默認值的選項結(jié)構(gòu)options 。options=optimset(Display,iter,TolFun,1e-8)例例1 options = Display: iter MaxFunEvals: MaxIter: TolFun: 1.0000e-008 TolX: FunValCheck: OutputFcn: ActiveConstrTol: BranchStrategy: DerivativeCheck: Diagnostics: DiffMaxChange: DiffMinChange: GoalsExa

24、ctAchieve: optnew=optimset(options,TolX,1e-4)例例2 options = Display: iter MaxFunEvals: MaxIter: TolFun: 1.0000e-008 TolX: 1.0000e-004 FunValCheck: OutputFcn: ActiveConstrTol: BranchStrategy: DerivativeCheck: Diagnostics: DiffMaxChange: DiffMinChange: GoalsExactAchieve: options=optimset(fminbnd)例例3 op

25、tions = Display: notify MaxFunEvals: 500 MaxIter: 500 TolFun: TolX: 1.0000e-004 FunValCheck: off OutputFcn: 返回options優(yōu)化結(jié)構(gòu)，其中包含所有的參數(shù)名和與fminbnd函數(shù)相關(guān)的默認值，結(jié)果如左：optimset fminbnd例例4 若只希望看到fminbnd函數(shù)的默認值，只需要簡單地鍵入上面的語句之一就可以了。其輸出結(jié)果同上例。optimset(fminbnd)或3. optimget 函數(shù)函數(shù) optimget 函數(shù)的功能是獲得options的優(yōu)化參數(shù)。具體的調(diào)用格式為：va

26、l=optimget( options, name )val=optimget ( options, name,default ) 功能：功能：返回優(yōu)化參數(shù)options中指定的參數(shù)的值。只需要用參數(shù)開頭的字母來定義參數(shù)就行了。 功能：功能：若options結(jié)構(gòu)參數(shù)中沒有定義指定參數(shù)，則返回默認值。注意，這種形式的函數(shù)主要用于其它優(yōu)化函數(shù)。 設(shè)置了參數(shù)options后就可以用上述調(diào)用形式完成指定任務(wù)了。val=optimget(options,Display)例例5 val =notifyoptnew=optimget(options,Display,final)例例6 optnew =not

27、ify如果顯示參數(shù)沒有定義，則返回值final。（四）模型輸入時需要注意的問題（四）模型輸入時需要注意的問題 使用優(yōu)化工具箱時，由于優(yōu)化函數(shù)要求目標函數(shù)和約束條件滿足一定的格式，所以需要用戶在進行模型輸入時注意以下幾個問題：1. 目標函數(shù)最小化 優(yōu)化函數(shù)fminbnd、fminsearch、fminunc、fminicon、fgoalattain、fminmax和lsqnonlin都要求目標函數(shù)最小化，如果優(yōu)化問題要求目標函數(shù)最大化，可以通過使該目標函數(shù)的負值最小化即-f (x)最小化來實現(xiàn)。近似地，對于quadprog函數(shù)提供-H和-f，對于linprog函數(shù)提供-f。3.避免使用全局變量2

28、.約束非正 優(yōu)化工具箱要求非線性不等式約束的形式為Ci(x) 0,通過對不等式取負可以達到使大于零的約束形式變?yōu)樾∮诹愕牟坏仁郊s束形式的目的，如 Ci(x) 0形式的約束等價于-Ci(x) 0 ；Ci(x)b形式的約束等價于-Ci(x) +b0。 在Matlab語言中，函數(shù)內(nèi)部定義的變量除特殊聲明外均為局部變量，即不加載到工作空間中。如果需要使用全局變量，則應(yīng)當使用命令global定義，而且在任何時候使用該全局變量的函數(shù)中都應(yīng)該加以定義。在命令窗口中也不例外。當程序比較大時，難免會在無意中修改全局變量的值，因而導(dǎo)致錯誤。更糟糕的是，這樣的錯誤很難查找。因此，在編程時應(yīng)該盡量避免使用全局變量。（

29、五）函數(shù)（五）函數(shù) Matlab6.0以后的版本中可以用函數(shù)進行函數(shù)調(diào)用函數(shù)調(diào)用。函數(shù)返回指定Matlab函數(shù)的句柄，其調(diào)用格式為： handle= function 利用函數(shù)進行函數(shù)調(diào)用的好處：u用句柄將一個函數(shù)傳遞給另一個函數(shù)；u減少定義函數(shù)的文件個數(shù)；u改進重復(fù)操作；u保證函數(shù)計算的可靠性。fhandle=humps;例例7 x = 0.6370 x=fminbnd(fhandle,0,1)為 humps 函數(shù)創(chuàng)建一個函數(shù)句柄，并將它指定為 fhandle 變量。傳遞句柄給另一個函數(shù)，也將傳遞所有變量。x=fminbnd(humps,0,1)x=fminbnd(humps,0,1)或或（

30、六）優(yōu)化算法介紹（六）優(yōu)化算法介紹 參數(shù)優(yōu)化就是求一組設(shè)計參數(shù) x=(x1,x2,xn)，以滿足在某種意義下最優(yōu)。一個簡單的情況就是對某依賴于 x 的問題求極大值或極小值。復(fù)雜一點的情況是欲進行優(yōu)化的目標函數(shù) f (x) 受到以下限定條件：1. 參數(shù)優(yōu)化問題參數(shù)優(yōu)化問題( )0,1,2,iec xim等式約束條件：等式約束條件：不等式約束條件：不等式約束條件：( )0,1,iec ximm 參數(shù)有界約束：參數(shù)有界約束：LbxUb. .( )0,1,2,( )0,1, ,.ieiestc ximc ximmLbxUb這類問題的一般數(shù)學(xué)模型為：min( )nx Rf x 要有效而且精確地解決這類問

31、題，不僅依賴于問題的大小即約束條件和設(shè)計變量的數(shù)目，而且依賴目標函數(shù)和約束條件的性質(zhì)。線性規(guī)劃二次規(guī)劃非線性規(guī)劃能得到可靠的解一般是通過求解線性規(guī)劃、二次規(guī)劃或無約束優(yōu)化的子問題來解決。2. 無約束優(yōu)化問題無約束優(yōu)化問題 搜索法搜索法是對非線性或不連續(xù)問題求解的合適方法，當欲優(yōu)化的函數(shù)具有連續(xù)一階導(dǎo)數(shù)時，梯度法梯度法（一個簡單的方法是沿負梯度方向搜索）一般說來更為有效，高階法高階法（例如Newton法）僅實用于目標函數(shù)的二階信息能計算出來的情況。擬Newton法 在使用梯度信息的方法中，最為有效的方法是擬Newton方法。此方法的實質(zhì)是建立每次迭代的曲率信息，以此來解決如下形式的二次模型問題：

32、1min( )2nTTx Rf xx Hxb xc其中H為目標函數(shù)的Hessian矩陣，H對稱正定，b為常數(shù)向量，c為常數(shù)。最優(yōu)解為：*1.xH b 多項式近似 對應(yīng)于擬Newton法， Newton法法直接計算H，并使用線搜索策略沿下降方向經(jīng)過一定次數(shù)的迭代后確定最小值，為了得到矩陣 H 需要經(jīng)過大量的計算；擬擬Newton法法則不同，它通過使用 f (x)和它的梯度來修正 H 的近似值常用的擬Newton法（ Hessian矩陣修正方法）BFGS方法DFP方法 該法用于目標函數(shù)比較復(fù)雜的情況。在這種情況下尋找一個與它近似的函數(shù)來代替目標函數(shù)，并用近似函數(shù)的極小點作為原函數(shù)極小點的近似。常用

33、的近似函數(shù)為二次多項式和三次多項式。 二次內(nèi)插的一般問題是，在定義域空間給定三個點x1，x2，x3和它們所對應(yīng)的函數(shù)值 f (x1)，f (x2)，f (x3)，由二階匹配得出最小值點如下：u 二次內(nèi)插2313121231231312123()()()12()()()kf xf xf xxf xf xf x極值點：二次函數(shù)：此點可能是最小值或最大值點。當執(zhí)行內(nèi)插或a為正時是最小值。只要利用三個梯度或者函數(shù)方程組即可確定系數(shù)a和b，從而可確定x*。得到該值以后，進行搜索區(qū)間的收縮。22, , 2,3,3,1,1,2ijijijijxxxxi j2( )f xaxbxc*2bxa 其中 三次插值的

34、基本思想和二次插值一致，它是用用4個已知個已知點點構(gòu)造一個三次多項式來逼近目標函數(shù)，同時以三次多項式的極小點作為目標函數(shù)極小點的近似。u 三次插值 三次插值法需要計算目標函數(shù)的導(dǎo)數(shù)，優(yōu)點是計算速度快。同類的方法還有Newton切線法、對分法、割線法等。優(yōu)化工具箱中使用的比較多的是三次插值法。 二次插值法的計算速度比黃金分割搜索法快，但是對于一些強烈扭曲或者可能多峰的函數(shù)，這種方法的收斂速度變得很慢，甚至失敗。 一般來講，三次插值法比二次插值法的收斂速度快，但是每次迭代需要計算兩個導(dǎo)數(shù)值。 如果導(dǎo)數(shù)容易求得，一般來說首先考慮使用三次插值法，因為它具有較高的效率，對于只需要計算函數(shù)值的方法中，二次

35、插值是一個很好的方法，它的收斂速度較快，在極小點所在的區(qū)間較小時尤其如此。黃金分割法是一種十分穩(wěn)定的方法，并且計算簡單。由于上述原因， Matlab優(yōu)化工具箱中較多地使用二次插值法、三次插值法以及二優(yōu)化工具箱中較多地使用二次插值法、三次插值法以及二次三次混合插值法和黃金分割法次三次混合插值法和黃金分割法。三次插值法的迭代公式為：12112121222112( )()( )()3,( )()f xf xf xf xxxf xf x其中2211221212()()()()2kf xxxxxf xf x3. 擬擬Newton法實現(xiàn)法實現(xiàn) 在函數(shù) fminunc 中使用擬 Newton 法，算法的實現(xiàn)

36、過程包括兩個階段：確定搜索方向 搜索方向的選擇由選擇 BFGS 方法還是選擇 DFP 方法來決定，在優(yōu)化工具箱中，通過將 options 參數(shù) HessUpdate設(shè)置為 BFGS 或 DFP 來確定搜索方向。 Hessian 矩陣 H 總是保持正定的，使得搜索方向總是保持為下降方向。這意味著，對于任意小的步長，在上述搜索方向上目標函數(shù)值總是減小的。只要 H 的初始值為正定并且計算出的 qkTsk 總是正的，則 H 的正定性得到保證。并且只要執(zhí)行足夠精度的線性搜索， qkTsk 為正的條件總能得到滿足。 要確定搜索方向首先必須完成 Hessian 矩陣的修正。Newton 法由于需要多次計算

37、Hessian 矩陣，所以計算量很大。擬 Newton 法通過構(gòu)建一個 Hessian 矩陣的近似矩陣來避開這個問題。線性（一維）搜索過程 另外，在三次插值法中，每一個迭代周期都要進行梯度和函數(shù)的計算。 在優(yōu)化工具箱中有兩種線性搜索方法可以使用，這取決于梯度信息是否可以得到。當梯度值可以直接得到時，默認情況下使用三次多項式方法；當梯度值不能直接得到時，默認情況下，采用混合二次和三次插值法。4. 最小二乘優(yōu)化最小二乘優(yōu)化 前面介紹了函數(shù) fminunc 中使用的是在擬 Newton 法中介紹的線性搜索法，在最小二乘優(yōu)化程序 lsqnonlin 中也部分地使用這一方法。最小二乘問題的優(yōu)化描述如下：

38、 在實際應(yīng)用中，特別是數(shù)據(jù)擬合時存在大量這種類型的問題，如非線性參數(shù)估計等?？刂葡到y(tǒng)中也經(jīng)常會遇到這類問題，如希望系統(tǒng)輸出的 y (x,t) 跟蹤某一個連續(xù)的期望軌跡，這個問題可以表示為：212min( ( , )( )tty x ttdt1( )( )( )2minnTx Rf xr xr x21min( )( ( , )( )( )( )mTiiiF xy x ttr xr x將問題離散化得到： 最小二乘問題的梯度和 Hessian 矩陣具有特殊的結(jié)構(gòu)，定義 r (x)的 Jacobian 矩陣為J(x)，則 F (x)的梯度和F(x) 的Hessian 矩陣定義為：其中1( )( )(

39、)miiiQ xr x H x( )2 ( )( )( )2 ( )( )2 ( )TTF xJ xr xH xJ xJ xQ x22min()()kkkJ x dr xGaussNewton法 在GaussNewton法中，每個迭代周期均會得到搜索方向d。它是最小二乘問題的一個解。GaussNewton法用來求解如下問題： 當Q(x)很大時，GaussNewton法很難得到問題的解，在這種情況下，LevenbergMarquadt方法顯得更有效。()()()()TTkkkkkkJ xJ xI dJ xr x LevenbergMarquadt法 LevenbergMarquadt法使用的搜索

40、方向是一組線性等式的解：5. 非線性最小二乘實現(xiàn)非線性最小二乘實現(xiàn)GaussNewton實現(xiàn) GaussNewton法是用前面求無約束問題中討論過的多項式線性搜索策略來實現(xiàn)的。使用Jacobian矩陣的QR分解，可以避免在求解線性最小二乘問題中等式條件惡化的問題。 這種方法中包含一項魯棒性檢測技術(shù)，這種技術(shù)步長低于限定值或當Jacobian矩陣的條件數(shù)很小時，將改為使用LevenbergMarquadt法。 這種實現(xiàn)方法在大量非線性問題中得到了成功的應(yīng)用，并被證明比GaussNewton法具有更好的魯棒性，比無約束條件方法具有更好的迭代效率。在使用lsqnonlin函數(shù)時，函數(shù)所使用的默認算法

41、是LevenbergMarquadt法。當options(5)=1時，使用GaussNewton法。LevenbergMarquadt實現(xiàn) 實現(xiàn)LevenbergMarquadt方法的主要困難是在每一次迭代中如何控制的大小的策略問題，這種控制可以使它對于寬譜問題有效。這種實現(xiàn)的方法是使用線性預(yù)測平方總和和最小函數(shù)值的三次插值估計，來估計目標函數(shù)的相對非線性，用這種方法的大小在每一次迭代中都能確定。6. 約束優(yōu)化約束優(yōu)化 在約束最優(yōu)化問題中，一般方法是先將問題變換為較容易的子問題，然后再求解。前面所述方法的一個特點是可以用約束條件的罰函數(shù)將約束優(yōu)化問題轉(zhuǎn)化為基本的無約束優(yōu)化問題，按照這種方法，條

42、件極值問題可以通過參數(shù)化為無約束優(yōu)化序列來求解。但這些方法效率不高，目前已經(jīng)被通過求解求解KuhnTucker方程方程的方法所取代。 KuhnTucker方程是條件極值問題的必要條件必要條件。如果欲解決的問題是所謂的凸規(guī)劃問題，那么KuhnTucker方程有解是極值問題有全局解的充分必要條件。 求解KuhnTucker方程是很多非線性規(guī)劃算法的基礎(chǔ)，這些方法試圖直接計算Lagrange乘子。因為在每一次迭代中都要求解一次QP子問題，這些方法一般又被稱為逐次逐次（或序列）二次規(guī)劃（或序列）二次規(guī)劃（SQP）方法）方法。這個問題可以通過任何求解二次規(guī)劃問題的算法求解。 使用序列二次規(guī)劃方法，非線性

43、約束條件的極值問題經(jīng)常可以比無約束優(yōu)化問題用更少的迭代得到解。造成這種現(xiàn)象的一個原因是：受到可行域的限制，這種方法更可能得到恰當?shù)乃阉鞣较蚝偷介L。1( , )( )( )miiiL xf xc x 給定一個約束最優(yōu)化問題，求解的基本思想是基于Lagrange函數(shù)的二次近似求解二次規(guī)劃子問題：1min()2TTkkd H df xd從而得到二次規(guī)劃子問題：. .( )( )0,1,( )( )0,1, .TiieTiiestc xdc xiEmc xdc xiImm7. SQP實現(xiàn)實現(xiàn) 在每一次迭代中，均作Lagrange函數(shù)的Hessian矩陣的正定擬Newton 近似，通過BFGS方法進

44、行計算。Matlab工具箱的SQP實現(xiàn)由三個部分組成：u修正Lagrange函數(shù)的Hessian矩陣u二次規(guī)劃問題求解u線性搜索修正Hessian矩陣用BFGS公式修正Hessian矩陣：（略） 此算法要求有一個合適的初始值，如果由逐次二次規(guī)劃方法得到的當前計算點是不合適的，則通過求解下述線性規(guī)劃問題可以得到合適的計算點：如果上述問題存在要求的點，就可以通過將 x 賦值為滿足等式條件的值來得到。求解二次規(guī)劃問題初始化 在逐次二次規(guī)劃方法中，每一次迭代都要解一個二次規(guī)劃問題：. .s tAxbAeq xbeq1min2TTxx H xfx. .s tAxbAeq xbeq,minnR x R三、

45、無約束優(yōu)化問題三、無約束優(yōu)化問題（一）一維優(yōu)化問題（一）一維優(yōu)化問題1. 數(shù)學(xué)原理及模型數(shù)學(xué)原理及模型 一般的優(yōu)化問題，因受多種因素的影響與制約，目標函數(shù)一般都是多元函數(shù)，稱為多維優(yōu)化問題。求解多維優(yōu)化問題，常?；癁橹鸩降难啬骋环较蚯髥卧瘮?shù)的極值問題，也就是一維搜索問題，在這里稱為一維優(yōu)化問題。一維搜索方法的好壞直接影響到優(yōu)化算法的求解速度。 一維搜索的直接目的是尋求單變量函數(shù)的極小點，在理論上，一維搜索主要是作為求多變量函數(shù)的極小點的手段而進行研究的。然而，在實際應(yīng)用中，很多問題都需要直接使用一維搜索的方法，如工程中常見的參數(shù)反演問題。應(yīng)該指出，所選用的一維搜索方法是否得當，常常對于整個計

46、算的進程的影響極大。u 數(shù)學(xué)模型一維優(yōu)化問題的數(shù)學(xué)模型為： 對于一維優(yōu)化問題來說，由于問題本身比較簡單，可選擇的方法也比較多。比較經(jīng)典的方法有：進退法、Fibonacci法（也叫分數(shù)法）、黃金分割法（也叫0.618法）、試位法以及各種插值法。一般來說，對于形態(tài)比較好、比較光滑的函數(shù)可以使用插值法插值法，這樣可以較快地逼近極小點；而對于形態(tài)比較差的函數(shù)，則可以使用黃金分黃金分割法割法。這也是Matlab優(yōu)化工具箱中的庫函數(shù)使用的兩種方法。u 算法介紹12min( ),x Rf xxxx2. Matlab工具箱中的基本函數(shù)工具箱中的基本函數(shù) 在Matlab中，一維優(yōu)化問題，也就是一維搜索問題的一維

47、搜索問題的實現(xiàn)是由函數(shù)實現(xiàn)是由函數(shù)fminbnd來實現(xiàn)的來實現(xiàn)的。 應(yīng)當注意：該函數(shù)所求的目標函數(shù)必須是連續(xù)的，并且只用于實數(shù)變量。同時該函數(shù)只能給出目標函數(shù)的局部最優(yōu)解。對于問題的解位于區(qū)間邊界上的情況，此函數(shù)收斂速度非常慢。具體的調(diào)用格式如下：x=fminbnd( fun，x1，x2 ) 功能：功能：返回在區(qū)間(x1，x2)中標量函數(shù)fun的最小值點。x=fminbnd( fun，x1，x2，options ) 功能：功能： 用options參數(shù)指定的優(yōu)化參數(shù)進行最小化，其中， options可取值為： Display ，TolX，MaxFunEval，MaxIter，F(xiàn)unValChec

48、k，和OutputFcn。options參數(shù)參數(shù) 含義含義Display顯示的水平：為off時，不顯示輸出；為iter時，顯示每一步迭代輸出；為final時，顯示最終結(jié)果。TolX在點x處的終止容限MaxFunEval函數(shù)評價的最大允許次數(shù)MaxIter最大允許迭代次數(shù)FunValCheck檢查非法函數(shù)值OutputFcn可加載輸出函數(shù)名options 參數(shù)各個取值的含義如下表所示：x，fval =fminbnd( ) 功能：功能：同時返回解x和在點x處的目標函數(shù)值。exitflag值值 含義含義 1函數(shù)收斂到目標函數(shù)最優(yōu)解處 0達到最大迭代次數(shù)或達到函數(shù)評價 -1算法由輸出函數(shù)終止 -2下界

49、大于上界exitflag值和相應(yīng)的含義如下表所示：x，fval，exitflag=fminbnd( ) 功能：功能：同時返回解 x 和在點 x 處的目標函數(shù)值。另外，返回 exitflag 值，描述極小化函數(shù)的退出條件。output結(jié)構(gòu)值結(jié)構(gòu)值含義含義output.iterations迭代次數(shù)output.funcCount函數(shù)評價次數(shù)output.algorithm所用的算法output包含的內(nèi)容和相應(yīng)的含義如下表所示：x，fval，exitflag，output=fminbnd( ) 功能：功能：返回同上述格式的值。另外，返回包含output結(jié)構(gòu)的輸出。例例8 fminbnd 演示。x=f

50、minbnd(cos,3,4)x = 3.1416x,fval,exitflag=fminbnd(cos,3,4,optimset(TolX,1e-12, Display,off)x = 3.1416fval = -1exitflag =1例例9 求函數(shù) f (x)=(x-4)2-5在區(qū)間(0,6)內(nèi)的最小值。function f=ex9(x)f=(x-4)2-5 2;編輯目標函數(shù)的 M 文件 ex9.m ：x,fval=fminbnd(ex9,0,6)x = 4fval = -5在命令窗口中輸入：例例10 帶參數(shù)優(yōu)化問題。function f=ex10(x,a)%This function

51、is to demonstrate minimize the objective%given in the function which is parameterized by its second% argument a f=(x-a)2;編輯如下 M 文件 ex10.m ：a=1.5; %define parameter first x=fminbnd(x) ex10(x,a),0,1)x = 0.9999在命令窗口中輸入：3. 應(yīng)用實例分析應(yīng)用實例分析function f=ex11(x)%The purpose of this file is to give the objective

52、function %This is a function to calculate the volumef=-(5-2*x).2*x;編輯如下 M 文件 ex11.m ：例例11 容積最大化問題。對邊長為 5m 的正方形鋼板，在 4 個角處剪去相等的正方形以制成方形無蓋的容器，問如何剪去使得容器的容積最大？假設(shè)剪去的正方形的邊長為 x，則容器的容積計算公式為：xxxg2)25()(xxxf2)25()(這里需要將最大化問題轉(zhuǎn)化為最小化問題，目標函數(shù)為：x,fval,exitflag,output=fminbnd(ex11,0,1.5)x = 0.8333fval = -9.2593exitfl

53、ag = 1output = iterations: 8 funcCount: 9 algorithm: golden section search, parabolic interpolation message: 1x112 char在命令窗口中輸入：（二）無約束非線性規(guī)劃問題（二）無約束非線性規(guī)劃問題1. 數(shù)學(xué)原理及模型數(shù)學(xué)原理及模型 無約束最優(yōu)化是一個十分古老的課題，至少可以追溯到 Newton 發(fā)明微積分的時代。無約束最優(yōu)化問題在實際應(yīng)用中也非常常見，另外，許多約束優(yōu)化問題也可以轉(zhuǎn)化成無約束優(yōu)化問題求解，所以，無約束優(yōu)化問題還是十分重要的。 由于簡單的無約束線性問題非常容易，這里提到

54、的無約束最優(yōu)化問題就是指無約束非線性規(guī)劃問題。u 數(shù)學(xué)模型 設(shè) f (x)是一個定義在 n 維歐式空間上的函數(shù)。把尋找f (x)的極小點的問題稱為一個無約束最優(yōu)化問題，這個問題可以用下列形式表示：12min( ),( ,)Tnnf xxx xxRu 算法介紹u最速下降法：適用于變量不多的問題；uNewton法u變尺度法(也稱為擬Newton法)u信賴域方法uPowell直接方法u共軛梯度法 直接搜索法 直接搜索法適用于目標函數(shù)高度非線性，沒有導(dǎo)數(shù)適用于目標函數(shù)高度非線性，沒有導(dǎo)數(shù)或?qū)?shù)很難計算的情況或?qū)?shù)很難計算的情況，由于實際工程中很多問題都是非線性的，直接搜索法不失為一種有效的解決辦法。常

55、用的直接搜索法為單純形法，其缺點是收斂速度慢。 在函數(shù)的導(dǎo)數(shù)可求函數(shù)的導(dǎo)數(shù)可求的情況下，梯度法是一種更優(yōu)的方法，該法利用函數(shù)的梯度（一階導(dǎo)數(shù)）和Hessian矩陣（二階導(dǎo)數(shù)）構(gòu)造算法，可以獲得更快的收斂速度。函數(shù) f (x)的負梯度方向- f (x)即反映了函數(shù)的最大下降方向。當搜索方向取為負梯度方向時稱為最速下降法。當需要最小化的函數(shù)有一狹長的谷形值域時，該法的效率很低。 常用的梯度法有最速下降法、Newton 法、Marquadt法、共軛梯度法和擬 Newton 法等。 梯度法u Hessian矩陣的修正l 確定搜索方向l 一維搜索階段 在所有這些方法中，用得最多的是擬擬Newton法法。

56、擬Newton法包括兩個階段，即 Newton法由于需要多次計算Hessian矩陣，計算量很大，而擬Newton法則通過構(gòu)建一個Hessian矩陣的近似矩陣來避開這個問題。 在優(yōu)化工具箱中，通過將options參數(shù) HessUpdate設(shè)置為 BFGS或DFP來決定搜索方向。 當Hessian矩陣H始終保持正定的，搜索方向就總是保持為下降方向。 Hessian矩陣的修正方法很多，對于求解一般問題， BFGS法是最有效的。 另一個有名的方法是DFP法。作為初值， H0可以設(shè)為任意對稱正定矩陣。u 一維搜索 若用戶在fun函數(shù)中提供梯度信息，則缺省時函數(shù)將選擇大型優(yōu)化算法，該算法是基于內(nèi)部映射Ne

57、wton法的子空間置信域法。計算中的每一次迭代涉及到用PCG法求解大型線性系統(tǒng)得到的近似解。 工具箱中有兩套方案進行一維搜索。當梯度值可以直接得到時，用三次插值的方法進行一維搜索，當梯度值不能直接得到時，采用二次、三次混合插值法。Matlab的庫函數(shù)中使用的方法為變尺度法和信賴域方法。大型優(yōu)化算法：大型優(yōu)化算法： 缺省時的一維搜索算法，當options.LineSearchType 設(shè)置為quadcubic時，將采用二次和三次混合插值法。將options.LineSearchType 設(shè)置為cubicpoly時，將采用三次插值法。第二種方法需要的目標函數(shù)計算次數(shù)更少，但梯度的計算次數(shù)更多。這樣

58、，如果提供了梯度信息，或者能較容易地算得，則三次插值法是更佳的選擇。中型優(yōu)化算法：中型優(yōu)化算法： 此時fminunc函數(shù)的參數(shù)options.LargeScale設(shè)置為off。該算法采用的是基于二次和三次混合插值一維搜索法的BFGS擬Newton法。該法通過BFGS公式來修正Hessian矩陣。通過將HessUpdate參數(shù)設(shè)置為dfp，可以用DFP公式來求得Hessian矩陣逆的近似。通過將HessUpdate參數(shù)設(shè)置為steepdesc，可以用最速下降法來更新Hessian矩陣。但一般不建議使用最速下降法。2. Matlab工具箱中的基本函數(shù)工具箱中的基本函數(shù) 在Matlab優(yōu)化工具箱函數(shù)

59、中，有以下兩個函數(shù)用來求解上述問題。 fminunc、fminsearch具體的調(diào)用格式如下：x= fminunc( fun，x0 ) 功能：功能：給定起始點x0，求函數(shù)fun的局部極小點x。其中， x0 可以是一個標量、向量或者矩陣。 fminuncx= fminunc( fun，x0，options ) 功能：功能：用options參數(shù)指定的優(yōu)化參數(shù)進行最小化，其中， options可取值為：Display，TolX，TolFun，Derivativecheck，Diagnostics，F(xiàn)unValCheck，GradObj，HessPattern， Hessian，HessMult，He

60、ssUpdate，InitialHessType，InitialHessMatrix，MaxFunEvals， MaxIter， DiffMinChange和DiffMaxChange， TypicalX ， LargeScale，MaxPCGIter， PrecondBandWidth， TolPCGx，fval= fminunc( fun，x0， ) 功能：功能：同時返回解x和在點x處的目標函數(shù)值。x，fval ，exitflag= fminunc( fun，x0， ) 功能：功能：同時返回解x和在點x處的目標函數(shù)值。另外，返回exitflag值，描述極小化函數(shù)的退出條件。exitflag