1、非線性規(guī)劃基本概念 （1學(xué)時(shí)）一維搜索 （1學(xué)時(shí)） 重 點(diǎn)：下降迭代算法、黃金分割法、二次插值法。難 點(diǎn)：下降迭代算法構(gòu)造基本要求：了解非線性規(guī)劃的分類，掌握梯度的計(jì)算和性質(zhì)，會用海賽陣判斷凸規(guī)劃，掌握用黃金分割法、二次插值法。第6講 非線性規(guī)劃及一維搜索（第3章）1非線性規(guī)劃基本概念（3.1）1 非線性規(guī)劃模型分類一般無約束極值形式為：一般有約束極值問題形式為：2例1 在層次分析（Analytic Hierarchy Process, 簡記為 AHP）中，為了進(jìn)行多屬性的綜合評價(jià)，需要確定每個(gè)屬性的相對重要性，即它們各自的權(quán)重。為此，將各屬性進(jìn)行兩兩比較可得如下判斷矩陣： 其中：是第個(gè)屬性與

2、第個(gè)屬性的重要性之比。 現(xiàn)需要從判斷矩陣求出各屬性的權(quán)重，為使求出的權(quán)重向量在最小二乘意義上能最好地反映判斷矩陣的估計(jì)，建立數(shù)學(xué)模型：有約束極值問題3例2 模型參數(shù)識別問題 設(shè)已知某問題的數(shù)學(xué)模型為 試驗(yàn)測得在時(shí)刻時(shí) 的值為試用其估計(jì)參數(shù) 。建立問題為的數(shù)學(xué)模型采用最小二乘法問題轉(zhuǎn)化為求解無約束極值問題42 多元函數(shù)的極值問題（1）梯度及Hesse 矩陣 梯度Hesse矩陣5 例3：求下列函數(shù)的梯度： 解：6解：7例4 求目標(biāo)函數(shù) f（X）=的梯度和Hesse矩陣。解： 則 又因?yàn)椋?故Hesse陣為： 8 （2）局部極值和全局極值極小點(diǎn)局部極小點(diǎn)全局極小點(diǎn)嚴(yán)格局部極小點(diǎn)非嚴(yán)格局部極小點(diǎn)非嚴(yán)格

3、全局極小點(diǎn)嚴(yán)格全局極小點(diǎn)例如：圖中一元函數(shù)f定義在區(qū)間a b上 為嚴(yán)格局部極小點(diǎn)， 非嚴(yán)格局部極小點(diǎn) a為嚴(yán)格全局極小點(diǎn)9凸（凹）函數(shù)定義: 設(shè)函數(shù) 在凸集 上有定義,如果對任意 和 屬于 及任何實(shí)數(shù)（ ） 則稱 是 上的凸函數(shù). （3）凸函數(shù)、凹函數(shù)及凸規(guī)劃凸（凹）函數(shù)二階判別定理： 設(shè) 是 非空開凸集 上的二階連續(xù)可微函數(shù)，則 為凸函數(shù)的充分必要條件是 在 上半正（負(fù)）定。1011凸規(guī)劃若 為凸函數(shù) 為凹函數(shù) ， 則該非線性規(guī)劃為凸規(guī)劃。定義：12凸規(guī)劃性質(zhì)：設(shè) 是凸規(guī)劃問題的一個(gè)局部最優(yōu)解，則 是全局最優(yōu)解。如果 是嚴(yán)格凸函數(shù)，則 是唯一全局最優(yōu)解。證明：反證法 設(shè) 是凸規(guī)劃的局部最優(yōu)解

4、但不是全局最優(yōu)解，則存在可行解 滿足由可行域?yàn)橥辜?，則 為可行解由 是凸函數(shù)即在 的任意小鄰域內(nèi)存在函數(shù)值小于 的可行解與 是局部極小點(diǎn)矛盾。證畢。13 （4）多元函數(shù)的泰勒公式 多元函數(shù)Taylor展開式在最優(yōu)化理論中十分重要。許多方法及其收斂性的證明都是從它出發(fā)的。下面就給出多元函數(shù)Taylor展開式：的二階泰勒展開例5 用泰勒公式將函數(shù) 在點(diǎn) 解：14給出 極小點(diǎn)的一個(gè)初始估計(jì)值 令設(shè)其中： 為一個(gè)方向向量， 為一個(gè)實(shí)數(shù)（稱為步長） 依次用（1）式計(jì)算得一個(gè)點(diǎn)列若有：則稱（1）為下降迭代算法1） 定義：4 下降迭代算法令15例 6 試求目標(biāo)函數(shù) 在點(diǎn) 處的負(fù)梯度方向，并求沿這個(gè)方向移動一

5、個(gè)單位長度后新點(diǎn)的目標(biāo)函數(shù)值。解： 由于 則函數(shù)在 處的負(fù)梯度方向是這個(gè)方向上的單位向量是：新的點(diǎn)為：16 （2）確定最佳步長 ：在 已知的情況下求 （1）確定搜索方向 ：不同的搜索方向?qū)?yīng)不同的算法定理 ：式（1）中按最佳步長得到的新的點(diǎn) 處的梯度和其搜索方向正交。即證明：得 即為最佳步長17例 7：試求目標(biāo)函數(shù) 在點(diǎn) 處的負(fù)梯度方向，并求沿這個(gè)方向移動最佳步長后新點(diǎn)的目標(biāo)函數(shù)值。解： 由于 則函數(shù)在 處的負(fù)梯度方向是182) 收斂性：若 其中 為極小點(diǎn)。則稱該算法是有效的下降算法得到的點(diǎn)列 不一定收斂到極小點(diǎn)，它依賴于初始點(diǎn)的選擇。例 顯然 為極小點(diǎn) 初始點(diǎn)選不可能收斂于初始點(diǎn)選193 )

6、收斂速度：設(shè) 收斂于 若存在與迭代次數(shù)無關(guān)的數(shù) 和 使得從 開始都有 則稱 為 階收斂。 線性收斂，超線性收斂，二階收斂。20 4) 計(jì)算機(jī)迭代時(shí)終止計(jì)算的準(zhǔn)則（1）絕對誤差（2）相對誤差(3) 根據(jù)目標(biāo)函數(shù)梯度21一維搜索 本節(jié)討論 的主要問題是 解決這個(gè)問題的方法稱為一維搜索。這種方法不僅對于解決一維最優(yōu)化本身具有實(shí)際意義，而且也是解多維最優(yōu)化問題的重要支柱。 在微積分中解 的方法限于方程 可以直接求解出來的情況。本節(jié)介紹的方法對 不作嚴(yán)格要求，它可以很復(fù)雜，其導(dǎo)數(shù)可能不存在或者很難求出。當(dāng)然對于可以求導(dǎo)數(shù)的情況，相應(yīng)的方法也會簡單些。22（1）黃金分割法：適用于一般的函數(shù)。（試探法）（2

7、）二次插值法：（3）Newton切線法：適用于 的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)都可求出的情況。（函數(shù)逼近法）本章將介紹以下幾種直線搜索方法：231 搜索區(qū)間的確定定義1：設(shè) ，t*是 在L 上的全局極小點(diǎn)。如果對于L上任取的兩點(diǎn) 和 且 均有 t* ，當(dāng) t*時(shí)，則稱 是區(qū)間L上的單谷函數(shù)。以下假設(shè)一元函數(shù) 是單谷函數(shù)。 0tt*t*t.24定義2： ，t*是 在L上的全局極小點(diǎn)。若找到 ,則稱此區(qū)間為 的極小點(diǎn)的一個(gè)搜索區(qū)間，。單谷函數(shù)的性質(zhì)： 設(shè) 是單谷函數(shù)極小點(diǎn)的一個(gè)搜索區(qū)間。在 上任取兩點(diǎn) ，使 ,若 則是 極小點(diǎn)的一個(gè)搜索區(qū)間；若 ，則 是 極小點(diǎn)的一個(gè)搜索區(qū)間。.ab25單谷函數(shù)的這一性質(zhì)可

8、用來將搜索區(qū)間無限縮小，以至求到極小點(diǎn)。 本章下面就介紹一維搜索法.證明：利用反證法證明。對于后一種情況，即若 不是搜索區(qū)間即的極小點(diǎn)必在 中。此時(shí)有 ,矛盾。根據(jù)單谷函數(shù)定義知：故 是搜索區(qū)間，同樣可證前種情形2627（負(fù)值舍去）28試探點(diǎn)的公式為：左試點(diǎn)右試點(diǎn)為了算法描述方便我們記試點(diǎn)如下：29步驟：1 給出初始區(qū)間 及精度 ，計(jì)算試探點(diǎn)及函數(shù)值 令k=1 2 若 停止計(jì)算， 中任意一點(diǎn)均可作為所求極小點(diǎn)的近似。否則當(dāng) 時(shí)轉(zhuǎn)3，當(dāng) 時(shí)轉(zhuǎn)4；3 置計(jì)算轉(zhuǎn)5；4 置計(jì)算轉(zhuǎn)5； 5 令 k=k+1返回230例8 用0.618法求解下列問題初始區(qū)間為計(jì)算結(jié)果列于下表：1 -1 1 -0.236 0

9、.236 -0.653 -1.1252 -0.236 1 0.236 0.528 -1.125 -0.970.-1.10.3 -0.236 0.528 0.056 0.236 -1.050 -1.125 4 0.056 0.528 0.236 0.348 -1.125 -1.106 56 0.168 0.348 0.236 0.279 -1.125 -1.123 7 0.168 0.279 0.056 0.348 0.168 0.236 -1.112 -1.125313 二次插值法考慮問題 二次插值法是以目標(biāo)函數(shù)的二次插值函數(shù)的極小點(diǎn)作為新的中間插值點(diǎn)，進(jìn)行一維搜索的方法。 假設(shè)初始區(qū)間函數(shù)值呈現(xiàn)“兩端大中間小”的3個(gè)點(diǎn)所確定的區(qū)間，三個(gè)點(diǎn)為，對應(yīng)的函數(shù)值為。令，過這三個(gè)點(diǎn)，可確定二次插值函數(shù)（1）（2）32（3）將式（2）和式（3）聯(lián)立解得將區(qū)間內(nèi)的3個(gè)點(diǎn)及其函數(shù)值分別代入式(2),得到含三個(gè)未知數(shù)的方程組：（4）3334例93