Matlab的優(yōu)化工具箱

1、9.1概述利用 Matlab 的優(yōu)化工具箱，可以求解線性規(guī)劃、非線性規(guī)劃和多目標(biāo)規(guī)劃問題。具體而言，包括線性、非線性最小化，最大最小化，二次規(guī)劃，半無限問題，線性、非線性方程（組）的求解，線性、非線性的最小二乘問題。另外，該工具箱還提供了線性、非線性最小化，方程求解，曲線擬合，二次規(guī)劃等問題中大型課題的求解方法，為優(yōu)化方法在工程中的實(shí)際應(yīng)用提供了更方便快捷的途徑。優(yōu)化工具箱中的函數(shù)優(yōu)化工具箱中的函數(shù)包括下面幾類：最小化函數(shù)表 9-1最小化函數(shù)表函數(shù)描述fgoalattain多目標(biāo)達(dá)到問題fminbnd有邊界的標(biāo)量非線性最小化fmincon有約束的非線性最小化fminimax最大最小化fmins

2、earch, fminunc無約束非線性最小化fseminf半無限問題linprog線性課題quadprog二次課題2方程求解函數(shù)表 9-2方程求解函數(shù)表函數(shù)描述線性方程求解fsolve非線性方程求解fzero標(biāo)量非線性方程求解3最小二乘（曲線擬合）函數(shù)表 9-3最小二乘函數(shù)表函數(shù)描述線性最小二乘lsqlin有約束線性最小二乘lsqcurvefit非線性曲線擬合lsqnonlin非線性最小二乘lsqnonneg非負(fù)線性最小二乘4實(shí)用函數(shù)表 9-4實(shí)用函數(shù)表函數(shù)描述optimset設(shè)置參數(shù)optimget大型方法的演示函數(shù)表 9-5大型方法的演示函數(shù)表函數(shù)描述circustentmolecule

3、optdeblur馬戲團(tuán)帳篷問題二次課題用無約束非線性最小化進(jìn)行分子組成求解用有邊界線性最小二乘法進(jìn)行圖形處理6中型方法的演示函數(shù)表 9-6中型方法的演示函數(shù)表函數(shù)描述bandemodfildemogoaldemooptdemotutdemo香蕉函數(shù)的最小化過濾器設(shè)計的有限精度目標(biāo)達(dá)到舉例演示過程菜單教程演示參數(shù)設(shè)置利用optimset函數(shù)，可以創(chuàng)建和編輯參數(shù)結(jié)構(gòu)；利用optimget函數(shù)，可以獲得 options優(yōu)化參數(shù)。optimget 函數(shù)功能：獲得 options優(yōu)化參數(shù)。語法：val = optimget(options,param)val = optimget(options,pa

4、ram,default)描述：val = optimget(options,param)返回優(yōu)化參數(shù) options中指定的參數(shù)的值。只需要用參數(shù)開頭的字母來定義參數(shù)就行了。val = optimget(options,param,default)若 options結(jié)構(gòu)參數(shù)中沒有定義指定參數(shù)，則返回缺省值。注意，這種形式的函數(shù)主要用于其它優(yōu)化函數(shù)。舉例：1下面的命令行將顯示優(yōu)化參數(shù)options返回到 my_options 結(jié)構(gòu)中：val = optimget(my_options,Display)2 下面的命令行返回顯示優(yōu)化參數(shù) options 到 my_options 結(jié)構(gòu)中（就象前面的例

5、子一樣），但如果顯示參數(shù)沒有定義，則返回值 final:optnew = optimget(my_options,Display,final); 參見：optimsetoptimset 函數(shù)功能：創(chuàng)建或編輯優(yōu)化選項參數(shù)結(jié)構(gòu)。語法：options = optimset(param1,value1,param2,value2,.)optimsetoptions = optimsetoptions = optimset(optimfun)options = optimset(oldopts,param1,value1,.)options = optimset(oldopts,newopts)描述：o

6、ptions = optimset(param1,value1,param2,value2,.)創(chuàng)建一個稱為options 的優(yōu)化選項參數(shù)，其中指定的參數(shù)具有指定值。所有未指定的參數(shù)都設(shè)置為空矩陣 （將參數(shù)設(shè)置為 表示當(dāng) options 傳遞給優(yōu)化函數(shù)時給參數(shù)賦缺省值）。賦值時只要輸入?yún)?shù)前面的字母就行了。optimset函數(shù)沒有輸入輸出變量時， 將顯示一張完整的帶有有效值的參數(shù)列表。options = optimset (with no input arguments)創(chuàng)建一個選項結(jié)構(gòu) options ，其中所有的元素被設(shè)置為 。options = optimset(optimfun)創(chuàng)建一

7、個含有所有參數(shù)名和與優(yōu)化函數(shù)optimfun 相關(guān)的缺省值的選項結(jié)構(gòu)options 。options = optimset(oldopts,param1,value1,.)創(chuàng)建一個 oldopts的拷貝，用指定的數(shù)值修改參數(shù)。options = optimset(oldopts,newopts)將已經(jīng)存在的選項結(jié)構(gòu) oldopts與新的選項結(jié)構(gòu) newopts 進(jìn)行合并。 newopts 參數(shù)中的所有元素將覆蓋 oldopts參數(shù)中的所有對應(yīng)元素。舉例：1下面的語句創(chuàng)建一個稱為options的優(yōu)化選項結(jié)構(gòu)，其中顯示參數(shù)設(shè)為iter， TolFun 參數(shù)設(shè)置為 1e-8:options = op

8、timset(Display,iter,TolFun,1e-8)下面的語句創(chuàng)建一個稱為 options 的優(yōu)化結(jié)構(gòu)的拷貝， 改變 TolX 參數(shù)的值，將新值保存到 optnew 參數(shù)中 :optnew = optimset(options,TolX,1e-4);下面的語句返回 options 優(yōu)化結(jié)構(gòu)，其中包含所有的參數(shù)名和與 fminbnd 函數(shù)相關(guān)的缺省值：options = optimset(fminbnd)若只希望看到 fminbnd 函數(shù)的缺省值，只需要簡單地鍵入下面的語句就行了：optimset fminbnd或者輸入下面的命令，其效果與上面的相同： optimset(fminbn

9、d)參見： optimget模型輸入時需要注意的問題使用優(yōu)化工具箱時，由于優(yōu)化函數(shù)要求目標(biāo)函數(shù)和約束條件滿足一定的格式，所以需要用戶在進(jìn)行模型輸入時注意以下幾個問題：目標(biāo)函數(shù)最小化優(yōu)化函數(shù) fminbnd 、fminsearch 、fminunc 、fmincon 、fgoalattain、fminmax和 lsqnonlin 都要求目標(biāo)函數(shù)最小化， 如果優(yōu)化問題要求目標(biāo)函數(shù)最大化， 可以通過使該目標(biāo)函數(shù)的負(fù)值最小化即 -f(x) 最小化來實(shí)現(xiàn)。近似地，對于 quadprog函數(shù)提供 -H 和-f ，對于 linprog函數(shù)提供 -f 。約束非正優(yōu)化工具箱要求非線性不等式約束的形式為Ci (x

10、) 0，通過對不等式取負(fù)可以達(dá)到使大于零的約束形式變?yōu)樾∮诹愕牟坏仁郊s束形式的目的，如 Ci (x) 0 形式的約束等價于 - C i (x) 0； Ci (x) b形式的約束等價于 - C i (x)+b 0。避免使用全局變量（函數(shù)句柄）函數(shù)MATLAB6.0 中可以用 函數(shù)進(jìn)行函數(shù)調(diào)用。 函數(shù)返回指定 MATLAB函數(shù)的句柄，其調(diào)用格式為：handle = function利用 函數(shù)進(jìn)行函數(shù)調(diào)用有下面幾點(diǎn)好處：用句柄將一個函數(shù)傳遞給另一個函數(shù)；減少定義函數(shù)的文件個數(shù)；改進(jìn)重復(fù)操作；保證函數(shù)計算的可靠性。下面的例子為 humps函數(shù)創(chuàng)建一個函數(shù)句柄，并將它指定為fhandle 變量。fhan

11、dle = humps;同樣傳遞句柄給另一個函數(shù)，也將傳遞所有變量。本例將剛剛創(chuàng)建的函數(shù)句柄傳遞給 fminbnd 函數(shù)，然后在區(qū)間 0.3,1 上進(jìn)行最小化。x = fminbnd (humps, 0.3, 1)x =0.63709.2最小化問題單變量最小化基本數(shù)學(xué)原理本節(jié)討論只有一個變量時的最小化問題，即一維搜索問題。該問題在某些情況下可以直接用于求解實(shí)際問題， 但大多數(shù)情況下它是作為多變量最優(yōu)化方法的基礎(chǔ)在應(yīng)用，因?yàn)檫M(jìn)行多變量最優(yōu)化要用到一維搜索法。該問題的數(shù)學(xué)模型為：其中， x, x1, 和 x2 為標(biāo)量， f ( x) 為函數(shù)，返回標(biāo)量。該問題的搜索過程可用下式表達(dá)：其中 xk 為本

12、次迭代的值， d 為搜索方向， 為搜索方向上的步長參數(shù)。所以一維搜索就是要利用本次迭代的信息來構(gòu)造下次迭代的條件。求解單變量最優(yōu)化問題的方法有很多種，根據(jù)目標(biāo)函數(shù)是否需要求導(dǎo)，可以分為兩類，即直接法和間接法。 直接法不需要對目標(biāo)函數(shù)進(jìn)行求導(dǎo)， 而間接法則需要用到目標(biāo)函數(shù)的導(dǎo)數(shù)。1直接法常用的一維直接法主要有消去法和近似法兩種。（1）消去法 該法利用單峰函數(shù)具有的消去性質(zhì)進(jìn)行反復(fù)迭代，逐漸消去不包含極小點(diǎn)的區(qū)間，縮小搜索區(qū)間，直到搜索區(qū)間縮小到給定的允許精度為止。一種典型的消去法為黃金分割法 (Golden Section Search) 。黃金分割法的基本思想是在單峰區(qū)間內(nèi)適當(dāng)插入兩點(diǎn)， 將區(qū)

13、間分為三段， 然后通過比較這兩點(diǎn)函數(shù)值的大小來確定是刪去最左段還是最右段， 或同時刪去左右兩段保留中間段。 重復(fù)該過程使區(qū)間無限縮小。插入點(diǎn)的位置放在區(qū)間的黃金分割點(diǎn)及其對稱點(diǎn)上，所以該法稱為黃金分割法。該法的優(yōu)點(diǎn)是算法簡單，效率較高，穩(wěn)定性好。（2）多項式近似法 該法用于目標(biāo)函數(shù)比較復(fù)雜的情況。此時尋找一個與它近似的函數(shù)代替目標(biāo)函數(shù)，并用近似函數(shù)的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似。常用的近似函數(shù)為二次和三次多項式。二次內(nèi)插涉及到形如下式的二次函數(shù)數(shù)據(jù)擬合問題：其中步長極值為：然后只要利用三個梯度或函數(shù)方程組就可以確定系數(shù)a 和 b，從而可以確定*。得到該值以后，進(jìn)行搜索區(qū)間的收縮。在縮短的新區(qū)間

14、中，重新安排三點(diǎn)求出下一次的近似極小點(diǎn) * ，如此迭代下去，直到滿足終止準(zhǔn)則為止。其迭代公式為：其中二次插值法的計算速度比黃金分割法的快， 但是對于一些強(qiáng)烈扭曲或可能多峰的函數(shù)，該法的收斂速度會變得很慢，甚至失敗。2間接法間接法需要計算目標(biāo)函數(shù)的導(dǎo)數(shù)， 優(yōu)點(diǎn)是計算速度很快。 常見的間接法包括牛頓切線法、 對分法、割線法和三次插值多項式近似法等。 優(yōu)化工具箱中用得較多的是三次插值法。三次插值的基本思想與二次插值的一致， 它是用四個已知點(diǎn)構(gòu)造一個三次多項式 P3(x) ，用它逼近函數(shù) f(x) ，以 P3(x) 的極小點(diǎn)作為 f(x) 的近似極小點(diǎn)。一般講，三次插值法比二次插值法的收斂速度要快些，

15、 但每次迭代需要計算兩個導(dǎo)數(shù)值。三次插值法的迭代公式為其中如果函數(shù)的導(dǎo)數(shù)容易求得， 一般來說首先考慮使用三次插值法， 因?yàn)樗哂休^高的效率。對于只需要計算函數(shù)值的方法中，二次插值法是一個很好的方法，它的收斂速度較快， 尤其在極小點(diǎn)所在區(qū)間較小時尤其如此。 黃金分割法則是一種十分穩(wěn)定的方法，并且計算簡單。由于以上原因， Matlab 優(yōu)化工具箱中使用得較多的方法是二次插值法、 三次插值法、二次、三次混合插值法和黃金分割法。相關(guān)函數(shù)介紹fminbnd功能：找到固定區(qū)間內(nèi)單變量函數(shù)的最小值。語法：x = fminbnd(fun,x1,x2)x = fminbnd(fun,x1,x2,options)

16、x = fminbnd(fun,x1,x2,options,P1,P2,.)x,fval = fminbnd(.)x,fval,exitflag = fminbnd(.)x,fval,exitflag,output = fminbnd(.)描述：fminbnd 求取固定區(qū)間內(nèi)單變量函數(shù)的最小值。x = fminbnd(fun,x1,x2) 返回區(qū)間 x1 ， x2 上 fun 參數(shù)描述的標(biāo)量函數(shù)的最小值x。x = fminbnd(fun,x1,x2,options)用 options參數(shù)指定的優(yōu)化參數(shù)進(jìn)行最小化。x = fminbnd(fun,x1,x2,options,P1,P2,.)提供另

17、外的參數(shù) P1,P2 等, 傳輸給目標(biāo)函數(shù) fun 。如果沒有設(shè)置options選項，則令 options=。x,fval = fminbnd(.)返回解 x 處目標(biāo)函數(shù)的值。x,fval,exitflag = fminbnd(.)返回 exitflag值描述 fminbnd 函數(shù)的退出條件。x,fval,exitflag,output = fminbnd(.)返回包含優(yōu)化信息的結(jié)構(gòu)輸出。變量：函數(shù)的輸入變量在表9-7 中進(jìn)行描述，輸出變量在表函數(shù)相關(guān)的細(xì)節(jié)內(nèi)容包含在fun,options,exitflag9-10 所示。9-8 中描述。與 fminbnd和 output等參數(shù)中，如表表 9-

18、10參數(shù)描述表參數(shù)描述需要最小化的目標(biāo)函數(shù)。 fun 將 fun 函數(shù)指定為命令行，如函數(shù)需要輸入標(biāo)量參數(shù)x ，返回x 處的目標(biāo)函數(shù)標(biāo)量值f ?？梢詘 = fminbnd(inline(sin(x*x),x0)fun同樣， fun 文件。若參數(shù)可以是一個包含函數(shù)名的字符串。對應(yīng)的函數(shù)可以是fun=myfun，則 M文件函數(shù)myfun.m 必須右下面的形式。M文件、內(nèi)部函數(shù)或MEXfunction f = myfun(x)f = .%計算x 處的函數(shù)值。優(yōu)化參數(shù)選項。你可以用optimset函數(shù)設(shè)置或改變這些參數(shù)的值。options參數(shù)有以下幾個選項：Display 顯示的水平。選擇 off ，

19、不顯示輸出；選擇 iter ，顯示每一步迭代過程options的輸出；選擇 final，顯示最終結(jié)果。MaxFunEvals 函數(shù)評價的最大允許次數(shù)。MaxIter 最大允許迭代次數(shù)。TolX x 處的終止容限。描述退出條件 :0表示目標(biāo)函數(shù)收斂于解x 處。exitflag表示已經(jīng)達(dá)到函數(shù)評價或迭代的最大次數(shù)。0表示目標(biāo)函數(shù)不收斂。該參數(shù)包含下列優(yōu)化信息：output.iterations 迭代次數(shù)。outputoutput.algorithm 所采用的算法。output.funcCount 函數(shù)評價次數(shù)。算法：fminbnd 是一個 M文件。其算法基于黃金分割法和二次插值法。文獻(xiàn)了實(shí)現(xiàn)同樣算

20、法的Fortran程序。局限性：1目標(biāo)函數(shù)必須是連續(xù)的。1 中給出2fminbnd 函數(shù)可能只給出局部最優(yōu)解。3當(dāng)問題的解位于區(qū)間邊界上時， fminbnd 函數(shù)的收斂速度常常很慢。此時， fmincon 函數(shù)的計算速度更快，計算精度更高。4fminbnd 函數(shù)只用于實(shí)數(shù)變量。參見：fminsearch, fmincon, fminunc, optimset, inline文獻(xiàn)：Forsythe, G.E., M.A. Malcolm, and C.B. Moler, Computer Methods for Mathematical Computations, Prentice Hall,

21、1976.應(yīng)用實(shí)例 例一 在區(qū)間（ 0 ，2）上求函數(shù) sin(x) 的最小值：x = fminbnd(sin,0,2*pi)x =4.7124所以區(qū)間（ 0，2 ）上函數(shù) sin(x) 的最小值點(diǎn)位于x=4.7124處。最小值處的函數(shù)值為：y = sin(x)y =-1.0000磁盤中該問題的 M 文件名為 opt21_1.m 。 例三 對邊長為 3m 的正方形鐵板，在四個角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？假設(shè)剪去的正方形的邊長為x，則水槽的容積為現(xiàn)在要求在區(qū)間（ 0，1.5 ）上確定一個 x ，使 最大化。因?yàn)閮?yōu)化工具箱中要求目標(biāo)函數(shù)最小化，所以需要對目標(biāo)

22、函數(shù)進(jìn)行轉(zhuǎn)換，即要求最小化。首先編寫 M 文件 opt21_3o.m:function f = myfun(x)f = -(3-2*x).2 * x;然后調(diào)用 fminbnd函數(shù) (磁盤中 M 文件名為 opt21_3.m)：x = fminbnd(opt21_3o,0,1.5)得到問題的解：x =0.5000即剪掉的正方形的邊長為0.5m 時水槽的容積最大。水槽的最大容積計算：y = optim2(x)y =-2.0000所以水槽的最大容積為2.0000m 3。線性規(guī)劃基本數(shù)學(xué)原理線性規(guī)劃是處理線性目標(biāo)函數(shù)和線性約束的一種較為成熟的方法，目前已經(jīng)廣泛應(yīng)用于軍事、經(jīng)濟(jì)、工業(yè)、農(nóng)業(yè)、教育、商業(yè)和

23、社會科學(xué)等許多方面。線性規(guī)劃問題的標(biāo)準(zhǔn)形式是：或?qū)懗删仃囆问綖椋浩渲校?0 為 n 維列向量。線性規(guī)劃的標(biāo)準(zhǔn)形式要求目標(biāo)函數(shù)最小化，約束條件取等式，變量非負(fù)。不符合這幾個條件的線性模型要首先轉(zhuǎn)化成標(biāo)準(zhǔn)形。線性規(guī)劃的求解方法主要是單純形法（Simple Method ），該法由 Dantzig于 1947 年提出，以后經(jīng)過多次改進(jìn)。單純形法是一種迭代算法，它從所有基本可行解的一個較小部分中通過迭代過程選出最優(yōu)解。其迭代過程的一般描述為：1 將線性規(guī)劃化為典范形式，從而可以得到一個初始基本可行解(0)x(0) ( 初始頂點(diǎn) ) ，2 尋找一個基本可行解x(1) ，使 z(x (1) ) z(x(1

24、)典范形式化為產(chǎn)生x的典范形式。(0) ) 。方法是通過消去法將產(chǎn)生x(0) 的3 繼續(xù)尋找較好的基本可行解x(2) ，x(3) ，使目標(biāo)函數(shù)值不斷改進(jìn)，即z(x (1) ) z(x (2) ) z(x (3) ) 。當(dāng)某個基本可行解再也不能被其它基本可行解改進(jìn)時，它就是所求的最優(yōu)解。Matlab優(yōu)化工具箱中采用的是投影法，它是單純形法的一種變種。相關(guān)函數(shù)介紹linprog函數(shù)功能：求解線性規(guī)劃問題。數(shù)學(xué)模型 ：其中 f ,x,b, beq,lb 和 ub 為向量， A 和 Aeq 為矩陣。語法：x = linprog(f,A,b,Aeq,beq)x = linprog(f,A,b,Aeq,b

25、eq,lb,ub)x = linprog(f,A,b,Aeq,beq,lb,ub,x0)x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)x,fval = linprog(.)x,fval,exitflag = linprog(.)x,fval,exitflag,output = linprog(.)x,fval,exitflag,output,lambda = linprog(.)描述：x = linprog(f,A,b)求解問題 min f*x，約束條件為 A*x 1%調(diào)用fun函數(shù)并要求有兩個輸出變量。g = .%計算x 處的梯度值。end若Hessi

26、an矩陣也可以求得，并且options.Hessian設(shè)為 on,即,options = optimset(Hessian,on)則 fun 函數(shù)必須返回解x 處的 Hessian 對稱矩陣 H 到第三個輸出變量中去。注意，當(dāng)被調(diào)用的fun 函數(shù)只需要一個或兩個輸出變量時（如算法只需要目標(biāo)函數(shù)的值f 和梯度值g 而不需要Hessian 矩陣 H 時），可以通過核對nargout的值來避免計算Hessian 矩陣function f,g,H = myfun(x)f = .%計算 x 處得函數(shù)值。if nargout 1%調(diào)用 fun 函數(shù)并要求有兩個輸出變量。g = .%計算 x 處的梯度值。i

27、f nargout 2H = .%計算 x 處的 Hessian 矩陣。end優(yōu)化參數(shù)選項。 可以通過 optimset 函數(shù)設(shè)置或改變這些參數(shù)。 其中有的參數(shù)適用于所有的優(yōu)化算法，有的則只適用于大型優(yōu)化問題，另外一些則只適用于中型問題。首先描述適用于大型問題的選項。這僅僅是一個參考，因?yàn)槭褂么笮蛦栴}算法有一些條件。對options于 fminunc 函數(shù)來說，必須提供梯度信息。LargeScale 當(dāng)設(shè)為 on 時使用大型算法，若設(shè)為off則使用中型問題的算法。適用于大型和中型算法的參數(shù)：exitflagoutputDiagnostics 打印最小化函數(shù)的診斷信息。Display 顯示水平。

28、選擇off，不顯示輸出；選擇iter，顯示每一步迭代過程的輸出；選擇 final，顯示最終結(jié)果。打印最小化函數(shù)的診斷信息。GradObj 用戶定義的目標(biāo)函數(shù)的梯度。對于大型問題此參數(shù)是必選的，對于中型問題則是可選項。MaxFunEvals 函數(shù)評價的最大次數(shù)。MaxIter 最大允許迭代次數(shù)。TolFun 函數(shù)值的終止容限。TolXx 處的終止容限。只用于大型算法的參數(shù)：Hessian 用戶定義的目標(biāo)函數(shù)的Hessian 矩陣。HessPattern 用于有限差分的Hessian 矩陣的稀疏形式。若不方便求fun 函數(shù)的稀疏Hessian 矩陣 H，可以通過用梯度的有限差分獲得的H 的稀疏結(jié)構(gòu)

29、 （如非零值的位置等）來得到近似的 Hessian 矩陣 H。若連矩陣的稀疏結(jié)構(gòu)都不知道，則可以將HessPattern設(shè)為密集矩陣，在每一次迭代過程中，都將進(jìn)行密集矩陣的有限差分近似（這是缺省設(shè)置）。這將非常麻煩，所以花一些力氣得到Hessian 矩陣的稀疏結(jié)構(gòu)還是值得的。MaxPCGIterPCG迭代的最大次數(shù)。PrecondBandWidth PCG 前處理的上帶寬，缺省時為零。對于有些問題，增加帶寬可以減少迭代次數(shù)。TolPCG PCG迭代的終止容限。TypicalX典型 x 值。只用于中型算法的參數(shù)：DerivativeCheck 對用戶提供的導(dǎo)數(shù)和有限差分求出的導(dǎo)數(shù)進(jìn)行對比。Dif

30、fMaxChange 變量有限差分梯度的最大變化。DiffMinChange -變量有限差分梯度的最小變化。LineSearchType 一維搜索算法的選擇。描述退出條件 :0表示目標(biāo)函數(shù)收斂于解x 處。表示已經(jīng)達(dá)到函數(shù)評價或迭代的最大次數(shù)。0表示目標(biāo)函數(shù)不收斂。該參數(shù)包含下列優(yōu)化信息：output.iterations 迭代次數(shù)。output.algorithm所采用的算法。output.funcCount函數(shù)評價次數(shù)。output.cgiterationsPCG迭代次數(shù)（只適用于大型規(guī)劃問題）。output.stepsize 最終步長的大?。ㄖ挥糜谥行蛦栴}）。output.firstord

31、eropt一階優(yōu)化的度量：解x 處梯度的范數(shù)。注意：1對于求解平方和的問題， fminunc 函數(shù)不是最好的選擇，用 lsqnonlin 函數(shù)效果更佳。2使用大型方法時， 必須通過將 options.GradObj 設(shè)置為 on 來提供梯度信息，否則將給出警告信息。算法：大型優(yōu)化算法 若用戶在 fun 函數(shù)中提供梯度信息， 則缺省時函數(shù)將選擇大型優(yōu)化算法，該算法是基于內(nèi)部映射牛頓法的子空間置信域法， 理論描述可參見文獻(xiàn) 8,9 。計算中的每一次迭代涉及到用 PCG法求解大型線性系統(tǒng)得到的近似解。中型優(yōu)化算法此時 fminunc 函數(shù)的參數(shù) options.LargeScale設(shè)置為 off。該

32、算法采用的是基于二次和三次混合插值一維搜索法的BFGS擬牛頓法。該法通過BFGS公式來更新 Hessian 矩陣。通過將 HessUpdate 參數(shù)設(shè)置為 dfp ，可以用DFP公式來求得 Hessian 矩陣逆的近似。通過將 HessUpdate 參數(shù)設(shè)置為 steepdesc ，可以用最速下降法來更新 Hessian 矩陣。但一般不建議使用最速下降法。缺省時的一維搜索算法，當(dāng)options.LineSearchType設(shè)置為 quadcubic時 , 將采用二次和三次混合插值法。將options.LineSearchType設(shè)置為 cubicpoly時，將采用三次插值法。 第二種方法需要的

33、目標(biāo)函數(shù)計算次數(shù)更少，但梯度的計算次數(shù)更多。這樣，如果提供了梯度信息，或者能較容易地算得，則三次插值法是更佳的選擇。局限性：1目標(biāo)函數(shù)必須是連續(xù)的。fminunc 函數(shù)有時會給出局部最優(yōu)解。2fminunc 函數(shù)只對實(shí)數(shù)進(jìn)行優(yōu)化，即x 必須為實(shí)數(shù)，而且f(x)必須返回實(shí)數(shù)。當(dāng) x 為復(fù)數(shù)時，必須將它分解為實(shí)部和虛部。3在使用大型算法時，用戶必須在fun 函數(shù)中提供梯度（GradObj 屬性必須設(shè)置為 on ）。4目前，若在 fun 函數(shù)中提供了解析梯度，則 options參數(shù)options參數(shù)中DerivativeCheck不能用于大型算法以比較解析梯度和有限差分梯度。通過將 options

34、參數(shù)的 MaxIter 屬性設(shè)置為 0 來用中型方法核對導(dǎo)數(shù)。然后重新用大型方法求解問題。參見：fminsearch, optimset, inlinefminsearch 函數(shù)功能：求解多變量無約束函數(shù)的最小值。數(shù)學(xué)模型 ：其中 x 為向量， f(x) 為函數(shù)，返回標(biāo)量。語法：x = fminsearch(fun,x0)x = fminsearch(fun,x0,options)x = fminsearch(fun,x0,options,P1,P2,.)x,fval = fminsearch(.)x,fval,exitflag = fminsearch(.)x,fval,exitflag,o

35、utput = fminsearch(.)描述：fminsearch求解多變量無約束函數(shù)的最小值。該函數(shù)常用于無約束非線性最優(yōu)化問題。x = fminsearch(fun,x0)初值為 x0，求 fun函數(shù)的局部極小點(diǎn) x。 x0 可以是標(biāo)量、向量或矩陣。x = fminsearch(fun,x0,options)用 options參數(shù)指定的優(yōu)化參數(shù)進(jìn)行最小化。x = fminsearch(fun,x0,options,P1,P2,.)將問題參數(shù) p1、p2 等直接輸給目標(biāo)函數(shù) fun ，將 options 參數(shù)設(shè)置為空矩陣，作為options參數(shù)的缺省值。x,fval = fminsearc

36、h(.)將 x 處的目標(biāo)函數(shù)值返回到fval參數(shù)中。x,fval,exitflag= fminsearch(.)返回 exitflag值，描述函數(shù)的退出條件。x,fval,exitflag,output = fminsearch(.)返回包含優(yōu)化信息的輸出參數(shù)output 。變量：各變量的意義同前。算法：fminsearch 使用單純形法進(jìn)行計算。對于求解二次以上的問題， fminsearch 函數(shù)比 fminunc 函數(shù)有效。但是，當(dāng)問題為高度非線性時， fminsearch 函數(shù)更具穩(wěn)健性。局限性：1應(yīng)用 fminsearch 函數(shù)可能會得到局部最優(yōu)解。2 fminsearch 函數(shù)只對實(shí)

37、數(shù)進(jìn)行最小化，即 x 必須由實(shí)數(shù)組成， f(x) 函數(shù)必須返回實(shí)數(shù)。如果 x 時復(fù)數(shù)，必須將它分為實(shí)數(shù)部和虛數(shù)部兩部分。注意 :fminsearch 函數(shù)不適合求解平方和問題，用lsqnonlin函數(shù)更好一些。參見：fminbnd, fminunc, optimset, inline二次規(guī)劃問題基本數(shù)學(xué)原理如果某非線性規(guī)劃的目標(biāo)函數(shù)為自變量的二次函數(shù)，約束條件全是線性函數(shù)，就稱這種規(guī)劃為二次規(guī)劃。其數(shù)學(xué)模型為：其中， H,A, 和 Aeq 為矩陣 , f ,b,beq,lb ,ub, 和 x 為向量。相關(guān)函數(shù)介紹quadprog 函數(shù)功能：求解二次規(guī)劃問題。語法：x = quadprog(H,

38、f,A,b)x = quadprog(H,f,A,b,Aeq,beq)x = quadprog(H,f,A,b,Aeq,beq,lb,ub)x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)x,fval = quadprog(.)x,fval,exitflag = quadprog(.)x,fval,exitflag,output = quadprog(.)x,fval,exitflag,output,lambda = quadprog(.)描述：x = quadprog(H,

39、f,A,b) 返回向量 x，最小化函數(shù) 1/2*x*H*x + f*x ，其約束條件為 A*x = b 。x = quadprog(H,f,A,b,Aeq,beq) 仍然求解上面的問題，但添加了等式約束條件 Aeq*x = beq 。x = quadprog(H,f,A,b,lb,ub)定義設(shè)計變量的下界 lb 和上界 ub，使得 lb = x= ub 。x = quadprog(H,f,A,b,lb,ub,x0)同上，并設(shè)置初值 x0。x = quadprog(H,f,A,b,lb,ub,x0,options)根據(jù) options參數(shù)指定的優(yōu)化參數(shù)進(jìn)行最小化。x,fval= quadprog

40、(.) 返回解 x 處的目標(biāo)函數(shù)值 fval= 0.5*x*H*x + f*x 。x,fval,exitflag= quadprog(.)返回 exitflag 參數(shù)，描述計算的退出條件。x,fval,exitflag,output = quadprog(.)返回包含優(yōu)化信息的結(jié)構(gòu)輸出output 。x,fval,exitflag,output,lambda = quadprog(.)返回解 x 處包含拉格朗日乘子的 lambda 參數(shù)。變量：各變量的意義同前。注意：1一般地，如果問題不是嚴(yán)格凸性的，用quadprog 函數(shù)得到的可能是局部最優(yōu)解。2 如果用 Aeq 和 Beq 明確地指定等式

41、約束， 而不是用 lb 和 ub 指定，則可以得到更好的數(shù)值解。3 若 x 的組分沒有上限或下限，則 quadprog 函數(shù)希望將對應(yīng)的組分設(shè)置為 Inf （對于上限）或 -Inf （對于下限），而不是強(qiáng)制性地給予上限一個很大的數(shù)或給予下限一個很小的負(fù)數(shù)。4對于大型優(yōu)化問題，若沒有提供初值x0，或 x0不是嚴(yán)格可行，則quadprog函數(shù)會選擇一個新的初始可行點(diǎn)。5若為等式約束，且quadprog 函數(shù)發(fā)現(xiàn)負(fù)曲度優(yōu)化過程終止， exitflag的值等于 -1 。算法：(negative curvature)，則大型優(yōu)化算法 當(dāng)優(yōu)化問題只有上界和下界， 而沒有線性不等式或等式約束， 則缺省算法為

42、大型算法。 或者，如果優(yōu)化問題中只有線性等式， 而沒有上界和下界或線性不等式時，缺省算法也是大型算法。本法是基于內(nèi)部映射牛頓法 (interior-reflective Newton method) 的子空間置信域法 ( subspace trust-region) 。該法的具體算法請參見文獻(xiàn) 2。該法的每一次迭代都與用 PCG法求解大型線性系統(tǒng)得到的近似解有關(guān)。中型優(yōu)化算法 quadprog 函數(shù)使用活動集法，它也是一種投影法，首先通過求解線性規(guī)劃問題來獲得初始可行解。診斷：大型優(yōu)化問題 大型優(yōu)化問題不允許約束上限和下限相等， 如若 lb(2)=ub(2) ，則給出以下出錯信息：Equal

43、upper and lower bounds not permitted in this large-scale method.Use equality constraints and the medium-scale method instead.若優(yōu)化模型中只有等式約束， 仍然可以使用大型算法； 如果模型中既有等式約束又有邊界約束，則必須使用中型方法。2中型優(yōu)化問題當(dāng)解不可行時， quadprog 函數(shù)給出以下警告：Warning: The constraints are overly stringent;there is no feasible solution.這里， quadprog

44、 函數(shù)生成使約束矛盾最壞程度最小的結(jié)果。當(dāng)?shù)仁郊s束不連續(xù)時，給出下面的警告信息：Warning: The equality constraints are overly stringent;there is no feasible solution.當(dāng) Hessian 矩陣為負(fù)半定時，生成無邊界解，給出下面的警告信息：Warning: The solution is unbounded and at infinity;the constraintsare not restrictive enough.這里， quadprog 函數(shù)返回滿足約束條件的x 值。局限性：1此時，顯示水平只能選擇off

45、和final，迭代參數(shù) iter不可用。2 當(dāng)問題不定或負(fù)定時，常常無解（此時 exitflag 參數(shù)給出一個負(fù)值，表示優(yōu)化過程不收斂） 。若正定解存在， 則 quadprog 函數(shù)可能只給出局部極小值，因?yàn)閱栴}可能時非凸的。3 對于大型問題，不能依靠線性等式，因?yàn)?Aeq 必須是行滿秩的，即 Aeq 的行數(shù)必須不多于列數(shù)。若不滿足要求，必須調(diào)用中型算法進(jìn)行計算。應(yīng)用實(shí)例 例一 求解下面的最優(yōu)化問題：目標(biāo)函數(shù)約束條件首先，目標(biāo)函數(shù)可以寫成下面的矩陣形式：其中輸入下列系數(shù)矩陣：H=1-1;-12f = -2; -6A=11;-12;21b = 2; 2; 3lb = zeros(2,1)然后調(diào)用

46、二次規(guī)劃函數(shù)quadratic ：x,fval,exitflag,output,lambda = quadprog(H,f,A,b,lb)得問題的解x =0.66671.3333fval =-8.2222exitflag =1output =iterations: 3algorithm: medium-scale: active-setfirstorderopt: cgiterations: lambda.ineqlinans =3.11110.44440lambda.lowerans =00磁盤中本問題的 M 文件為 opt24_1.m 。有約束最小化基本數(shù)學(xué)原理在有約束最優(yōu)化問題中， 通常

47、要將該問題轉(zhuǎn)換為更簡單的子問題， 這些子問題可以求解并作為迭代過程的基礎(chǔ)。 早期的方法通常是通過構(gòu)造懲罰函數(shù)等來將有約束的最優(yōu)化問題轉(zhuǎn)換為無約束最優(yōu)化問題進(jìn)行求解。 現(xiàn)在，這些方法已經(jīng)被更有效的基于 K-T（ Kuhn-Tucker ）方程解的方法所取代。 K-T 方程是有約束最優(yōu)化問題求解的必要條件。假設(shè)有所謂的 Convex 規(guī)劃問題， f(x) 和 Gi(x) ， i=1,2, ,m 為 Convex函數(shù)，則 K-T 方程對于求得全局極小點(diǎn)是必要的，也是充分的。對于規(guī)劃問題n其中， x 是設(shè)計參數(shù)向量， （xR），f ( x) 為目標(biāo)函數(shù)，返回標(biāo)量值，向量函數(shù) G( x) 返回等式約束和

48、不等式約束在 x 處的值。它的 K-T 方程可表達(dá)為：（ * ）i=1 , , mi=me+1, , m其中第一行描述了目標(biāo)函數(shù)和約束條件在解處梯度的取消。由于梯度取消，需要用拉格朗日乘子 i (i=1,2, ,m) 來平衡目標(biāo)函數(shù)與約束梯度間大小的差異。K-T 方程的解形成了許多非線性規(guī)劃算法的基礎(chǔ)， 這些算法直接計算拉格朗日乘子，通過用擬牛頓法更新過程， 給 K-T 方程積累二階信息， 可以保證有約束擬牛頓法的超線性收斂。這些方法稱為序列二次規(guī)劃法（ SQP），因?yàn)樵诿恳淮沃饕牡卸记蠼庖淮味我?guī)劃問題。對于給定的規(guī)劃問題，序列二次規(guī)劃（ SQP）的主要的思路是形成基于拉格朗日函數(shù)二次

49、近似的二次規(guī)劃子問題，即這里，通過假設(shè)約束條件為不等式約束來使（ * ）式得到了簡化，通過非線性有約束問題線性化來獲得二次規(guī)劃子問題。二次規(guī)劃子問題可表達(dá)為i =1, , mei =me+1, , m該子問題可以用任意一種二次規(guī)劃算法求解，求得的解可以用來形成新的迭代公式 xk +1=xk+ kdk。用 SQP法求解非線性有約束問題時的迭代次數(shù)常比用解無約束問題時的少，因?yàn)樵谒阉鲄^(qū)域內(nèi)， SQP方法可以獲得最佳的搜索方向和步長信息。給 Rosenbrock 函數(shù)添加非線性不等式約束 g( x)經(jīng)過 96 次迭代得到問題的解： x=0.9072,0.8288 ，初值為 x=-1.9,2 ，無約束

50、問題則需要 140 次迭代。圖 9-3 是搜索路徑圖。圖 9-3 SQP 法的搜索路徑MATLAB 中 SQP法的實(shí)現(xiàn)分三步，即拉格朗日函數(shù) Hessian 矩陣的更新；二次規(guī)劃問題求解；一維搜索和目標(biāo)函數(shù)的計算( 一) 、Hessian 矩陣的更新在每一次主要迭代過程中， 都用 BFGS法計算拉格朗日函數(shù)的Hessian 矩陣的擬牛頓近似矩陣。更新公式為：其中：上式中， i ( i =1, 2, , m) 為拉格朗日乘子的估計。（二）、二次規(guī)劃求解SQP法的每一次主要迭代過程中都要求一次二次規(guī)劃問題，形式如下：i =1, , mei =me+1, , m求解過程分兩步，第一步涉及可行點(diǎn)（若存

51、在）的計算，第二步為可行點(diǎn)至解的迭代序列。在第一步中，需要有可行點(diǎn)作為初值，若當(dāng)前點(diǎn)不可行，則通過求解下列線性規(guī)劃問題可以得到一個可行點(diǎn)：i =1, , mei =me+1, , m其中， Ai 為矩陣 A 的第 i 行。（三）、一維搜索和目標(biāo)函數(shù)的計算二次規(guī)劃子問題的解生成一個向量dk，它形成一個新的迭代公式：k 為步長參數(shù)。目標(biāo)函數(shù)的形式如下：其中，i =1, , m相關(guān)函數(shù)介紹fmincon 函數(shù)功能：求多變量有約束非線性函數(shù)的最小值。數(shù)學(xué)模型 ：其中， x, b , beq , lb, 和 ub 為向量， A 和 Aeq 為矩陣， c( x)和 ceq( x) 為函數(shù)，返回標(biāo)量。f(x

52、) ,cx) ,和 ceqx可以是非線性函數(shù)。()語法：x = fmincon(fun,x0,A,b)x = fmincon(fun,x0,A,b,Aeq,beq)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2, .)x,fval = fmincon(.)x,

53、fval,exitflag = fmincon(.)x,fval,exitflag,output = fmincon(.)x,fval,exitflag,output,lambda = fmincon(.)x,fval,exitflag,output,lambda,grad = fmincon(.)x,fval,exitflag,output,lambda,grad,hessian = fmincon(.)描述：fmincon求多變量有約束非線性函數(shù)的最小值。該函數(shù)常用于有約束非線性優(yōu)化問題。x = fmincon(fun,x0,A,b)給定初值 x0，求解 fun 函數(shù)的最小值 x。fun函

54、數(shù)的約束條件為 A*x = b ， x0 可以是標(biāo)量、向量或矩陣。x = fmincon(fun,x0,A,b,Aeq,beq)最小化 fun 函數(shù)，約束條件為 Aeq*x = beq和 A*x = b 。若沒有不等式存在，則設(shè)置A= 、 b= 。x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)定義設(shè)計變量 x 的下界 lb 和上界 ub，使得總是有 lb = x = ub。若無等式存在，則令A(yù)eq= 、beq= 。x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)在上面的基礎(chǔ)上，在nonlcon 參數(shù)中提供非線性不等式c(x)

55、 或等式 ceq(x) 。 fmincon 函數(shù)要求 c(x)= 0 且 ceq(x) = 0 。當(dāng)無邊界存在時，令lb=和（或） ub= 。x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)用 optiions參數(shù)指定的參數(shù)進(jìn)行最小化。x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,.)將問題參數(shù) P1, P2等直接傳遞給函數(shù)fun 和 nonlin 。若不需要這些變量，則傳遞空矩陣到 A, b, Aeq, beq, lb, ub, nonlconx,fval = f

56、mincon(.)返回解x,fval,exitflag= fmincon(.)和 options。x 處的目標(biāo)函數(shù)值。返回 exitflag參數(shù)，描述函數(shù)計算的退出條件。x,fval,exitflag,output = fmincon(.)返回包含優(yōu)化信息的輸出參數(shù)output 。x,fval,exitflag,output,lambda = fmincon(.)返回解x 處包含拉格朗日乘子的lambda 參數(shù)。x,fval,exitflag,output,lambda,grad= fmincon(.)返回解x 處fun函數(shù)的梯度。x,fval,exitflag,output,lambda,g

57、rad,hessian = fmincon(.)返回解x處 fun 函數(shù)的 Hessian 矩陣。變量：nonlcon 參數(shù)該參數(shù)計算非線性不等式約束 c(x) 2%GC=.%GCeq = .%解 x 處的非線性等式。被調(diào)用的 nonlcon 函數(shù)，要求有不等式的梯度。等式的梯度。4 個輸出變量。end若 nonlcon 函數(shù)返回 m元素的向量 c 和長度為 n 的 x，則 c(x) 的梯度 GC是一個 n*m 的矩陣，其中 GC(i,j) 是 c(j) 對 x(i) 的偏導(dǎo)數(shù)。同樣，若 ceq 是一個 p 元素的向量，則 ceq(x) 的梯度 Gceq是一個 n*p 的矩陣，其中 Gceq(

58、i,j) 是 ceq(j) 對 x(i) 的偏導(dǎo)數(shù)。其它參數(shù)意義同前。注意：大型優(yōu)化問題：1 使用大型算法，必須在 fun 函數(shù)中提供梯度信息 (options.GradObj 設(shè)置為 on) 。如果沒有梯度信息，則給出警告信息。fmincon 函數(shù)允許 g(x) 為一近似梯度，但使用真正的梯度將使優(yōu)化過程更具穩(wěn)健性。2當(dāng)對矩陣的二階導(dǎo)數(shù)（即 Hessian 矩陣）進(jìn)行計算以后，用該函數(shù)求解大型問題將更有效。 但不需要求得真正的 Hessian 矩陣，如果能提供 Hessian 矩陣的稀疏結(jié)構(gòu)的信息 （用 options 參數(shù)的 HessPattern 屬性），則 fmincon 函數(shù)可以算得

59、 Hessian 矩陣的稀疏有限差分近似。3若 x0 不是嚴(yán)格可行的，則fmincon 函數(shù)選擇一個新的嚴(yán)格可行初始點(diǎn)。4若 x 的某些元素沒有上界或下界，則fmincon 函數(shù)更希望對應(yīng)的元素設(shè)置為Inf （對于上界）或 -Inf （對于下界），而不希望強(qiáng)制性地給上界賦一個很大的值，給下界賦一個很小的負(fù)值。5線性約束最小化課題中也有幾個問題需要注意：Aeq矩陣中若存在密集列或近密集列（A dense ( 或fairly dense) column），會導(dǎo)致滿秩并使計算費(fèi)時。fmincon 函數(shù)剔除 Aeq 中線性相關(guān)的行。 此過程需要進(jìn)行反復(fù)的因子分解， 因此，如果相關(guān)行很多的話，計算將是一

60、件很費(fèi)時的事情。每一次迭代都要用下式進(jìn)行稀疏最小二乘求解T中型優(yōu)化問題1如果用 Aeq 和 beq 清楚地提供等式約束， 將比用 lb 和 ub 獲得更好的數(shù)值解。2在二次子問題中，若有等式約束并且因等式（ dependent equalities ）被發(fā)現(xiàn)和剔除的話，將在過程標(biāo)題中顯示 dependent( 當(dāng) output 參數(shù)要求使用options.Display = iter)。只有在等式連續(xù)的情況下，因等式才會被剔除。若等式系統(tǒng)不連續(xù)，則子問題將不可行并在過程標(biāo)題中打印infeasible信息。算法：大型優(yōu)化算法缺省時，若提供了函數(shù)的梯度信息， 并且只有上下界存在或只有線性等式約束存