Matlab目標(biāo)優(yōu)化入門

1、2。二階梯度方法這類方法很多，最簡(jiǎn)單的稱為Newton-Raphson方法，而最常用的是Quasi-Newton方法。Newtons method for finding an extreme point isxk+1 = xk - H-1(xk) y(xk)Quasi-Newton方法： use an approximation of the inverse Hessian.Form of approximation differs among methods牛頓-拉夫遜法 BFGS methodBroyden-Fletcher-Golfarb-ShannoDFP methodDavidon

2、-Fletcher-Powell優(yōu)化問(wèn)題及優(yōu)化問(wèn)題及matlabmatlab實(shí)現(xiàn)實(shí)現(xiàn)入門視頻教程一入門視頻教程一 ByBy考拉考拉2008.111、各種優(yōu)化模型介紹、各種優(yōu)化模型介紹2、典型優(yōu)化函數(shù)的使用方法、典型優(yōu)化函數(shù)的使用方法（線性、非線性、有約束、無(wú)約束、多目標(biāo)規(guī)劃，以及一般線性、非線性、有約束、無(wú)約束、多目標(biāo)規(guī)劃，以及一般性非線性整型優(yōu)化函數(shù)的使用和實(shí)例講解性非線性整型優(yōu)化函數(shù)的使用和實(shí)例講解）3、優(yōu)化中參數(shù)設(shè)置、優(yōu)化中參數(shù)設(shè)置4、matlab幫組系統(tǒng)的使用幫組系統(tǒng)的使用5、工具箱的安裝方法、工具箱的安裝方法優(yōu)化問(wèn)題分類優(yōu)化問(wèn)題分類約束型約束型（constrained）非約束型非約束

3、型（Unconstrained）線性（線性（linear）非線性（非線性（Nonlinear）整數(shù)型（整數(shù)型（integer）混合型混合型（mixed integer）多目標(biāo)多目標(biāo)(multiple objectives )非約束型規(guī)劃問(wèn)題非約束型規(guī)劃問(wèn)題 x,fval,exitflag,output= fminsearch(fun,x0) 實(shí)例：實(shí)例：求函數(shù)求函數(shù) f=8x-4y+x2+3y2的最小值的最小值 f=8*x(1)-4*x(2) +x(1)2+3*x(2)2; 確定一個(gè)初始點(diǎn)的方法：確定一個(gè)初始點(diǎn)的方法：x,y=meshgrid(-10:.5:10); f= 8*x-4*y +x

4、.2+3*y.2; surf(x,y,f) 選初始點(diǎn)：選初始點(diǎn)：x0=(0,0) x0=0,0; x,fval,exitflag=fminunc(f,x0) 本例本例matlab代碼代碼example_1 可以從可以從獲得。獲得。fminsearch和和fminunc是是matlab中關(guān)于無(wú)約束非線性中關(guān)于無(wú)約束非線性 優(yōu)化問(wèn)題優(yōu)化問(wèn)題的兩個(gè)函數(shù)，用來(lái)求解函數(shù)的極小值。的兩個(gè)函數(shù)，用來(lái)求解函數(shù)的極小值。fminsearch()和和fminunc()，前者適合處理階次低但是間斷點(diǎn)多，前者適合處理階次低但是間斷點(diǎn)多的函數(shù)，后者則對(duì)于高階連續(xù)的函數(shù)比較有效。的函數(shù)，后者則對(duì)于高階連續(xù)的函數(shù)比較有效。

5、 根據(jù)它們各自的實(shí)現(xiàn)原理來(lái)看（其中，前者是利用了單純形法的根據(jù)它們各自的實(shí)現(xiàn)原理來(lái)看（其中，前者是利用了單純形法的原理，后者是利用了擬牛頓法的原理），這兩個(gè)函數(shù)原理，后者是利用了擬牛頓法的原理），這兩個(gè)函數(shù) 都容易陷都容易陷入局部?jī)?yōu)化，并且結(jié)果的正確與否還要入局部?jī)?yōu)化，并且結(jié)果的正確與否還要取決于初值點(diǎn)取決于初值點(diǎn)x0的選的選取。取。 有約束線性優(yōu)化有約束線性優(yōu)化 x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)當(dāng)我們用當(dāng)我們用MATLAB軟件作優(yōu)化問(wèn)題時(shí)，軟件作優(yōu)化問(wèn)題時(shí)，所有求所有求maxf 的問(wèn)題化

6、為求的問(wèn)題化為求min(-f )來(lái)作。來(lái)作。約束約束g (x)0，化為，化為 g （x）0來(lái)作。來(lái)作。 實(shí)例：生產(chǎn)計(jì)劃問(wèn)題實(shí)例：生產(chǎn)計(jì)劃問(wèn)題 假設(shè)某廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，現(xiàn)庫(kù)存主要材料有A類3600公斤，B類2000公斤，C類3000公斤。每件甲產(chǎn)品需用材料A類9公斤，B類4公斤，C類3公斤。每件乙產(chǎn)品，需用材料A類4公斤，B類5公斤，C類10公斤。甲單位產(chǎn)品的利潤(rùn)70元，乙單位產(chǎn)品的利潤(rùn)120元。問(wèn)如何安排生產(chǎn)，才能使該廠所獲的利潤(rùn)最大。建立數(shù)學(xué)模型：建立數(shù)學(xué)模型：設(shè)設(shè)x1、x2分別為生產(chǎn)甲、乙分別為生產(chǎn)甲、乙產(chǎn)品的件數(shù)。產(chǎn)品的件數(shù)。f為該廠所獲總潤(rùn)。為該廠所獲總潤(rùn)。max f=70*x

7、(1)+120*x(2) s.t 9*x(1)+4*x(2)3600 4*x(1)+5*x(2)2000 3*x(1)+10*x(2)3000 x(1),x(2)0Matlab求解模型：求解模型： min f=-(70*x(1)+120*x(2) s.t 9*x(1)+4*x(2)3600 4*x(1)+5*x(2)2000 3*x(1)+10*x(2)3000 -x(1),-x(2) 0linprog模型：模型： f=-70 -120 s.t A=9 4;4 5;3 10 B=3600;2000;3000 Aeq=; Beq= lb=0 0;ub=inf inf x0=1 1 Code：ex

8、ample_2 可以從可以從 下載下載 linprog(f,A,b,Aeq,beq,lb,ub,x0,options)options的參數(shù)描述的參數(shù)描述：Display 顯示水平。 選擇off 不顯示輸出；選擇iter顯示每一 步迭代過(guò)程的輸出；選擇final 顯示最終結(jié)果。MaxFunEvals 函數(shù)評(píng)價(jià)的最大允許次數(shù)Maxiter 最大允許迭代次數(shù)TolX x處的終止容限 x,fval=linprog() 左端 fval 返回解x處的目標(biāo)函數(shù)值。x,fval,exitflag,output,lambda=linprog(f,A,b, Aeq,beq,lb,ub,x0) 的輸出部分： exi

9、tflag 描述函數(shù)計(jì)算的退出條件：若為正值，表示目標(biāo)函數(shù)收斂于解x處；若為負(fù)值，表示目標(biāo)函數(shù)不收斂；若為零值，表示已經(jīng)達(dá)到函數(shù)評(píng)價(jià)或迭代的最大次數(shù)。output 返回優(yōu)化信息：output.iterations表示迭代次數(shù)；output.algorithm表示所采用的算法；outprt.funcCount表示函數(shù)評(píng)價(jià)次數(shù)。lambda 返回x處的拉格朗日乘子。它有以下屬性： lambda.lower-lambda的下界； lambda.upper-lambda的上界； lambda.ineqlin-lambda的線性不等式； lambda.eqlin-lambda的線性等式。 Options

10、=optimset(display,iter,Tolx,1e-8);有約束的非線性規(guī)劃有約束的非線性規(guī)劃=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x,fval,exitflag,output,lambda,grad,hessian 例子：Min f=ex1*(6x12+3x22+2x1*x2+4x2+1) s.t x1x2-x1-x2+10 -2x1*x2-50 x(1)+2*x(1)=0 Matlab實(shí)現(xiàn)： function f=objfun(x) f=exp(x(1)*(6*x(1)2+3*x(2)2+2*x(1)*x(2)+4*x

11、(2)+1); function c,g=confun(x) c(1)=x(1)*x(2)-x(1)-x(2)+1； c(2)=-2*x(1)*x(2)-5； g=;然后可在工作空間鍵入程序： AE=1 2;BE=0; x0=1,1; nonlcon=confunx, fval =fmincon(objfun,x0, nonlcon)本例代碼本例代碼example_3.m，可以從，可以從獲得。獲得。多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃 多目標(biāo)規(guī)劃定義多目標(biāo)規(guī)劃定義為在一組約束下，多個(gè)不同的目標(biāo)為在一組約束下，多個(gè)不同的目標(biāo)函數(shù)進(jìn)行優(yōu)化設(shè)計(jì)。函數(shù)進(jìn)行優(yōu)化設(shè)計(jì)。 主要目標(biāo)法主要目標(biāo)法 其基本思想是：在多目標(biāo)問(wèn)題中

12、，根據(jù)問(wèn)題的實(shí)際情況，確定一個(gè)目標(biāo)為主要目標(biāo)，而把其余目標(biāo)作為次要目標(biāo)，并且根據(jù)經(jīng)驗(yàn)，選取一定的界限值。這樣就可以把次要目標(biāo)作為約束來(lái)處理，于是就將原來(lái)的多目標(biāo)問(wèn)題轉(zhuǎn)化為一個(gè)在新的約束下的單目標(biāo)最優(yōu)化問(wèn)題。 線性加權(quán)和法線性加權(quán)和法 其基本思想是：按照多目標(biāo)fi(x) (i=1, 2, ,m)的重要程度，分別乘以一組權(quán)系數(shù)j(j=1, 2, ,m)然后相加作為目標(biāo)函數(shù)而構(gòu)成單目標(biāo)規(guī)劃問(wèn)題。 實(shí)例：實(shí)例：某鋼鐵廠準(zhǔn)備用5000萬(wàn)用于A、B兩個(gè)項(xiàng)目的技術(shù)改造投資。設(shè)x1、x2分別表示分配給項(xiàng)目A、B的投資。據(jù)專家預(yù)估計(jì)，投資項(xiàng)目A、B的年收益分別為70%和66%。同時(shí)，投資后總的風(fēng)險(xiǎn)損失將隨著總投

13、資和單項(xiàng)投資的增加而增加，已知總的風(fēng)險(xiǎn)損失為0.02x12+0.01x22+0.04(x1+x2)2，問(wèn)應(yīng)如何分配資金才能使期望的收益最大，同時(shí)使風(fēng)險(xiǎn)損失為最小。 數(shù)學(xué)模型：max f1(x)=70 x1+66x2 min f2(x)= 0.02x12+0.01x22+0.04(x1+x2)2 s.t x1+x25000 0 x1, 0 x2 線性加權(quán)構(gòu)造目標(biāo)函數(shù)： max f=0.5f1(x) 0.5f2(x) 化最小值問(wèn)題： min (f)=- 0.5f1(x) +0.5f2(x)Matlab實(shí)現(xiàn)實(shí)現(xiàn)f=-0.5*(70*x(1)+66*x(2) +0.5*(0.02*x(1)2+0.01

14、*x(2)2 +0.04*(x(1)+x(2)2); x0=1000,1000A=1 1;b=5000;lb=zeros(2,1); x,fval, exitflag=fmincon (f,x0, A,b,lb,) 代碼代碼example_4,可從可從 下載下載(3) 極大極小法極大極小法 其基本思想是：對(duì)于極小化的多目標(biāo)規(guī)劃，讓其中最大的目標(biāo)函數(shù)值盡可能地小于此，對(duì)每個(gè) xR，我們先求諸目標(biāo)函數(shù)值fi(x)的最大值，然后再求這些最大值中的最小值。 x,fval,maxfval,exitflag,output,lambda=fminmax (fun,x0,A,b,Aeq,beq,lb,ub,n

15、onlcon,options,p1,p2,.)(4) 目標(biāo)達(dá)到法目標(biāo)達(dá)到法 fgoalattain函數(shù)用于解決此類問(wèn)題。 其數(shù)學(xué)模型形式數(shù)學(xué)模型形式為： min F(x)-weight goal c(x) 0 ceq(x)=0 A xb Aeq x=beq lbxub 其中，x,weight,goal,b,beq,lb和ub為向量，A和Aeq為矩陣，c(x),ceq(x)和F(x)為函數(shù)，例：例：某 化工廠擬生產(chǎn)兩種新產(chǎn)品A和B，其生產(chǎn)設(shè)備費(fèi)用分別為2萬(wàn)元/噸和5萬(wàn)元/噸。這兩種產(chǎn)品均將造成環(huán)境污染，設(shè)由公害所造成的損失可折算為A為4萬(wàn)元 /噸，B為1萬(wàn)元/噸。由于條件限制，工廠生產(chǎn)產(chǎn)品A和B

16、的最大生產(chǎn)能力各為每月5噸和6噸，而市場(chǎng)需要這兩種產(chǎn)品的總量每月不少于7噸。試問(wèn)工廠如何安 排生產(chǎn)計(jì)劃，在滿足市場(chǎng)需要的前提下，使設(shè)備投資和公害損失均達(dá)最小。該工廠決策認(rèn)為，這兩個(gè)目標(biāo)中環(huán)境污染應(yīng)優(yōu)先考慮，設(shè)備投資的目標(biāo)值為20萬(wàn)元，公 害損失的目標(biāo)為12萬(wàn)元。 建立數(shù)學(xué)模型：建立數(shù)學(xué)模型： 設(shè)工廠每月生產(chǎn)產(chǎn)品A為x1噸，B為x2噸，設(shè)備投資費(fèi)為f(x1),公害損失費(fèi)為f(x2),則問(wèn)題表達(dá)為多目標(biāo)優(yōu)化問(wèn)題： min f1(x)=2x1+5x2 min f2(x)=4x1+x2 s.t x15； x26； x1+x27；x1 ,x20Matlab實(shí)現(xiàn)：實(shí)現(xiàn)： function f=ff12(x

17、) f(1)=2*x(1)+5*x(2); f(2)= 4*x(1) +x(2); 按給定目標(biāo)?。?goal=20,12; weight=20,12; x0=2,2 A=1 0; 0 1;-1 -1; b=5 6 -7; lb=zeros(2,1);x,fval,attainfactor,exitflag =fgoalattain(ff12,x0,goal,weight,A,b,lb,) example_5可以從可以從獲得獲得一般的非線性一般的非線性整數(shù)整數(shù)規(guī)劃規(guī)劃errmsg,Z,X,t,c,fail = BNB20(fun,x0,xstat,xl,xu,a,b,aeq,beq,nonlc,

18、setts,opts,varargin)本例中使用的本例中使用的bnb20工具箱，工具箱， 在在的的工具箱下載版塊工具箱下載版塊可以下載，但在可以下載，但在matlab7中使用，存在中使用，存在bug，修改后的，修改后的bnb20將分為將分為matlab6，6.5和和7.0版本，版本，隨本例代碼隨本例代碼bnbexample.m，一起發(fā)布在網(wǎng)站，一起發(fā)布在網(wǎng)站視頻教學(xué)視頻教學(xué)版塊版塊，提供下載。，提供下載。 單純形解法單純形解法 線性規(guī)劃 單純形方法的基本思路是，首先從可行域中找一個(gè)基可行解，然后判別它是否為最優(yōu)解，如果是，則停止計(jì)算；否則，就找一個(gè)更好的基可行解，再進(jìn)行檢驗(yàn)，如此反復(fù)迭代，直

19、至找到最優(yōu)解，或者判定它無(wú)界（即無(wú)有限最優(yōu)解）為止。 幾種常見的優(yōu)化方法Taylor 展開：V(x) = V(xk) + (x-xk)V(xk) +1/2 (x-xk)2 V(xk)+. 當(dāng)x是3N個(gè)變量的時(shí)候， V(xk)成為3Nx1的向量，而V(xk)成為3Nx3N的矩陣，矩陣元如：jixxVHessian解非線性方程解非線性方程f(x)=0的牛頓的牛頓(Newton) 法，就是將非線性法，就是將非線性方程線性化的一種方法。它是解代數(shù)方程和超越方程的有效方方程線性化的一種方法。它是解代數(shù)方程和超越方程的有效方法之法之 一。一。 一階梯度法 a. Steepest descendentSk = -gk/|gk|directiongradient知道了方向，如何確定步長(zhǎng)呢？最常用的是先選擇任意步長(zhǎng)l，然后在計(jì)算中調(diào)節(jié)kkkkSXXl1用體系的能量作為外界衡量標(biāo)準(zhǔn)，能量升高了則逐步減小步長(zhǎng)。robust, but slow最速下降法 最陡下降法（最陡下降法（S