最優(yōu)化模型與算法

最優(yōu)化模型與算法2內(nèi)容概要優(yōu)化模型簡(jiǎn)介優(yōu)化模型分類(lèi)優(yōu)化算法及其分類(lèi)Matlab優(yōu)化工具箱現(xiàn)代智能優(yōu)化算法3優(yōu)化模型簡(jiǎn)介——概念、基本形式什么是優(yōu)化？就是從各種方案中選取一個(gè)最好的。從數(shù)學(xué)角度看，優(yōu)化理論就是研究如何在狀態(tài)空間中尋找到全局最優(yōu)點(diǎn)。一般的優(yōu)化具有下面形式：

minf(x1,x2,…,xn) s.t.g(x)

0，x

D

其中x1,x2,…,xn

Ω（即問(wèn)題的可行域，代表問(wèn)題參數(shù)的選擇范圍），即minf(X)，其中X

Ω（矢量形式）。f(x)是決策問(wèn)題的數(shù)學(xué)模型，也是決策問(wèn)題的目標(biāo)函數(shù)，g(x)

0是決策問(wèn)題的約束條件，X是決策問(wèn)題的決策變量，D是決策問(wèn)題的定義域（可行域）。問(wèn)題歸結(jié)為求極值。極值點(diǎn)非常多，需要找到全局最小點(diǎn)。 注：求問(wèn)題的最大和最小是同一個(gè)問(wèn)題，算法完全一樣。分布模型的參數(shù)估計(jì)問(wèn)題是典型的優(yōu)化問(wèn)題，最大似然估計(jì)模型是典型的優(yōu)化模型。4優(yōu)化模型分類(lèi)1.根據(jù)是否存在約束條件有約束模型，無(wú)約束模型注：有約束問(wèn)題通常采用轉(zhuǎn)換方法將有約束模型轉(zhuǎn)換為無(wú)約束模型再求解。2.根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì)

線(xiàn)性規(guī)劃，非線(xiàn)性規(guī)劃，二次規(guī)劃，多目標(biāo)規(guī)劃等注：最常見(jiàn)的優(yōu)化模型為非線(xiàn)性規(guī)劃模型。3.根據(jù)決策變量的連續(xù)性

連續(xù)性?xún)?yōu)化模型，離散性?xún)?yōu)化模型（典型的組合優(yōu)化問(wèn)題，最短路）注：兩類(lèi)模型在求解方法上有較大不同，本次講解針對(duì)前一種。5優(yōu)化算法及其分類(lèi)什么是優(yōu)化算法？專(zhuān)門(mén)用于求解優(yōu)化模型的方法叫做優(yōu)化算法，優(yōu)化算法與優(yōu)化模型有本質(zhì)區(qū)別。優(yōu)化算法可分為兩大類(lèi)1梯度類(lèi)算法

牛頓法、二分法、共軛梯度法、梯度下降法、單純形法等，該類(lèi)算法也稱(chēng)為局部?jī)?yōu)化算法，明顯缺陷是局部?jī)?yōu)化。Matlab優(yōu)化工具箱多用該類(lèi)算法。2非梯度類(lèi)算法

（1）遍歷搜索法，在組合優(yōu)化中稱(chēng)為窮舉法，計(jì)算量大，適用于小規(guī)模計(jì)算求解。

（2）隨機(jī)搜索法，包括遺傳算法、模擬退火算法、群類(lèi)算法、禁忌搜索法等，又稱(chēng)為現(xiàn)代優(yōu)化算法，是一類(lèi)全局最優(yōu)算法，求解的準(zhǔn)確性與時(shí)間長(zhǎng)度、迭代次數(shù)直接相關(guān)。常用的優(yōu)化功能函數(shù)求解線(xiàn)性規(guī)劃問(wèn)題的主要函數(shù)是linprog。求解二次規(guī)劃問(wèn)題的主要函數(shù)是quadprog。求解無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題的主要函數(shù)是fminbnd、fminunc和fminsearch。求解約束非線(xiàn)性規(guī)劃問(wèn)題的函數(shù)是

fmincon

。多目標(biāo)優(yōu)化問(wèn)題的MATLAB函數(shù)有fgoalattain和fminimax。MATLAB優(yōu)化工具箱優(yōu)化求解一般步驟

建立目標(biāo)函數(shù)文件

針對(duì)具體工程問(wèn)題建立優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型不等式約束條件表示成g(X)≤0的形式

建立調(diào)用優(yōu)化工具函數(shù)的M文件或命令文件建立約束函數(shù)文件運(yùn)行優(yōu)化工具函數(shù)的M文件或命令文件求解

minf(x1,x2,…,xn)s.t.g(x)≤0無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題的MATLAB函數(shù)fminbnd要求目標(biāo)函數(shù)為連續(xù)函數(shù)只求解單變量問(wèn)題fminunc可求解單變量和多變量問(wèn)題適用于簡(jiǎn)單優(yōu)化問(wèn)題可求解復(fù)雜優(yōu)化問(wèn)題fminsearch[xopt,fopt,exitflag]=fminsearch(fun,x0,options)無(wú)約束多元函數(shù)最小值函數(shù)fminsearch調(diào)用格式設(shè)置優(yōu)化選項(xiàng)參數(shù)初始點(diǎn)目標(biāo)函數(shù)返回最優(yōu)設(shè)計(jì)變量返回目標(biāo)函數(shù)值返回算法的終止指示變量值例

求y=2x13

+4x1x23-10x1x2+x22

的最小值點(diǎn).解：>>X=fminsearch('2*x(1)^3+4*x(1)*x(2)^3-10*x(1)*x(2)+x(2)^2',[0,0])結(jié)果為:

X=1.00160.8335或在MATLAB編輯器中建立函數(shù)文件.functionf=myfun(x)f=2*x(1)^3+4*x(1)*x(2)^3-10*x(1)*x(2)+x(2)^2;保存為myfun.m，在命令窗口鍵入>>X=fminsearch('myfun',[0,0])或>>X=fminsearch(@myfun,[0,0])結(jié)果為：X=1.00160.8335有約束的多元函數(shù)最小值數(shù)學(xué)模型形式：

minf（X）

s.t.AX≤b（線(xiàn)性不等式約束）

AeqX=beq（線(xiàn)性等式約束）

C(X)≤0（非線(xiàn)性不等式約束條件）

Ceq(X)=0（非線(xiàn)性等式約束）

Lb≤X≤Ub（邊界約束條件）其中：x、b、beq、lb、ub是向量，A、Aeq為矩陣，C(x)、Ceq(x)是返回向量的函數(shù)，f(x)為目標(biāo)函數(shù)，f(x)、C(x)、Ceq(x)可以是非線(xiàn)性函數(shù).函數(shù)

fmincon格式

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,fval]=fmincon(…)[x,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(…)參數(shù)說(shuō)明：fun為目標(biāo)函數(shù)，它可用前面的方法定義；nonlcon的作用是通過(guò)接受的向量x來(lái)計(jì)算非線(xiàn)性不等約束和非線(xiàn)性等式約束分別在x處的估計(jì)C和Ceq，通過(guò)指定函數(shù)名或函數(shù)名句柄來(lái)使用，如：>>x=fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@mycon)，先建立非線(xiàn)性約束函數(shù)，并保存為mycon.m：function[C,Ceq]=mycon(x)C=…%計(jì)算x處的非線(xiàn)性不等約束的函數(shù)值.Ceq=…%計(jì)算x處的非線(xiàn)性等式約束的函數(shù)值.lambda是Lagrange乘子，它體現(xiàn)哪一個(gè)約束有效.output輸出優(yōu)化信息；grad表示目標(biāo)函數(shù)在x處的梯度；hessian表示目標(biāo)函數(shù)在x處的Hessian值.控制參數(shù)options序號(hào)功能默認(rèn)值及其含義說(shuō)明1輸出形式0，無(wú)中間結(jié)果輸出Options(1)=1,按照表格輸出結(jié)果Options(1)=-1,隱藏警告信息2解x的精度1e-4Options(2)設(shè)置x解的終止條件3函數(shù)f的精度1e-4Options(3)設(shè)置函數(shù)f的終止條件4約束g的精度1e-6Options(4)設(shè)置約束g的終止條件5選擇主要算法0Options(5)選擇主要優(yōu)化算法6搜索方向算法0fmin()函數(shù)為無(wú)約束優(yōu)化搜索方向提供3種算法：Options(6)=0,擬牛頓法BFGS公式Options(6)=1,擬牛頓法DFP公式Options(6)=2,梯度法7步長(zhǎng)一維搜索0fmin()函數(shù)為無(wú)約束優(yōu)化的步長(zhǎng)一維搜索提供2種算法：Options(7)=0,二次和三次混合插值法Options(7)=1,三次多項(xiàng)式插值法控制參數(shù)options序號(hào)功能默認(rèn)值及其含義說(shuō)明8函數(shù)值輸出Options(8)輸出最終迭代函數(shù)值9梯度檢驗(yàn)0，不檢驗(yàn)Options(9)比較梯度10函數(shù)計(jì)算次數(shù)Options(10)輸出函數(shù)計(jì)算次數(shù)11梯度計(jì)算次數(shù)Options(11)輸出函數(shù)梯度計(jì)算次數(shù)12約束計(jì)算次數(shù)Options(12)輸出約束計(jì)算次數(shù)13等式約束個(gè)數(shù)0，等式約束為0Options(13)輸入等式約束個(gè)數(shù)14最大迭代次數(shù)100n（n為變量維數(shù)）Options(14)輸入最大迭代次數(shù)15目標(biāo)個(gè)數(shù)0Options(15)輸入目標(biāo)個(gè)數(shù)16差分步長(zhǎng)最小值1e-8Options(16)步長(zhǎng)的下限或變量的最小梯度值17差分步長(zhǎng)最大值0.1Options(17)步長(zhǎng)的上限或變量的最大梯度值18步長(zhǎng)Options(18)步長(zhǎng)參數(shù)，第1次迭代時(shí)置1【例】求解約束非線(xiàn)性規(guī)劃：解:首先建立一個(gè)m文件myfun.mfunctiony=myfun(x)y=-exp(x(1))*x(2)^2*(3-exp(x(1))-x(2)^2);存儲(chǔ)為myfun.m首先將問(wèn)題轉(zhuǎn)化為matlab要求的格式;即求出fun,A,b,Aeq,Beq,X0,Lb,Ub然后建立一個(gè)

m文件

confun.mfunction[c,cep]=confun(x)c=[];%c為非線(xiàn)性不等式cep=exp(x(1))+x(2)^2-3;%cep為非線(xiàn)性等式然后存儲(chǔ)為confun.m最后在命令窗口中輸入：A=[];b=[];Aeq=[];beq=[];Lb=[];Ub=[];[x,f]=fmincon(‘myfun’,[1;1],[],[],[],[],[],[],’confun’)

題目中有非線(xiàn)性約束條件，所以建立非線(xiàn)性約束m-文件。x=0.88520.7592f=6.2043e-016優(yōu)化過(guò)程演示為了進(jìn)一步了解優(yōu)化模型的求解算法，給出具體實(shí)例的優(yōu)化過(guò)程演示。例：以共軛梯度優(yōu)化算法優(yōu)化某函數(shù)進(jìn)行演示,并說(shuō)明計(jì)算時(shí)間復(fù)雜度。18現(xiàn)代優(yōu)化算法遺傳算法

模擬退火算法

禁忌搜索算法

蟻群算法粒子群算法差分進(jìn)化算法特點(diǎn)：基于客觀世界中的一些自然現(xiàn)象；建立在計(jì)算機(jī)迭代計(jì)算的基礎(chǔ)上；都屬于隨機(jī)搜索算法，具有全局優(yōu)化能力；具有普適性，可解決實(shí)際應(yīng)用問(wèn)題。注：群類(lèi)算法還有魚(yú)群算法、蜂群算法、鳥(niǎo)群算法等?，F(xiàn)代優(yōu)化算法20現(xiàn)代優(yōu)化算法——全局性?xún)?yōu)化理論的一般性描述兩種搜索方式：?jiǎn)吸c(diǎn)法和多點(diǎn)法。單點(diǎn)法是一種串行方式，即從一個(gè)初始狀態(tài)（單個(gè)個(gè)體）出發(fā)，按照某種方式轉(zhuǎn)移狀態(tài)進(jìn)行全局優(yōu)化，這種方式通常要消耗較多機(jī)時(shí)；多點(diǎn)法是一種并行方式，即從可行域的多個(gè)初始狀態(tài)（多個(gè)個(gè)體）同時(shí)進(jìn)行搜索尋找全局最優(yōu)解，但是空間開(kāi)銷(xiāo)大。根據(jù)各態(tài)歷經(jīng)假設(shè)，理論上二者可以具有相同的搜索效果。事實(shí)上，單CPU情況下的單點(diǎn)法和多點(diǎn)法并沒(méi)有本質(zhì)性的區(qū)別。模擬退火算法及模型

算法的提出

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。物理退火過(guò)程算法的目的解決NP復(fù)雜性問(wèn)題；克服優(yōu)化過(guò)程陷入局部極??；克服初值依賴(lài)性。什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。物理退火過(guò)程模擬退火算法及模型

Metropolis準(zhǔn)則——以概率接受新?tīng)顟B(tài)

物理退火過(guò)程

固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用MonteCarlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。若在溫度