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

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

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

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

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

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

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

7、供了多維無約束非線性優(yōu)化的求解函數(shù)fminunc，在MATLAB的該求解函數(shù)中運用到了我們前面提到的多種算法，例如利用梯度信息或者Hessian矩陣信息的迭代算法，或者如果用戶不提供梯度信息的話，可能使用到有限差分形式去估計相應(yīng)值的方法。在下面函數(shù)使用過程中的算法和參數(shù)的設(shè)置時，將會重點講述這些問題 調(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(.),多維無約束優(yōu)化的求解函數(shù)fminunc,輸入?yún)?shù)和輸出參數(shù),多維無約束優(yōu)化的求解函數(shù)fminunc,多維無約束優(yōu)化的求解函數(shù)fminunc,fminunc的輸出參數(shù)主要包括x、fval、grad、hessian、exitflag、output，其中g(shù)rad和hessian分 別返回x處的梯度和Hessian矩陣信息。算法終止時狀態(tài)指示結(jié)構(gòu)變量exitflag取值代表的物理意義和輸出參數(shù)outpu

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

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

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

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

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

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

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