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

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

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

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

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

試驗(yàn)測得在時(shí)刻時(shí)

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

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

則

又因?yàn)椋?/p>

故Hesse陣為：

第8頁,共38頁，2024年2月25日，星期天

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

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

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

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

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

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

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

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

依次用（1）式計(jì)算得一個(gè)點(diǎn)列若有：則稱（1）為下降迭代算法1）定義：4下降迭代算法令第15頁,共38頁，2024年2月25日，星期天例6

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

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

則稱為階收斂。

線性收斂，超線性收斂，二階收斂。第20頁,共38頁，2024年2月25日，星期天

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

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

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

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

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

,矛盾。根據(jù)單谷函數(shù)定義知：故是搜索區(qū)間，同樣可證前種情形第26頁,共38頁，2024年2月25日，星期天第27頁,共38頁，2024年2月25日，星期天（負(fù)值舍去）第28頁,共38頁，2024年2月25日，星期天試探點(diǎn)的公式為：左試點(diǎn)右試點(diǎn)為了算法描述方便我們記試點(diǎn)如下：第29頁,共38頁，2024年2月25日，星期天步驟：1給出初始區(qū)間及精度，計(jì)算試探點(diǎn)及函數(shù)值令k=12若停止計(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返回2第30頁,共38頁，2024年2月25日，星期天例8用0.618法求解下列問題初始區(qū)間為計(jì)算結(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年2月25日，星期天3二次插值法考慮問題

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

假設(shè)初始區(qū)間函數(shù)值呈現(xiàn)“兩端大中間小”的