優(yōu)化問題的求解.ppt

1、第11章 優(yōu)化問題的求解,11.1 線性規(guī)劃 11.2 無約束優(yōu)化 11.3 單目標(biāo)約束優(yōu)化 11.4 多目標(biāo)約束優(yōu)化 11.5 最小二乘優(yōu)化 11.6 混合整數(shù)規(guī)劃 11.7 動(dòng)態(tài)規(guī)劃 11.8 實(shí)例解析,本章目標(biāo)：求 或,11.1 線性規(guī)劃,線性規(guī)劃問題是目標(biāo)函數(shù)和約束條件均為線性函數(shù)的問題，其整個(gè)問題的數(shù)學(xué)描述為： MATLAB的最優(yōu)化工具箱中提供的線性規(guī)劃求解函數(shù)是linprog()，該函數(shù)的調(diào)用格式為： x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,.),11.2 無約束優(yōu)化,非線

2、性規(guī)劃是指目標(biāo)函數(shù)或約束函數(shù)（或兩者）為設(shè)計(jì)變量的非線性函數(shù)的一種優(yōu)化方法。其標(biāo)準(zhǔn)形式為： 其中 求解無約束優(yōu)化問題的主要算法有單純形法、擬牛頓法和最速下降法（或共軛梯度法）等，MATLAB提供了相應(yīng)算法的實(shí)現(xiàn)函數(shù)fminsearch()和fminunc()。它們的調(diào)用格式分別如下： x,fval,exitflag,output = fminsearch(fun,x0,options,p1,p2,.) x,fval,exitflag,output,grad,hessian=fminunc(fun,x0,options,p1,p2,.),11.3 單目標(biāo)約束優(yōu)化,一、帶有變量邊界約束的優(yōu)化 帶有

3、變量邊界約束的優(yōu)化問題的一般描述為： 對(duì)于單變量目標(biāo)函數(shù)f (x)，MATLAB提供了fminbnd()函數(shù)求解該目標(biāo)函數(shù)在區(qū)間內(nèi)的極小值，該函數(shù)的調(diào)用格式如下： x,fval,exitflag,output=fminbnd(fun,x1,x2,options,p1,p2,.) 對(duì)于一般的多變量目標(biāo)函數(shù)f (x)，MATLAB并未提供直接的函數(shù)求解。John DErrico開發(fā)的fminsearchbnd()函數(shù)擴(kuò)展了現(xiàn)有函數(shù)的功能，能直接求解這樣的問題，該函數(shù)可以從以下網(wǎng)址下載： x,fval,exitflag,output=fminsearchbnd(fun,x0,LB,UB,option

4、s,p1,p2,.),二、多變量約束優(yōu)化 多變量非線性約束優(yōu)化問題的一般描述為： 其中， 。為求解方便，約束條件還可以進(jìn)一步細(xì)化為線性等式約束，線性不等式約束，這時(shí)原規(guī)劃問題可以改寫成 MATLAB最優(yōu)化工具箱中提供了一個(gè)專門用于求解各種約束下的優(yōu)化問題的函數(shù)fmincon()，該函數(shù)的調(diào)用格式為： x,fval,exitflag,output,lambda,grad,hessian=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,p1,p2,.),三、二次規(guī)劃 一般二次型規(guī)劃問題的數(shù)學(xué)表示為： MATLAB最優(yōu)化工具箱中提供了求解二次規(guī)劃問題

5、的函數(shù)quadprog()，該函數(shù)的調(diào)用格式為： x,fval,exitflag,output,lambda=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0, options,p1,p2,.),四、半無限約束優(yōu)化 半無限約束優(yōu)化問題的標(biāo)準(zhǔn)形式為： 其中 為向量x和 的連續(xù)函數(shù)，且向量 的長(zhǎng)度最多為2。,MATLAB最優(yōu)化工具箱中提供的函數(shù)fseminf()可以直接求解半無限約束優(yōu)化問題，該函數(shù)的調(diào)用格式為： x,fval,exitflag,output,lambda=fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,lb,ub,opti

6、ons,p1,p2,.) 其中ntheta是半無限約束條件的個(gè)數(shù)，seminfcon是一函數(shù)名，該函數(shù)定義了非線性約束條件和半無限約束條件，該函數(shù)的一般寫法如下： function c,ceq,K1,K2,.,Kntheta,S = myinfcon(x,S) % S為向量w的采樣值 % 初始化樣本間距 if isnan(S(1,1), S = . % S有ntheta行2列 end w1 = . % 計(jì)算樣本集 w2 = . % 計(jì)算樣本集 . wntheta = . % 計(jì)算樣本集 K1 = . % 在x和w處的第1個(gè)半無限約束值 K2 = . % 在x和w處的第2個(gè)半無限約束值 . Kn

7、theta = . % 在x和w處的第ntheta個(gè)半無限約束值 c = . % 在x處計(jì)算非線性不等式約束值 ceq = . % 在x處計(jì)算非線性不等式約束值,11.4 多目標(biāo)約束優(yōu)化,多目標(biāo)優(yōu)化問題的一般表示為： 其中， 一、極小極大優(yōu)化 假設(shè)有一組n個(gè)目標(biāo)函數(shù) ，它們中的每一個(gè)均可以提取出一個(gè)最大值 而這樣得出的一組最大值仍然是x的函數(shù)?，F(xiàn)在想對(duì)這些最大值進(jìn)行比較進(jìn)行最小化搜索，即 則這類問題稱為極小極大問題。,考慮各類約束條件，極小極大問題可以更一般地改寫成 MATLAB最優(yōu)化工具箱中的fminimax()函數(shù)可以直接求解極小極大問題，該函數(shù)的調(diào)用格式為 x,fval,maxfval,

8、exitflag,output,lambda=fminimax(fun,x0,A,b,Aeq,beq,lb,ub, nonlcon,options,p1,p2,.) 另外，基于fminimax()函數(shù)，還可以求解相關(guān)的變形問題，如極小極小優(yōu)化問題：,二、目標(biāo)規(guī)劃 目標(biāo)規(guī)劃的標(biāo)準(zhǔn)形式如下： MATLAB最優(yōu)化工具箱中提供了函數(shù)fgoalattain()來求解目標(biāo)規(guī)劃問題，該函數(shù)的調(diào)用格式為： x,fval,attainfactor,exitflag,output,lambda=fgoalattain(fun,x0,goal,weight,A,b,Aeq, beq,lb,ub,nonlcon,op

9、tions,p1,p2,.),11.5 最小二乘優(yōu)化,一、線性最小二乘優(yōu)化 線性最小二乘優(yōu)化問題的一般數(shù)學(xué)描述為： MATLAB優(yōu)化工具箱提供了函數(shù)lsqlin()來直接求解上述優(yōu)化問題，該函數(shù)的調(diào)用格式為： x,resnorm,residual,exitflag,output,lambda=lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0, options,p1,p2,.),實(shí)際問題中經(jīng)常會(huì)遇到下面的非負(fù)最小二乘優(yōu)化問題： 對(duì)于這種問題，MATLAB提供的lsqnonneg()函數(shù)可以用來輕松求解。lsqnonneg()函數(shù)的調(diào)用格式為： x,resnorm,residual,

10、exitflag,output,lambda = lsqnonneg(C,d,x0,options),二、非線性最小二乘優(yōu)化 對(duì)于多目標(biāo)規(guī)劃問題 其中， ，則可以按照下面的方式將其轉(zhuǎn)換成單目標(biāo)優(yōu)化問題： 這就是所謂的非線性最小二乘優(yōu)化。對(duì)于該問題固然可以利用前面介紹的函數(shù)求解，此外，MATLAB最優(yōu)化工具箱還提供了lsqnonlin()函數(shù)直接求解這個(gè)問題，該函數(shù)的調(diào)用格式為： x,resnorm,residual,exitflag,output,lambda,jacobian=lsqnonlin(fun,x0,lb,ub, options,p1,p2,.),11.6 混合整數(shù)規(guī)劃,一、線性整

11、數(shù)規(guī)劃（LIP） 所謂線性整數(shù)規(guī)劃，就是在線性規(guī)劃的基礎(chǔ)上，使得全部或部分自變量取整數(shù)。線性整數(shù)規(guī)劃的一般數(shù)學(xué)描述為： MATLAB本身沒有提供線性整數(shù)規(guī)劃問題的求解函數(shù)，但如果已知自變量所在的區(qū)間，則理論上可以用窮舉法列出區(qū)間內(nèi)所有的變量組合，逐個(gè)判定約束條件是否滿足，從滿足的組合中逐個(gè)求取函數(shù)的值并排序，由其最小值的對(duì)應(yīng)關(guān)系可以簡(jiǎn)單地求解所需的自變量值。該方法看似簡(jiǎn)單直觀，但它僅對(duì)于一些小規(guī)模問題可行。因此需要另外尋找比較好的算法求解線性整數(shù)規(guī)劃問題，下面介紹常用的分支定界法。,分支定界法（分而治之）步驟：（為便于敘述，將要求解的整數(shù)規(guī)劃問題稱為L(zhǎng)IP，將與它對(duì)應(yīng)的線性規(guī)劃問題稱為L(zhǎng)P）

12、（1）求解問題LP，將得到以下情況之一： LP沒有可行解，這時(shí)LIP也沒有可行解，則停止； LP有最優(yōu)解，并且解變量都是整數(shù)，則它也是LIP的最優(yōu)解，則停止； LP有最優(yōu)解，但不符合LIP中的整數(shù)條件，此時(shí)記它的目標(biāo)函數(shù)值為 ，這時(shí)若記 為L(zhǎng)IP的最優(yōu)目標(biāo)函數(shù)值，則必有 。 （2）分支與定界 首先在LP的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量x，設(shè)其值為l，構(gòu)造兩個(gè)約束條件： ,將這兩個(gè)約束條件分別加入問題LP，將問題LP分為兩個(gè)后繼問題LP1和LP2，不考慮整數(shù)條件要求，求解LP1和LP2，以每一個(gè)后繼子問題為一分支并標(biāo)明求解的結(jié)果，與其他問題的解的結(jié)果一道，找出最優(yōu)目標(biāo)函數(shù)值最小者作為新的下

13、界，替換 ,從已符合整數(shù)條件的各分支中，找出目標(biāo)數(shù)值為最小者作為新的上界 ,即有 。 （3）比較與剪支 各分支的最優(yōu)目標(biāo)函數(shù)中若有大于 者，則剪掉這一支（即這一支所代表的子問題已無繼續(xù)分解的必要）；若小于 ，且不符合整數(shù)條件，則重復(fù)第一步驟，一直到最后得到的最優(yōu)目標(biāo)函數(shù)值 為止，從而得到最優(yōu)整數(shù)解 。,分支定界法的MATLAB實(shí)現(xiàn) 因?yàn)镸ATLAB本身并沒有提供求解線性整數(shù)規(guī)劃問題的函數(shù)，所以我們有必要根據(jù)分支定界法的步驟自行設(shè)計(jì)其求解函數(shù)，但是幸運(yùn)的是Thomas Trtscher編寫了函數(shù)miprog()及幾個(gè)附帶函數(shù)，這幾個(gè)函數(shù)可以從以下網(wǎng)址上下載： 該函數(shù)的調(diào)用格式為： x_best

14、= miprog(f,A,b,Aeq,beq,lb,ub,yidx,options) 其中，參數(shù)yidx為整數(shù)變量指標(biāo)列向量，1代表整數(shù)，0代表實(shí)數(shù)。注意：這里的yidx是一個(gè)邏輯向量，且它至少要含有一個(gè)邏輯1。,二、非線性整數(shù)規(guī)劃（NLIP） 一般非線性整數(shù)規(guī)劃的數(shù)學(xué)描述為： 同樣地，MATLAB最優(yōu)化工具箱中沒有提供求解一般非線性規(guī)劃問題的函數(shù)。不過幸好荷蘭Groningen大學(xué)的Koert Kuipers編寫了函數(shù)bnb20()直接求解一般非線性整數(shù)規(guī)劃的問題。該函數(shù)可以從以下網(wǎng)址下載： 該函數(shù)也是基于分支定界的思想設(shè)計(jì)的，該函數(shù)的一般調(diào)用格式為： errmsg,f,x,t,c,fail

15、=bnb20(fun,x0,xstatus,lb,ub,A,b,Aeq,beq,nonlcon,settings, options,p1,p2,.),三、0-1規(guī)劃 所謂0-1規(guī)劃，即指自變量的值或者為0，或者為1。所以求解0-1規(guī)劃看起來很簡(jiǎn)單，讓每個(gè)自變量遍取0,1，在得出的組合中選擇既滿足約束條件又使目標(biāo)函數(shù)取最小值的項(xiàng)。但這種完全窮舉法的思想也僅適用于小規(guī)模問題。故仍然需要考慮其他算法進(jìn)行求解。 自MATLAB 7.0版本起，MATLAB最優(yōu)化工具箱中提供了一個(gè)新函數(shù)bintprog()專門用來求解0-1規(guī)劃問題。該函數(shù)的調(diào)用格式為： x,fval,exitflag,output =

16、bintprog(f,A,b,Aeq,beq,x0,options),一、動(dòng)態(tài)規(guī)劃的基本概念 使用動(dòng)態(tài)規(guī)劃方法解決多階段決策問題，首先要將實(shí)際問題寫成動(dòng)態(tài)規(guī)劃模型，同時(shí)也為了今后敘述和討論方便，這里需要對(duì)動(dòng)態(tài)規(guī)劃的下述一些基本術(shù)語進(jìn)一步加以說明和定義：(一) 階段和階段變量 為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。通常，階段是按決策進(jìn)行的時(shí)間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目。,11.7 動(dòng)態(tài)規(guī)劃,（二）狀態(tài)、狀態(tài)變量和

17、可能狀態(tài)集 1.狀態(tài)與狀態(tài)變量： 描述事物(或系統(tǒng))在某特定的時(shí)間與空間域中所處位置及運(yùn)動(dòng)特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量包含在給定的階段上確定全部允許決策所需要的信息。每個(gè)階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止?fàn)顟B(tài)記為sk+1。通常定義階段的狀態(tài)即指其初始狀態(tài)。 2可能狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達(dá)狀態(tài)集。可能狀態(tài)集實(shí)際上是關(guān)于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，skSk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題

18、而定 （三）決策、決策變量和允許決策集合 決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。用以描述決策變化的量稱之決策變量。決策變量的值可以用數(shù)，向量、其它量，也可以是狀態(tài)變量的函數(shù)，記以u(píng)k= uk(sk)，表示于階段k狀態(tài)sk時(shí)的決策變量。 決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示, uk(sk) Uk(sk) 允許決策集合實(shí)際是決策的約束條件。,（四）策略和允許策略集合 策略(Policy)也叫決策序列策略有全過程策略和k部子策略之分，全過程策略是指由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策序列，簡(jiǎn)

19、稱策略，表示為p1,nu1,u2,un。從k階段到第n階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,nuk,uk+1,un ，顯然當(dāng)k=1時(shí)的k部子策略就是全過程策略。 在實(shí)際問題中，由于在各個(gè)階段可供選擇的決策有許多個(gè)，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n ，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。 （五）狀態(tài)轉(zhuǎn)移方程 系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即系統(tǒng)由階段k的初始狀態(tài)sk轉(zhuǎn)移到終止?fàn)顟B(tài)sk+1 。 對(duì)于具有無后效性的多階段決策過程,系統(tǒng)由階段k

20、到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k的狀態(tài)sk和決策 uk(sk) 所確定，與系統(tǒng)過去的狀態(tài) s1, s2, , sk -1及其決策u1(s1), u2(s2)，uk-1(sk-1)無關(guān)。 系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公式描述即有： 通常稱上式為多階段決策過程的狀態(tài)轉(zhuǎn)移方程。有些問題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。,(六) 指標(biāo)函數(shù) 用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對(duì)不同問題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤(rùn)、產(chǎn)量、耗量、距離、時(shí)間、效用，等等。 1)階段指標(biāo)函

21、數(shù)（階段效應(yīng)） 用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時(shí)的指標(biāo)，則它就是第k段指標(biāo)函數(shù)，簡(jiǎn)記為gk 2)過程指標(biāo)函數(shù)（目標(biāo)函數(shù)） 用Rk(sk,uk)表示第k子過程的指標(biāo)函數(shù)。Rk(sk,uk) 不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子過程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的函數(shù)，嚴(yán)格說來，應(yīng)表示為: 實(shí)際應(yīng)用中上式可表示為 Rk(sk,uk) 或 Rk(sk) ； 過程指標(biāo)函數(shù) Rk(sk) 通常是描述所實(shí)現(xiàn)的全過程或 k 后部子過程效果優(yōu)劣的數(shù)量指標(biāo)，它是由各階段的階段指標(biāo)函數(shù) gk(sk,uk) 累積形成的。,適于用動(dòng)態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式對(duì)于k部子過程的指標(biāo)函數(shù)可以表示為： （表示某種運(yùn)算） 多階段決策問題中，常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即: 有些問題，如系統(tǒng)可靠性問