Matlab優(yōu)化算法

1、2015/4/24Matlab優(yōu)化主講人：饒志歡現(xiàn)代優(yōu)化算法什么是優(yōu)化？就是從各種方案中選取一個(gè)最 好的。從數(shù)學(xué)角度看，優(yōu)化理論就是研究如 何在狀態(tài)空間中尋找到全局最優(yōu)點(diǎn)。比如水泥混凝土的性能，涉及到水、沙、石 子、水泥和其他摻雜物比例。學(xué)校課程表排 課問題、售票員上崗問題、公司內(nèi)部人員安 排出效益等。降低成本、提咼效益是冋題的 關(guān)鍵。i2015/4/241.1 MATLAB軍優(yōu)化問題的主要函數(shù)類 型模型基唱暉磐七面刪小Nir. F Cxi tKKxiSs=f mirtrnd (F xyg)無紡寂橈小Hu. F(X)呂細(xì)lntift亡(F；始； K=fudnsercht F jb)錢苣規(guī)Min

2、 cTX 軋t A戢PJliEpng(比為 b：Mir sffe+cSc2. t.蟲玫力K= qua如工 o gH, c3 A, b)（鞍生規(guī)劃）m f(X)s.-. G =0aincon(迭副目桁間題Kin is.七 FtxJirUgoalX=f foalat tain(T x_.劭oal,v)擾乍痕問題Min 血空Fi)i譏礎(chǔ)s.-. G(x) 0囂= jcHmax (FG，運(yùn),)1.2優(yōu)化函數(shù)的輸入變量說午 r - p =(FhV； 訂丘a t+bdft* +_u7：JL爼:r |,- L j -. iri AT禍 MAI i I,.JIA A dm Iim 71.：i 1 . I- -

3、 1 1 iflUIGW Uvuuw* Isoujiwift1 申 ord itiZZ1.3優(yōu)化函數(shù)的輸出變量下表曲 述Z冊;35iJ.iT 崟M絡(luò)它只是雄KSllt 吋土：才粹王且hi i； 片/酗蕓審*忙廿冃標(biāo)1：俶信1 n ii 兄 IfgQilii 11 ai Fj,f u i r i： if ii -ii hpi打.Tl、ijci i irfi H#squoii ir f fn it linrl輻應(yīng)吐命件： ifjv.志E帀腳，：權(quán)裁干凍朮 云已1壬!0倉三誡汪比砂皿；斗；.斥日吊毆必収誑f 和乜啻比忙狛咒it懇廨吐商. -ti at: e x i-nn. I所予幣的至出 ruLxC

4、cim-t ： LI 班評 h?：Sr1.4控制參數(shù)options的設(shè)置(1) Display顯示水平.取值為o時(shí)，不顯示輸出；取值為ite時(shí) ，顯示每次迭代的信息；取值為fina時(shí),顯示最終結(jié)果.默認(rèn)值為final .(2) MaxFunEvals允許進(jìn)行函數(shù)評價(jià)的最大次數(shù)，取值為正整數(shù)(3) Maxlter:允許進(jìn)行迭代的最大次數(shù)，取值為正整數(shù)控制參數(shù)options可以通過函數(shù)optimset創(chuàng)建或修改。命令的格式如下：(1) options=optimset( optimfun )創(chuàng)建一個(gè)含有所有參數(shù)名，并與優(yōu)化函數(shù)optimfun相關(guān)的默認(rèn)值的選項(xiàng)結(jié)構(gòu)options.1.4控制參數(shù)op

5、tions的設(shè)置(2)options=optimset( paraml ,value1, param2 ,value2,.J創(chuàng)建一個(gè)名稱為options的優(yōu)化選項(xiàng)參數(shù),其中指定的參數(shù)具有指定值，所有未指定的參數(shù)取默認(rèn)值.(3)options=optimset(oldops, paraml ,value1, param2,value2,.J創(chuàng)建名稱為oldops的參數(shù)的拷貝，用指定的參數(shù)值修改oldops中相應(yīng)的參數(shù).例：opts=optimset( Display , iter -8) ToIFun ,1e該語句創(chuàng)建一個(gè)稱為opts的優(yōu)化選項(xiàng)結(jié)構(gòu)，其中顯示參數(shù)設(shè)為iter , T參數(shù)設(shè)為1e-

6、8.2.1 一元函數(shù)無約束優(yōu)化問題一元函數(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 ()函數(shù)fminbnd的算法基于黃金分害割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。2.1 一元函數(shù)無約束優(yōu)化問題例-汕在0x芒乜興工s. t. AT如g / =民4住LB用MATLAB軟件求解

7、，其輸入格式如下：1. x=quadprog(H,C,A,b);2. x=quadprog(H,C,A,b,Aeq,beq);3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0);5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,XO,options);6. x,fval=quaprog(.);7. x,fval,exitflag=quaprog(.J;8. x,fval,exitflag,output=quaprog(.J;2.3二次規(guī)劃例 min f

8、(x1,x2)=-2*x1-6*x2+x2-2*x1*x2+2*x2人2s.t. x1+x2電niin z 31、寫成標(biāo)準(zhǔn)形式:I. i.2、輸入命令：H=1 -1; -1 2;-#+2x2玄訂心 J 屯x2先c=-2 ;-6;A=1 1; -1 2;b=2;2;Aeq=;beq=; VLB=0;0;VUB=;x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、運(yùn)算結(jié)果為：x =0.6667 1.3333 z = -8.22222.4 一般非線性規(guī)劃標(biāo)準(zhǔn)型為min F(X)s.tAX=bG(X)Ceq(X)=0 VLEKVUB其中X為n維變元向量，G(X)與 Ceq(

9、X均為非線性函數(shù)組成的向量，其它變量的含義與線性規(guī)劃、二次規(guī)劃中相同用Matlab求解上述問題，基本步驟分三步：1. 首先建立M文件fun.m,定義目標(biāo)函數(shù)F(X):function f=fun( X);f=F(X);2. 若約束條件中有非線性約束:G(X)或Ceq(X)=0則建立M文件 nonIcon.m定義函數(shù) G(X)與Ceq(X):function G,Ceq=nonlcon(X)G=.Ceq=.2.4 一般非線性規(guī)劃3. 建立主程序.非線性規(guī)劃求解的函數(shù)是 fmincon,命令的基本格式如下：(1) x=fmincon ( fun ,X0,A,b)(2) x=fmincon ( fu

10、n ,X0,A,b,Aeq,beq)(3) x=fmineon ( fun ,X0,A,b, Aeq,beq,VLB,VUB)nonIcon )nonleon (4)x=fmineon ( fun ,X0,A,b,Aeq,beq,VLB,VUB, (5)x=fmineon ( fun ,X0,A,b,Aeq,beq,VLB,VUB,opti ons)(6) x,fval= fmincon (.)(7) x,fval,exitflag= fmincon (.)(8) x,fval,exitflag,output= fmincon (.)2.4 一般非線性規(guī)劃1 fmincon函數(shù)提供了大型優(yōu)化算

11、法和中型優(yōu) 化算法。默認(rèn)時(shí)，若在fun函數(shù)中提供了梯度（options參數(shù)的GradOb設(shè)置為o），并且 只有上卞界存在或只有等式約束，fmincon函 數(shù)將選擇大型算法。當(dāng)既有等式約束又有梯 度約束時(shí)，使用中型算法。2 fmincon函數(shù)的中型算法使用的是序列二次 規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問 題，并用BFG法更新拉格朗日HessiaS陣。3 fmincon函數(shù)可能會(huì)給出局部最優(yōu)解，這與初值X0的選取有關(guān)。2.4 一般非線性規(guī)劃5二沁工02.4 一般非線性規(guī)劃2、先建立M-文件fun3.m:fun cti on f=fun 3(x);f=-x(1)-2*x(2)+(1/2)*x(1

12、)A2+(1/2)*x(2)A23、再建立主程序youh2.m：x0=1;1;A=2 3 ;1 4; b=6;5;Aeq=;beq=;VLB=0;0; VUB=;x,fval=fmi neon (fu n3,x0,A,b,Aeq,beq,VLB,VUB)4、運(yùn)算結(jié)果為：x = 0.7647 1.0588fval = -2.02942.5線性規(guī)劃問題線性規(guī)劃問題線性規(guī)劃問題是目標(biāo)函數(shù)和約束條件均為線 性函數(shù)的問題，MATLAB6.0解決的線性規(guī)劃 問題的標(biāo)準(zhǔn)形式為：min f(x)sub.to :x A ?fo Aeq = beq?ub x Toolboxes-Optimization-Opti

13、mization3.2使用步驟1. 選擇求解器solver和優(yōu)化算法algorithm;2. 選定目標(biāo)函數(shù)(objective function);3. 設(shè)定目標(biāo)函數(shù)的相關(guān)參數(shù)；4. 設(shè)置優(yōu)化選項(xiàng)；5. 單擊“ start按鈕，運(yùn)行求解；6. 查看求解器的狀態(tài)和求解結(jié)果；將目標(biāo)函數(shù)、選項(xiàng)和結(jié)果導(dǎo)入導(dǎo)出。142015/4/243.2使用步驟，S-OcoHaijiarh Pih itiHBQ1UB4W :*-flft-” Ejtigin* LcnJJBHtE：B Rr 切h*r 河 口QkAa-MiJrCb(E 憐 f 吐 9ecriIXXEKr沽呼詡 vxr tekhKCurtPrblrn 5i

14、up Ml ItviUKl Soterard:卄！M14?4 LJitwtrwanWhwFa t-rirwlim uLisi； “nlr*嚴(yán) rwniwfiEkiv t n-iuBctK hjrcbmMUTEFW.舊血3.3應(yīng)用實(shí)例無約束優(yōu)化(fminunc求解器)求f(x)=xA2+4*x-6極小值，初始點(diǎn)取x=0。解：1.首先建立目標(biāo)函數(shù)文件 FunUnc.m文件:fun cti on y二FunUn c(x)y=xA2+4*x-6;2.然后啟動(dòng)優(yōu)化工具152015/4/243.3應(yīng)用實(shí)例3.3應(yīng)用實(shí)例一Algorithm 有兩個(gè)選擇： Large scale和 Medium scale，

15、設(shè)置完參數(shù)點(diǎn)擊start即可得到上圖中 的結(jié)果。162015/4/243.4應(yīng)用實(shí)例二無約束優(yōu)化(fminsearch求解器)求f(x)=|x2-3*x+2|的極小值，初始點(diǎn)取x=-7解：1解：啟動(dòng)優(yōu)化工具；用fminunc時(shí)設(shè)置參數(shù)如圖2.運(yùn)行得到結(jié)果3.4應(yīng)用實(shí)例二4咼級優(yōu)化算法習(xí)慣上，將優(yōu)化算法分為兩類：局部優(yōu)化算法和全局性優(yōu)化算法。前者可以稱 為經(jīng)典優(yōu)化算法，已經(jīng)得到了人們廣泛深入 的研究。線性規(guī)劃、整數(shù)規(guī)劃、0-規(guī)劃、非 線性規(guī)劃、排隊(duì)論、決策論。后者習(xí)慣上稱 為現(xiàn)代優(yōu)化算法，是20世紀(jì)80年代興起的新 型全局性優(yōu)化算法，主要包括禁忌搜索、模 擬退火、遺傳算法、神經(jīng)網(wǎng)絡(luò)等，其主要應(yīng)

16、用對象是優(yōu)化問題中的 難解問題，即NP-hard問題4.1算法簡介為了找出地球上最高的山，一群有志氣的兔 子們開始想辦法。4.1算法簡介方案一：兔子們吃了失憶藥片，并 被發(fā)射到太空，然后隨機(jī)落到了地球上的某 些地方。他們不知道自己的使命是什么。但 是，如果你過幾年就殺死一部分海拔低的兔 子，多產(chǎn)的兔子們自己就會(huì)找到珠穆朗瑪峰。遺傳算法202015/4/24#2015/4/244.1算法簡介方案二：兔子們朝著比現(xiàn)在高的地 方跳去，它們找到了不遠(yuǎn)處的最高山峰。但 是這座山不一定是珠穆朗瑪峰。其實(shí)，它們 這種做法只是自己心理上認(rèn)為找到了最高的 山，并不能保證局部最優(yōu)值就是全局最優(yōu)值。局部搜索法4.1算法簡介方案三：兔子們知道一個(gè)兔子的力 量是渺小的。于是，它們互相轉(zhuǎn)告著，哪里 的山已經(jīng)找過，并且找過的每一座山他們都 留下一只兔子做記號。這樣，它們制定了下 一步去哪里尋找的策略。禁忌搜索法212015/4/24#2015/4/244.1算法簡