非線(xiàn)性規(guī)劃_多維無(wú)約束優(yōu)化_0507.ppt

1、第六章 非線(xiàn)性規(guī)劃 多維無(wú)約束非線(xiàn)性?xún)?yōu)化,概述,多維無(wú)約束優(yōu)化問(wèn)題是指在沒(méi)有任何限制條件下尋求目標(biāo)函數(shù)的極小點(diǎn)。其表達(dá)形式為： 研究無(wú)約束優(yōu)化問(wèn)題的意義： 在求解有約束優(yōu)化問(wèn)題的解時(shí)，有一大類(lèi)解法是通過(guò)對(duì)約束條件的處理，把有約束問(wèn)題變成一系列無(wú)約束的問(wèn)題進(jìn)行求解。研究無(wú)約束優(yōu)化問(wèn)題的解，也為研究約束優(yōu)化問(wèn)題的解法打下基礎(chǔ)； 在實(shí)際問(wèn)題中，某些實(shí)際問(wèn)題的數(shù)學(xué)模型本身也可能是一個(gè)無(wú)約束優(yōu)化問(wèn)題。 在研究最優(yōu)化問(wèn)題時(shí)，通常首先要研究無(wú)約束問(wèn)題的最優(yōu)化問(wèn)題。無(wú)約束優(yōu)化問(wèn)題求解的方法有多種，它們的主要不同點(diǎn)在于如何構(gòu)造搜索方向。,最速下降法,基本思想 最速下降法由法國(guó)數(shù)學(xué)家Cauchy于1847年首先提

2、出。該算法在每次迭代中，沿最速下降方向（負(fù)梯度方向）進(jìn)行搜索，每步沿負(fù)梯度方向取最優(yōu)步長(zhǎng)，因此這種方法稱(chēng)為最優(yōu)梯度法 算法特點(diǎn) 最速下降法方法簡(jiǎn)單，只以一階梯度的信息確定下一步的搜索方向，收斂速度慢；越是接近極值點(diǎn)，收斂越慢 它是其它許多無(wú)約束、有約束最優(yōu)化方法的基礎(chǔ)。該法一般用于最優(yōu)化開(kāi)始的幾步搜索。,最速下降法,算法分析,最速下降法,最速下降法由初始點(diǎn)向最優(yōu)點(diǎn)迭代過(guò)程示意圖,最速下降法,算法步驟,最速下降法,最速下降法的特點(diǎn),牛頓法,概述 為了尋找收斂速度快的無(wú)約束最優(yōu)化方法，我們考慮在每次迭代時(shí)，用適當(dāng)?shù)亩魏瘮?shù)去近似目標(biāo)函數(shù)，并用迭代點(diǎn)指向近似二次函數(shù)極小點(diǎn)的方向來(lái)構(gòu)造搜索方向，然后精

3、確地求出近似二次函數(shù)的極小點(diǎn)，以該極小點(diǎn)作為的極小點(diǎn)的近似值這就是Newton切線(xiàn)法的基本思想，它是Newton切線(xiàn)法的推廣,牛頓法,算法分析,牛頓法,迭代步驟,牛頓法,例1 用牛頓法求函數(shù)的極小點(diǎn),牛頓法,牛頓法的收斂性質(zhì),阻尼牛頓法,算法思想 在牛頓法的實(shí)際操作中必須要選擇一個(gè)具有較優(yōu)目標(biāo)值的初始點(diǎn)，但這往往是困難的。為了克服這個(gè)缺點(diǎn)，人們提出了“阻尼牛頓法”對(duì)此進(jìn)行修正。,阻尼牛頓法,迭代步驟,阻尼牛頓法,收斂性質(zhì),阻尼牛頓法,例1 利用阻尼牛頓法求解非線(xiàn)性規(guī)劃問(wèn)題 取初始點(diǎn) ，則,利用牛頓法和阻尼牛頓法求解二次型,共軛方向法,基本思想,共軛方向法,理論基礎(chǔ),共軛方向法,共軛的性質(zhì),共軛

4、方向法,原理,共軛方向法,迭代步驟,共軛梯度法,基本思想,共軛梯度法,迭代步驟,共軛梯度法,FR公式,共軛梯度法,PRP公式和DM公式 與FR公式類(lèi)似，我們還還可以采用Polak-Ribilere-Polyak(PRP)公式和Dixon-Myers公式。其形式分別為 FR、 PRP、DM這三個(gè)公式對(duì)于二次型函數(shù)問(wèn)題的求解效果相同，對(duì)于非二次型函數(shù)在數(shù)值計(jì)算上會(huì)有差異，結(jié)果也會(huì)有所不同。,共軛梯度法,例1 利用FR法求解無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題,擬牛頓法,什么是擬牛頓法 擬牛頓法的優(yōu)點(diǎn) 僅需一階導(dǎo)數(shù)（牛頓法需二階導(dǎo)數(shù)） 保持正定，使得方法具有下降性質(zhì) 每次迭代需 次乘法運(yùn)算（牛頓法需 次乘法運(yùn)算）

5、搜索方向是相互共軛的，從而具有二次終止性,變尺度算法,概述 變尺度法又稱(chēng)Davidon-Fletcher-Powell(DFP)算法，這是因?yàn)樵撍惴ㄔ?959年由Davidon提出，后來(lái)經(jīng)Fletcher和Powell解釋并改進(jìn)而得名。它是變尺度算法中提得最早的一個(gè)，該算法超線(xiàn)性收斂，對(duì)解多元函數(shù)的無(wú)約束極小是一個(gè)比較好的方法。該算法屬于擬牛頓法的一種，變尺度法是求解無(wú)約束極值問(wèn)題的一種有效方法，由于它避免了計(jì)算二階導(dǎo)數(shù)矩陣及其求逆計(jì)算，又比梯度法的收斂速度快，特別是對(duì)高維問(wèn)題具有顯著的優(yōu)越性，因而使變尺度法獲得了很高的聲譽(yù)，被稱(chēng)之為在算法上有“突破”。例如在1962年以前，由于原有各種算法計(jì)

6、算耗時(shí)太多，因而求解非線(xiàn)性函數(shù)的極小值一般只能計(jì)算10個(gè)變量以下的問(wèn)題，而應(yīng)用了DFP法，可以在幾分鐘內(nèi)計(jì)算出100個(gè)變量的函數(shù)極小值，有的問(wèn)題只用半分鐘即可解出。而相應(yīng)的問(wèn)題用其它算法求解，則要30分鐘才能解出。 變尺度法和共軛梯度法一樣，都是為了克服梯度法收斂慢和Newton法計(jì)算工作量大的缺點(diǎn)而提出來(lái)的一種算法。,變尺度算法,基本思想,變尺度算法,DFP算法 BFGS算法,變尺度算法,迭代步驟,變尺度算法,例1 利用變尺度算法求解無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題,變尺度算法,變尺度算法,變尺度算法,變尺度算法和共軛梯度法的統(tǒng)一,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,概述 MATLAB優(yōu)化工具箱中提

7、供了多維無(wú)約束非線(xiàn)性?xún)?yōu)化的求解函數(shù)fminunc，在MATLAB的該求解函數(shù)中運(yùn)用到了我們前面提到的多種算法，例如利用梯度信息或者Hessian矩陣信息的迭代算法，或者如果用戶(hù)不提供梯度信息的話(huà)，可能使用到有限差分形式去估計(jì)相應(yīng)值的方法。在下面函數(shù)使用過(guò)程中的算法和參數(shù)的設(shè)置時(shí)，將會(huì)重點(diǎn)講述這些問(wèn)題 調(diào)用格式： x = fminunc(fun,x0) x = fminunc(fun,x0,options) x = fminunc(problem) x,fval = fminunc(.) x,fval,exitflag = fminunc(.) x,fval,exitflag,output =

8、fminunc(.) x,fval,exitflag,output,grad = fminunc(.) x,fval,exitflag,output,grad,hessian = fminunc(.),多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,輸入?yún)?shù)和輸出參數(shù),多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,fminunc的輸出參數(shù)主要包括x、fval、grad、hessian、exitflag、output，其中g(shù)rad和hessian分 別返回x處的梯度和Hessian矩陣信息。算法終止時(shí)狀態(tài)指示結(jié)構(gòu)變量exitflag取值代表的物理意義和輸出參數(shù)outpu

9、t結(jié)構(gòu)變量中所包含的信息分別如表所示：,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,控制參數(shù)設(shè)置方法（打開(kāi)word文檔即可查看） 命令詳解 x = fminunc(fun,x0) 從初始點(diǎn)x0開(kāi)始尋找目標(biāo)函數(shù)fun的局部極小點(diǎn)x，x0可以是標(biāo)量、向量或矩陣 x = fminunc(fun,x0,options) 在求解問(wèn)題的同時(shí)用options指定的優(yōu)化參數(shù)進(jìn)行目標(biāo)函數(shù)的最小化 x,fval = fminunc(.) 返回最優(yōu)解x處的目標(biāo)函數(shù)值fval x,fval,exitflag = fminunc(.) 在優(yōu)化計(jì)算結(jié)束之時(shí)返回exitflag值，描述函數(shù)計(jì)算的退出條件 x,fval,exit

10、flag,output = fminunc(.) 在優(yōu)化計(jì)算結(jié)束之時(shí)返回返回結(jié)構(gòu)變量output x,fval,exitflag,output,grad = fminunc(.) 在優(yōu)化計(jì)算結(jié)束之時(shí)返回解x處的梯度 x,fval,exitflag,output,grad,hessian = fminunc(.) 在優(yōu)化計(jì)算結(jié)束之時(shí)返回解x處的Hessian矩陣,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,fminunc可以根據(jù)用戶(hù)選擇的不同參數(shù)，選用不同的優(yōu)化方法 大型優(yōu)化算法 若用戶(hù)在fun函數(shù)中提供梯度信息，則默認(rèn)時(shí)函數(shù)將選擇大型優(yōu)化算法，該 算法是基于內(nèi)部映射牛頓法的子空間置信域法。計(jì)算中的

11、每一次迭代涉及用 PCG法求解大型線(xiàn)性系統(tǒng)得到的近似解。 中型優(yōu)化算法 當(dāng)不使用大型規(guī)模算法，即通過(guò)optimset將options.LargeScale設(shè)置為off時(shí)， fminunc在優(yōu)化過(guò)程中選用BFGS擬牛頓法，即通過(guò)BFGS校正來(lái)更新對(duì)目標(biāo)函數(shù) 的Hessian矩陣的估計(jì)值。 我們可以將參數(shù)HessUpdate設(shè)置為dfp使得fminunc采用DFP校正來(lái)更新對(duì)目標(biāo)函數(shù)的Hessian矩陣的逆的估計(jì)；將HessUpdate設(shè)置為steepdesc同時(shí)將LargeScale設(shè)置為off，則此時(shí)使用最速下降法，但是一般不推薦使用最速下降法。 在此強(qiáng)調(diào)一下，當(dāng)使用大型規(guī)模算法時(shí)，必須在定義

12、目標(biāo)函數(shù)的M-函數(shù)文件中給出梯度向量的解析形式，同時(shí)設(shè)置控制參數(shù)GradObj的值為on，當(dāng)沒(méi)有設(shè)置控制參數(shù)LargeScale為off，且用戶(hù)沒(méi)有提供梯度向量的計(jì)算公式時(shí)，MATLAB將返回一個(gè)警告信息。,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,fminunc在求解無(wú)約束最優(yōu)化問(wèn)題時(shí)的局限性 最優(yōu)化問(wèn)題的目標(biāo)函數(shù)必須是連續(xù)的，且fminunc不能保證給出的是全局最優(yōu)解，有時(shí)會(huì)給出局部最優(yōu)解。 fminunc只能對(duì)實(shí)數(shù)進(jìn)行優(yōu)化，即設(shè)計(jì)變量x的值只能為實(shí)數(shù)，且f(x)必須返回實(shí)數(shù)，當(dāng)x為復(fù)數(shù)時(shí)，必須將其分解成實(shí)部和虛部。 fminunc不適合用于求解目標(biāo)函數(shù)為函數(shù)平方的問(wèn)題，即若最優(yōu)問(wèn)題具有如下

13、形式的目標(biāo)函數(shù)： 則最好使用lsqnonlin函數(shù)進(jìn)行求解。,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,例1 求解下述無(wú)約束最優(yōu)化問(wèn)題,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,例2 求解無(wú)約束最優(yōu)化問(wèn)題 其中n=1000 方法一：利用梯度向量和Hessian矩陣的精確計(jì)算公式,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,方法二：利用梯度向量和Hessian矩陣的稀疏形式,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,多維無(wú)約束優(yōu)化的求解函數(shù)fminunc,例3 使用匿名函數(shù)調(diào)用求解無(wú)約束

14、最優(yōu)化問(wèn)題 其中a=3，b=2，c=5,多維無(wú)約束優(yōu)化的求解函數(shù)fminsearch,概述 MATLAB中求解無(wú)約束優(yōu)化問(wèn)題還可以調(diào)用fminsearch函數(shù)，該函數(shù)和fminunc不同，因?yàn)閒minsearch進(jìn)行尋優(yōu)的算法基于不使用梯度的單純形法。其應(yīng)用范圍也是無(wú)約束的多維非線(xiàn)性規(guī)劃問(wèn)題。 fminsearch和fminbnd類(lèi)似，不同之處在于fminsearch解決的是多維函數(shù)的尋優(yōu)問(wèn)題，而且在fminsearch中指定的是初始點(diǎn)，而在fminbnd指定的是一個(gè)搜索的區(qū)間。fminsearch的尋優(yōu)過(guò)程實(shí)際上就是在初始點(diǎn)附近找到最優(yōu)化問(wèn)題目標(biāo)函數(shù)的一個(gè)局部極小點(diǎn)。 由于函數(shù)fminsea

15、ch的輸入輸出參數(shù)以及函數(shù)使用方法很多地方均和fminunc類(lèi)似，故在此不再詳細(xì)贅述，本節(jié)在進(jìn)行一個(gè)簡(jiǎn)單的用法總結(jié)之后，給出fminsearch的幾個(gè)應(yīng)用實(shí)例。 函數(shù)fminsearch的輸入?yún)?shù)有fun,x0和options；輸出參數(shù)有x、fval、exitflag和output；其可以設(shè)置的控制參數(shù)包括Display、FunValCheck、MaxFunEvals、MaxIter、OutputFcn、PlotFcns、TolFun、TolX，具體方法和fminunc類(lèi)似，讀者可以自行翻閱幫助信息。,多維無(wú)約束優(yōu)化的求解函數(shù)fminsearch,調(diào)用方法 x = fminsearch(fun,x0) 從初始點(diǎn)x0開(kāi)始尋找目標(biāo)函數(shù)fun的局部極小點(diǎn)x，x0可以是標(biāo)量、向量或矩陣。 x = fminsearch(fun,x0,options) 在求解問(wèn)題的同時(shí)用options指定的優(yōu)化參數(shù)進(jìn)行目標(biāo)函數(shù)的最小化， x,fval = fminsearch(.) 返回最優(yōu)解x處的目