第六章非線性規(guī)劃

運籌學

(OperationsResearch)

趙超建筑工程學院

2013年1月Chapter6非線性規(guī)劃基本概念凸函數(shù)和凸規(guī)劃一維搜索方法無約束最優(yōu)化方法約束最優(yōu)化方法本章主要內(nèi)容：第一節(jié)基本概念非線性規(guī)劃問題非線性規(guī)劃方法概述一、非線性規(guī)劃問題引例例1

曲線的最優(yōu)擬合問題例2構(gòu)件容積問題設計一個右圖所示的由圓錐和圓柱面圍成的構(gòu)件，要求構(gòu)件的表面積為S，圓錐部分的高h和圓柱部分的高x2之比為a。確定構(gòu)件尺寸，使其容積最大。h二、數(shù)學模型約束集或可行域其中x=(x1,x2,...,xn

)T∈Rn

，D中的點稱為可行解或可行點三、分類（1）線性規(guī)劃：目標函數(shù)和約束條件皆為x的線性函數(shù)。（2）非線性規(guī)劃：目標函數(shù)和約束條件中至少有一個是x的非線性函數(shù)。本章討論非線性規(guī)劃。（1）當p=0,q=0,即可行域D=Rn

時，(P)可寫成稱為無約束非線性規(guī)劃或無約束最優(yōu)化問題。（2）若可行域D≠Rn

，(P)稱為約束非線性規(guī)劃或約束最優(yōu)化問題。定義1

對于非線性規(guī)劃(P)，若并且存在x*的一個鄰域則x*稱為局部最優(yōu)解或局部極小點，稱f(x*)為局部最優(yōu)值或局部極小值。則稱x*為嚴格局部最優(yōu)解或嚴格局部極小點,稱f(x*)為嚴格局部最優(yōu)值或嚴格局部極小值。

若使得使得四、最優(yōu)解和最優(yōu)值四、最優(yōu)解和最優(yōu)值全局最優(yōu)解為x*=(1/2,1/2)T,全局最優(yōu)值為f(x*)=1/2。1

x1x21x*若目標函數(shù)改為：其最優(yōu)解和最優(yōu)值如何？五、非線性規(guī)劃方法概述迭代法:按某種方法給出目標函數(shù)極小點的一個初始估計，稱為初始點。然后按某種特定的迭代規(guī)則產(chǎn)生一點列{xk}，使得{xk}

為有窮點列時，其最后一個點是最優(yōu)解；當{xk}

是無窮點列時，其極限點是最優(yōu)解(此時稱該方法是收斂的)。定義3則稱向量p是函數(shù)f(x)在點處的下降方向。定義4則稱向量p是函數(shù)f(x)在點處的可行方向。基本迭代格式第1步

選取初始點,k:=0;第2步

構(gòu)造搜索方向第3步

根據(jù)，確定步長第4步

若x

k+1已滿足某種終止條件，停止迭代，輸出近似解.否則令k:=k+1，轉(zhuǎn)回第2步。隨機性方法是按照某種規(guī)則隨機產(chǎn)生迭代點,迭代點列依概率收斂到最優(yōu)解，包括遺傳算法,模擬退火算法,神經(jīng)網(wǎng)絡算法等,這類方法具有對函數(shù)性質(zhì)要求低、容易實現(xiàn)等優(yōu)點,但效率低、可靠性差、不能保證產(chǎn)生優(yōu)化問題的最優(yōu)解.全局優(yōu)化算法概述全局優(yōu)化方法可分為隨機性方法和確定性方法.全局優(yōu)化算法概述確定性方法充分利用了問題的解析性質(zhì),如函數(shù)的凸性、單調(diào)性、稠密性等,產(chǎn)生一個確定性的有限或無限點序列,使得該點序列收斂于全局最優(yōu)解.包括分枝定界算法、區(qū)間算法、填充函數(shù)法、割平面法、頂點枚舉法等,這類算法在理論上有較強的可行性,但對較為復雜的大型優(yōu)化問題卻難于應用.全局優(yōu)化方法可分為隨機性方法和確定性方法.第二節(jié)凸函數(shù)和凸規(guī)劃凸函數(shù)及其性質(zhì)凸規(guī)劃及其性質(zhì)一、凸函數(shù)及其性質(zhì)定義5

設是非空凸集，如果對任意的有則稱f是S上的凸函數(shù)，或f在S上是凸的。有則稱f是S上的嚴格凸函數(shù)，或f在S上是嚴格凸的。如果對于任意的若–f是S上的（嚴格）凸函數(shù)，則稱f是S上的（嚴格）凹函數(shù)或f在S上是（嚴格）凹的例1線性函數(shù)在Rn上既是凸函數(shù)又是凹函數(shù)。例2函數(shù)證證證:(1)定理1(1)若f(x)是S上的凸函數(shù)，都是S上的凸函數(shù),是S上的凸函數(shù)。

是非空凸集。(2)則也是S上的凸函數(shù)。

凸函數(shù)的性質(zhì)定理1(1)若f(x)是S上的凸函數(shù)，是S上的凸函數(shù)。

是非空凸集。凸函數(shù)的性質(zhì)都是S上的凸函數(shù),(2)則也是S上的凸函數(shù)。

證:(2)定理2

設是非空凸集，是凸函數(shù)，，則集合是凸集。證：水平集又因f是S上的凸函數(shù)，所以凸函數(shù)的性質(zhì)定理3

設是非空開凸集，是函數(shù)f在點處的梯度（1）f是S上的凸函數(shù)的充要條件是（2）f是S上的嚴格凸函數(shù)的充要條件是可微，則凸函數(shù)的判定證

(1)必要性.設f是S上的凸函數(shù)，則對代入得由泰勒公式得證（1）（2）對和

充分性.設定理4

設是非空開凸集，則f是S上的凸函數(shù)的充要條件是f

的Hesse矩陣在S上是半正定的.注意：該逆命題不成立。f在S上二階連續(xù)可導,在S上正定時，f是S上的嚴格凸函數(shù).凸函數(shù)的判定二次型二次型函數(shù)其中x∈R

n,A是一個n階對稱矩陣，所以當且僅當A為半正定矩陣時，f(x)是凸函數(shù)。A為正定矩陣時，f(x)是嚴格凸函數(shù)。例二、凸規(guī)劃及其性質(zhì)約束集如果(P)的約束集D是凸集，目標函數(shù)f是D上的凸函數(shù)，則(P)叫做非線性凸規(guī)劃，或簡稱為凸規(guī)劃。非線性規(guī)劃定理5

對于非線性規(guī)劃(P)，若并且f是D上的凸函數(shù)，則(P)是凸規(guī)劃。皆為Rn上的凸函數(shù)，皆為線性函數(shù)證：又因f

是D上的凸函數(shù)，(P)是凸規(guī)劃定理6

凸規(guī)劃的任一局部最優(yōu)解都是它的全局最優(yōu)解。證：又因f是凸函數(shù)，所以矛盾例：驗證下列規(guī)劃為凸規(guī)劃

第三節(jié)一維搜索方法★非精確一維搜索方法

Goldstein法

Armijo法★精確一維搜索方法

0.618法

Newton法目標函數(shù)為單變量的非線性規(guī)劃問題稱為一維搜索問題數(shù)學模型由定義知，t*是在[a,b]上的唯一極小點。一、基本原理定義1如果存在一個，使得在區(qū)間上嚴格遞減，且在區(qū)間上嚴格遞增，則稱函數(shù)在區(qū)間[a,b]上是單谷的，區(qū)間[a,b]

稱為的單谷區(qū)間。使得，稱[a,b]為搜索區(qū)間。不斷縮短搜索區(qū)間的長度，當區(qū)間足夠小時,得到所求問題的近似最優(yōu)解。在區(qū)間[a,b]上任取兩點t1,t2，設t1<t2，然后，讓下一次迭代中區(qū)間縮短相同的比例ω，并且已有一個計算過的點在縮短后的區(qū)間內(nèi)。二、0.618法（近似黃金分割法）abt1t2設新的探索區(qū)間為[a,t2],其上的兩個探索點為0.618法（近似黃金分割法）由以上分析得迭代公式：0.618法（近似黃金分割法）算法步驟：例1：試用黃金分割法求解解(1)

(2)

(3)

(4)得最優(yōu)解：三、斐波那契（Fibonacci）法定義2

設數(shù)列{Fn}滿足：數(shù)列{Fk

}稱為斐波那契（Fibonacci）數(shù)列

。k012345678Fk112358132134一、斐波那契（Fibonacci）法計算n次函數(shù)值所得最大縮短率為1/Fn要把區(qū)間縮短為原區(qū)間的δ(δ<

1)倍或更小，只要n足夠大時，(1)ab算法步驟：第1步

確定試點的個數(shù)n.根據(jù)縮短率δ，計算Fn

，求出最小的n。第2步

由前面公式求前兩個測試點第3步計算第4步

計算迭代公式：第5步

當k=n-1時，算法步驟：二、0.618法與Fibonacci法的關(guān)系同理可證，事實上，設由上兩式得在斐波那契法中，0.618法（近似黃金分割法）斐波那契（Fibonacci）法例：試用斐波那契法求函數(shù)要求縮短率為δ

=0.08四、Newton法基本思想：用在探索點tk處的二階Taylor展開式g(t)近似替代其中用g(t)的最小點作為新的探測點。因此，Newton法第1步第2步轉(zhuǎn)第3步；第3步例：用Newton法求函數(shù)的最優(yōu)解解ktk110.785422-0.5708-0.51781.325830.11690.11631.01374-0.001061Newton法Goldstein法Goldstein法步驟Armijo法第四節(jié)無約束最優(yōu)化方法無約束問題的最優(yōu)性條件最速下降法共軛方向法一、無約束問題的最優(yōu)性條件定理1

證

由Taylor展式，對任意t>0，有定理2

若x*是(UP)的定理3

則x*是(UP)的嚴格局部最優(yōu)解。局部最優(yōu)解，則一、無約束問題的最優(yōu)性條件定理4

則x*是(UP)的全局最優(yōu)解。x*是(UP)的全局最優(yōu)解。一、無約束問題的最優(yōu)性條件例1解目標函數(shù)的Hesse矩陣為一、無約束問題的最優(yōu)性條件一、無約束問題的最優(yōu)性條件二、最速下降法基本思想：從當前點xk出發(fā)，取函數(shù)f(x)在點xk處下降最快的方向為搜索方向pk，即負梯度方向。設目標函數(shù)f(x)一階連續(xù)可微.二、最速下降法算法步驟：第1步

選取初始點x0,給定終止誤差

ε>0,令k:=0；第2步計算第4步進行一維搜索，求tk使得第3步用最速下降法求得最優(yōu)解是目標函數(shù)的一個駐點。例2用最速下降法求解解：經(jīng)10輪迭代得最優(yōu)解。三、共軛方向法定義設A是n階實對稱矩陣，若則稱p和q是相互A共軛的。對于非零向量組則稱p0,p1,...,pn-1是A共軛方向組，或稱一組A共軛方向。共軛概念是正交概念的推廣。證線性無關(guān)共軛方向組中最多含n個向量，且線性無關(guān)反之，n維空間的一組基可以構(gòu)造一組A共軛方向共軛方向組的構(gòu)造由定理知：二次嚴格凸函數(shù)的無約束最優(yōu)化問題定理6

對于問題(QP)，若組A共軛方向，則由任意初始點出發(fā)，依次沿則最多經(jīng)n次迭代可得(QP)的整體最優(yōu)解。為任意一進行精確一維搜索，由任意初始點出發(fā)，依此沿某共軛方向組進行一維搜索求解無約束優(yōu)化的方法叫共軛方向法。利用迭代點處的負梯度向量為基礎產(chǎn)生一組共軛方向，這種方法叫共軛梯度法。共軛梯度法（1）公式（1）是由Fletcher和Reeves于1964年提出的，稱為F-R公式，用公式（1）求解無約束最優(yōu)化問題最優(yōu)解的方法簡稱為F-R法。第1步

選取初始點x0,給定終止誤差

ε>0；第2步計算第4步進行一維搜索，求tk使得第3步F-R法步驟第5步計算第6步第7步用F-R公式取例2用F-R法求解解：利用F-R公式得：若用某種方法求解(QP)問題，經(jīng)有限輪迭代可以達到最優(yōu)解，稱此方法具有二次終止性。F-R法具有二次終止性。第五節(jié)約束最優(yōu)化方法約束最優(yōu)化問題的最優(yōu)化條件簡約梯度法懲罰函數(shù)法一、約束最優(yōu)化問題的最優(yōu)化條件定理1

處可微，在點x*處連續(xù)，在點x*劃(P)的局部最優(yōu)解，則存在兩組實數(shù)若x*是非線性規(guī)稱約束規(guī)范條件Kuhn-Tucker條件，簡稱K-T條件特殊地，對于只有不等式約束的非線性規(guī)劃問題若x*是局部最優(yōu)解，則存在實數(shù)對于只有等式約束的非線性規(guī)劃問題一、約束最優(yōu)化問題的最優(yōu)化條件現(xiàn)引進Lagrange函數(shù)如下：一、約束最優(yōu)化問題的最優(yōu)化條件K-T條件為：定理2

對于問題(P)，若在點x*處連續(xù)可微，若可行點x*滿足(P)的K-T條件，且是凸函數(shù),是線性函數(shù)，則x*是(P)的全局最優(yōu)解。一、約束最優(yōu)化問題的最優(yōu)化條件例用K-T條件解非線性規(guī)劃二、簡約梯度法假設（1）每個可行點至少有m個大于0的分量（2）A的任意m列線性無關(guān)簡約梯度法的基本思想是Wolfe于1962年提出二、簡約梯度法基本思想：類似于單純形法，將當前點xk的m個最大正分量定為基變量，其余的m-n個分量作為非基變量，那么目標函數(shù)作為非基變量的函數(shù)求負梯度方向，并依據(jù)這一方向構(gòu)造從xk到xk+1的可行下降方向。二、簡約梯度法稱rN為f在點x處對應于基矩陣B的簡約梯度。首先，求f對非基變量的梯度二、簡約梯度法其次，在迭代點xk處依據(jù)簡約梯度構(gòu)造可行下降方向取，則是下降方向，但不一定是可行方向。二、簡約梯度法這是因為，二、簡約梯度法綜上所述，利用簡約梯度（*）定理3設f是可微函數(shù)，，二、簡約梯度法二、簡約梯度法最后，考察如何從點xk

∈Dl沿上面構(gòu)造的可行下降方向pk進行有效一維搜索。因而取t的上界為為使Wolfe法步驟Wolfe法步驟例用Wolfe法求解極小化問題解上面問題可化為下列問題二、懲罰函數(shù)法罰函數(shù)法障礙函數(shù)法基本思想：利用問題中的約束函數(shù)做出適當?shù)膸в?/p>