規(guī)劃數(shù)學非線性規(guī)劃基本知識

關于規(guī)劃數(shù)學非線性規(guī)劃基本知識非線性規(guī)劃基本概念（3.1）1非線性規(guī)劃模型分類

一般無約束極值形式為：一般有約束極值問題形式為：第2頁,共38頁，星期六，2024年，5月例1在層次分析（AnalyticHierarchyProcess,簡記為AHP）中，為了進行多屬性的綜合評價，需要確定每個屬性的相對重要性，即它們各自的權重。為此，將各屬性進行兩兩比較可得如下判斷矩陣：

其中：是第個屬性與第個屬性的重要性之比?，F(xiàn)需要從判斷矩陣求出各屬性的權重，為使求出的權重向量在最小二乘意義上能最好地反映判斷矩陣的估計，建立數(shù)學模型：有約束極值問題第3頁,共38頁，星期六，2024年，5月例2模型參數(shù)識別問題

設已知某問題的數(shù)學模型為

試驗測得在時刻時

的值為試用其估計參數(shù)。建立問題為的數(shù)學模型采用最小二乘法問題轉(zhuǎn)化為求解無約束極值問題第4頁,共38頁，星期六，2024年，5月2多元函數(shù)的極值問題（1）梯度及Hesse矩陣梯度Hesse矩陣第5頁,共38頁，星期六，2024年，5月

例3：求下列函數(shù)的梯度：①解：第6頁,共38頁，星期六，2024年，5月②解：第7頁,共38頁，星期六，2024年，5月例4求目標函數(shù)f（X）=的梯度和Hesse矩陣。解：

則

又因為：

故Hesse陣為：

第8頁,共38頁，星期六，2024年，5月

（2）局部極值和全局極值極小點局部極小點全局極小點嚴格局部極小點非嚴格局部極小點非嚴格全局極小點嚴格全局極小點例如：圖中一元函數(shù)f定義在區(qū)間[ab]上為嚴格局部極小點，非嚴格局部極小點a為嚴格全局極小點第9頁,共38頁，星期六，2024年，5月凸（凹）函數(shù)定義:

設函數(shù)在凸集上有定義,如果對任意和屬于及任何實數(shù)

（）則稱是上的凸函數(shù).

（3）凸函數(shù)、凹函數(shù)及凸規(guī)劃凸（凹）函數(shù)二階判別定理：

設是非空開凸集上的二階連續(xù)可微函數(shù)，則為凸函數(shù)的充分必要條件是在上半正（負）定。

第10頁,共38頁，星期六，2024年，5月第11頁,共38頁，星期六，2024年，5月凸規(guī)劃若為凸函數(shù)為凹函數(shù)，則該非線性規(guī)劃為凸規(guī)劃。定義：第12頁,共38頁，星期六，2024年，5月凸規(guī)劃性質(zhì)：設是凸規(guī)劃問題的一個局部最優(yōu)解，則是全局最優(yōu)解。如果是嚴格凸函數(shù)，則是唯一全局最優(yōu)解。證明：反證法設是凸規(guī)劃的局部最優(yōu)解但不是全局最優(yōu)解，則存在可行解滿足由可行域為凸集，則為可行解由是凸函數(shù)即在的任意小鄰域內(nèi)存在函數(shù)值小于的可行解與是局部極小點矛盾。證畢。第13頁,共38頁，星期六，2024年，5月

（4）多元函數(shù)的泰勒公式

多元函數(shù)Taylor展開式在最優(yōu)化理論中十分重要。許多方法及其收斂性的證明都是從它出發(fā)的。下面就給出多元函數(shù)Taylor展開式：的二階泰勒展開例5用泰勒公式將函數(shù)在點解：第14頁,共38頁，星期六，2024年，5月給出極小點的一個初始估計值令設其中：為一個方向向量，為一個實數(shù)（稱為步長）

依次用（1）式計算得一個點列若有：則稱（1）為下降迭代算法1）定義：4下降迭代算法令第15頁,共38頁，星期六，2024年，5月例6

試求目標函數(shù)在點處的負梯度方向，并求沿這個方向移動一個單位長度后新點的目標函數(shù)值。解：由于則函數(shù)在處的負梯度方向是這個方向上的單位向量是：新的點為：第16頁,共38頁，星期六，2024年，5月

（2）確定最佳步長：在已知的情況下求（1）確定搜索方向：不同的搜索方向?qū)煌乃惴ǘɡ恚菏剑?）中按最佳步長得到的新的點處的梯度和其搜索方向正交。即證明：得即為最佳步長第17頁,共38頁，星期六，2024年，5月例7：試求目標函數(shù)在點處的負梯度方向，并求沿這個方向移動最佳步長后新點的目標函數(shù)值。解：由于則函數(shù)在處的負梯度方向是第18頁,共38頁，星期六，2024年，5月2)收斂性：若其中為極小點。則稱該算法是有效的下降算法得到的點列不一定收斂到極小點，它依賴于初始點的選擇。例顯然為極小點初始點選不可能收斂于初始點選第19頁,共38頁，星期六，2024年，5月3)收斂速度：設收斂于若存在與迭代次數(shù)無關的數(shù)和使得從開始都有

則稱為階收斂。

線性收斂，超線性收斂，二階收斂。第20頁,共38頁，星期六，2024年，5月

4)計算機迭代時終止計算的準則（1）絕對誤差（2）相對誤差(3)根據(jù)目標函數(shù)梯度第21頁,共38頁，星期六，2024年，5月一維搜索

本節(jié)討論的主要問題是

解決這個問題的方法稱為一維搜索。這種方法不僅對于解決一維最優(yōu)化本身具有實際意義，而且也是解多維最優(yōu)化問題的重要支柱。在微積分中解的方法限于方程可以直接求解出來的情況。本節(jié)介紹的方法對不作嚴格要求，它可以很復雜，其導數(shù)可能不存在或者很難求出。當然對于可以求導數(shù)的情況，相應的方法也會簡單些。第22頁,共38頁，星期六，2024年，5月

（1）黃金分割法：適用于一般的函數(shù)。（試探法）（2）二次插值法：（3）Newton切線法：適用于的一階導數(shù)和二階導數(shù)都可求出的情況。（函數(shù)逼近法）本章將介紹以下幾種直線搜索方法：第23頁,共38頁，星期六，2024年，5月1搜索區(qū)間的確定

定義1：設，t*是在L上的全局極小點。如果對于L上任取的兩點和且<均有≤t*，當≥t*時，則稱是區(qū)間L上的單谷函數(shù)。以下假設一元函數(shù)是單谷函數(shù)。

0tt*t*t..第24頁,共38頁，星期六，2024年，5月定義2：，t*是在L上的全局極小點。若找到,則稱此區(qū)間為的極小點的一個搜索區(qū)間，。單谷函數(shù)的性質(zhì)：設是單谷函數(shù)極小點的一個搜索區(qū)間。在上任取兩點，使,若則是極小點的一個搜索區(qū)間；若，則是極小點的一個搜索區(qū)間。....ab第25頁,共38頁，星期六，2024年，5月

單谷函數(shù)的這一性質(zhì)可用來將搜索區(qū)間無限縮小，以至求到極小點。本章下面就介紹一維搜索法.證明：利用反證法證明。對于后一種情況，即若不是搜索區(qū)間即的極小點必在中。此時有

,矛盾。根據(jù)單谷函數(shù)定義知：故是搜索區(qū)間，同樣可證前種情形第26頁,共38頁，星期六，2024年，5月第27頁,共38頁，星期六，2024年，5月（負值舍去）第28頁,共38頁，星期六，2024年，5月試探點的公式為：左試點右試點為了算法描述方便我們記試點如下：第29頁,共38頁，星期六，2024年，5月步驟：1給出初始區(qū)間及精度，計算試探點及函數(shù)值令k=12若停止計算，中任意一點均可作為所求極小點的近似。否則當時轉(zhuǎn)3，當時轉(zhuǎn)4；3置計算轉(zhuǎn)5；4置計算轉(zhuǎn)5；

5令k=k+1返回2第30頁,共38頁，星期六，2024年，5月例8用0.618法求解下列問題初始區(qū)間為計算結果列于下表：1-11-0.2360.236

-0.653-1.1252-0.2361

0.2360.528-1.125-0.970.-1.10....3-0.236

0.528

0.056

0.236-1.050

-1.125

40.0560.5280.2360.348-1.125-1.106

560.1680.3480.2360.279-1.125-1.12370.1680.2790.0560.3480.1680.236-1.112-1.125第31頁,共38頁，星期六，2024年，5月3二次插值法考慮問題

二次插值法是以目標函數(shù)的二次插值函數(shù)的極小點作為新的中間插值點，進行一維搜索的方法。

假設初始區(qū)間函