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

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

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

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

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

試驗測得在時刻時

的值為試用其估計參數(shù)。建立問題為的數(shù)學(xué)模型采用最小二乘法問題轉(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求目標(biāo)函數(shù)f（X）=的梯度和Hesse矩陣。解：

則

又因為：

故Hesse陣為：

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

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

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

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

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

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

第10頁,共38頁，星期六，2024年，5月第11頁,共38頁，星期六，2024年，5月凸規(guī)劃若為凸函數(shù)為凹函數(shù)，則該非線性規(guī)劃為凸規(guī)劃。定義：第12頁,共38頁，星期六，2024年，5月凸規(guī)劃性質(zhì)：設(shè)是凸規(guī)劃問題的一個局部最優(yōu)解，則是全局最優(yōu)解。如果是嚴(yán)格凸函數(shù)，則是唯一全局最優(yōu)解。證明：反證法設(shè)是凸規(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è)其中：為一個方向向量，為一個實數(shù)（稱為步長）

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

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

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

則稱為階收斂。

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

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

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

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

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

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

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

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

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

5令k=k+1返回2第30頁,共38頁，星期六，2024年，5月例8用0.618法求解下列問題初始區(qū)間為計算結(jié)果列于下表：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二次插值法考慮問題

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

假設(shè)初始區(qū)間函