非線性規(guī)劃基礎(chǔ)

非線性規(guī)劃基礎(chǔ)第一頁，共三十六頁，編輯于2023年，星期二第一節(jié)非線性規(guī)劃的基本概念一、非線性規(guī)劃模型二、非線性規(guī)劃的幾何求解第二頁，共三十六頁，編輯于2023年，星期二一、

非線性規(guī)劃模型非線性規(guī)劃的一般形式：

稱為決策變量稱為不等式約束稱為等式約束可行域稱為目標(biāo)函數(shù)第三頁，共三十六頁，編輯于2023年，星期二1、局部解局部極大值局部極小值2、全局解全局最大值全局最小值局部最優(yōu)解≠全局最優(yōu)解

線性規(guī)劃問題的最優(yōu)解在角點(diǎn)取到，對非線性規(guī)劃問題，最優(yōu)解在何處取到呢？第四頁，共三十六頁，編輯于2023年，星期二二、非線性規(guī)劃的幾何求解例13.1求解下列非線性規(guī)劃的最優(yōu)解。作圖求解第五頁，共三十六頁，編輯于2023年，星期二例13.2求解下列非線性規(guī)劃的最優(yōu)解。作圖求解第六頁，共三十六頁，編輯于2023年，星期二例13.3求解下列非線性規(guī)劃的最優(yōu)解。作圖求解第七頁，共三十六頁，編輯于2023年，星期二線性規(guī)劃與非線性規(guī)劃有很大的區(qū)別：如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在可行域的邊界達(dá)到。而非線性規(guī)劃的最優(yōu)解（如果最優(yōu)解存在）則可能在可行域的任何一點(diǎn)達(dá)到。

第八頁，共三十六頁，編輯于2023年，星期二第二節(jié)凸函數(shù)

一、凸函數(shù)的基本概念二、凸函數(shù)的判斷三、凸規(guī)劃第九頁，共三十六頁，編輯于2023年，星期二凸函數(shù)定義凹函數(shù)定義一、凸函數(shù)的基本概念凸函數(shù)凹函數(shù)非凸非凹函數(shù)第十頁，共三十六頁，編輯于2023年，星期二凸函數(shù)具有如下性質(zhì)

第十一頁，共三十六頁，編輯于2023年，星期二二、凸函數(shù)的判斷一元函數(shù)凸性的判斷第十二頁，共三十六頁，編輯于2023年，星期二多元函數(shù)凸性的判斷梯度：

Hessian矩陣：第十三頁，共三十六頁，編輯于2023年，星期二f(x)=x13+3x1x2+x22，則f(x)的Hessian矩陣為：判定正定的方法：當(dāng)一個n×n矩陣A的任意k階順序主子式大于0時，則該矩陣為正定的。

第十四頁，共三十六頁，編輯于2023年，星期二D為凸集合，f(x)是定義在上的二次可微函數(shù)，則f(x)為凸函數(shù)的充要條件為f(x)在任意一點(diǎn)的Hessian矩陣為半正定。則f(x)為凸函數(shù)的充要條件為：第十五頁，共三十六頁，編輯于2023年，星期二例13.4判別下列函數(shù)的凸凹性

解：1）1）2）H(x1,x2)的兩個順序主子式分別H1(x1,x2)=4和H2(x1,x2)=8-4=4均大于0。所以f(x)為凸函數(shù)。2）H(x1,x2)的兩個順序主子式分別H1(x1,x2)=2>0和H2(x1,x2)=-4<0。所以f(x)不是凸函數(shù)。

第十六頁，共三十六頁，編輯于2023年，星期二三、凸規(guī)劃當(dāng)f(x),g(x)為凸函數(shù)，h(x)=(h1(x),…,hl(x))是線性函數(shù)時，上述規(guī)劃問題稱為凸規(guī)劃問題。凸規(guī)劃的求解可借助下節(jié)的KKT定理。

h(x)=(h1(x),…,hl(x))=0第十七頁，共三十六頁，編輯于2023年，星期二第三節(jié)最優(yōu)性條件一、無約束優(yōu)化的最優(yōu)性條件二、約束極值問題的最優(yōu)性條件第十八頁，共三十六頁，編輯于2023年，星期二引入兩個概念

下降方向：

可行方向：則稱d為f(x)在點(diǎn)的下降方向。

則稱d為D在點(diǎn)的可行方向。

定理13.6若f(x)在點(diǎn)可微，如果存在方向d，使，則使有第十九頁，共三十六頁，編輯于2023年，星期二一、無約束優(yōu)化的最優(yōu)性條件在無約束規(guī)劃問題中，由于不涉及到可行域的問題，因此，只涉及下降方向。不涉及可行方向的問題。第二十頁，共三十六頁，編輯于2023年，星期二定理13.7（一階必要條件）

若f(x)在點(diǎn)可微，且為無約束優(yōu)化問題（13.4）的局部最優(yōu)解，則。定理13.8（二階必要條件）若f(x)在點(diǎn)二階連續(xù)可微，且點(diǎn)為無約束優(yōu)化問題（13.4）的局部最優(yōu)解。則且半正定。定理13.9（二階充分條件）設(shè)滿足且正定，則點(diǎn)為無約束優(yōu)化問題（13.4）的局部最優(yōu)解。定理13.10

若目標(biāo)函數(shù)f(x)是Rn上的連續(xù)可微凸函數(shù)，則的充分必要條件為無約束優(yōu)化問題（13.4）的全局最優(yōu)點(diǎn)和局部最優(yōu)點(diǎn)。第二十一頁，共三十六頁，編輯于2023年，星期二例13.5求函數(shù)f(x)的最優(yōu)值點(diǎn)，即。正定解：所以為局部最小值點(diǎn)。

第二十二頁，共三十六頁，編輯于2023年，星期二二、約束極值問題的最優(yōu)性條件

在x點(diǎn)取到局部最優(yōu)值的條件為：

無解約束規(guī)劃問題不僅涉及到目標(biāo)函數(shù)，還涉及到可行域。因此既要考慮下降方向，還要考慮可行方向第二十三頁，共三十六頁，編輯于2023年，星期二定理13.11（Gorden）：設(shè)，則Ax<0有解的充分必要條件為：不存在非零向量，使得。

無解的充分必要條件為：存在不全為零的非負(fù)實(shí)數(shù)使上述定理的幾何意義為：

dA1A2A3A3A1A2Ad<0有解

Ad<0無解

第二十四頁，共三十六頁，編輯于2023年，星期二定理（Fritz-John）：問題（13.5）在點(diǎn)取到局部極小值，則存在不全為零的非負(fù)實(shí)數(shù)使例13.6：是下列優(yōu)化問題的最優(yōu)解，驗(yàn)證x滿足Fritz-John定理。第二十五頁，共三十六頁，編輯于2023年，星期二緊指標(biāo)集I={1,2}

如(w0,w1,w2)=(1,1,2)。

因此，x滿足Fritz-John定理。第二十六頁，共三十六頁，編輯于2023年，星期二例13.7(0,2)T是下列優(yōu)化問題的最優(yōu)解，驗(yàn)證x滿足Fritz-John定理(w0,w1,w2)=(0,k,2k)，w0=0

因此，x滿足Fritz-John定理。

第二十七頁，共三十六頁，編輯于2023年，星期二

約束規(guī)格：線性無關(guān)定理（KKT）：設(shè)是問題（13.5）局部最優(yōu)解，在處可微，在處連續(xù)，且線性無關(guān)，則存在不全為零的非負(fù)實(shí)數(shù)使第二十八頁，共三十六頁，編輯于2023年，星期二例13.8求下列問題的KKT點(diǎn)。KKT點(diǎn)：第二十九頁，共三十六頁，編輯于2023年，星期二定理13.14.在問題（13.5）中，f,gi(i=1,…,m)是凸函數(shù)，，，在處可微，在處連續(xù)，且在處KKT條件成立，則是問題（13.5）全局最優(yōu)解。第三十頁，共三十六頁，編輯于2023年，星期二

第四節(jié)非線性規(guī)劃問題的算法一、一維搜索法二、最速下降法第三十一頁，共三十六頁，編輯于2023年，星期二minf(x)f:RnR是一階連續(xù)函數(shù)無約束優(yōu)化問題的極值條件基本迭代格式尋找搜索方向是無約束優(yōu)化的關(guān)鍵問題第三十二頁，共三十六頁，編輯于2023年，星期二一、一維搜索法一維搜索法是求解無約束優(yōu)化的一種方法。它是沿射線xk+1=xk+tdk，求f(x)在該射線上的極小值，這一問題可轉(zhuǎn)化為求一元函數(shù)的極小值，即因此，這一過程稱為一維搜索法。第三十三頁，共三十六頁，編輯于2023年，星期二通常，無約束優(yōu)化問題算法的一般形式為：初始步：給定初始點(diǎn)，令k=0。第1步：如果，停止計(jì)算；否則，進(jìn)入下一步。第2步：計(jì)算下降方向dk，使。第3步：計(jì)算步長tk，使得，令；k=k+1，轉(zhuǎn)第1步。第三十四頁，共三十六頁，編輯于2023年，星期二一維搜索的方法很多，歸納起來，可分為試探法和函數(shù)逼近法。試探法中包括如黃金分割法、Fibonacci法等；函數(shù)逼近法中包括如牛頓法、割線法等。第三十五頁，共三十六頁，編輯