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

運(yùn)籌學(xué)

(OperationsResearch)

趙超建筑工程學(xué)院

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

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

)T∈Rn

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

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

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

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

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

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

為有窮點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)是最優(yōu)解；當(dāng){xk}

是無窮點(diǎn)列時(shí)，其極限點(diǎn)是最優(yōu)解(此時(shí)稱該方法是收斂的)。定義3則稱向量p是函數(shù)f(x)在點(diǎn)處的下降方向。定義4則稱向量p是函數(shù)f(x)在點(diǎn)處的可行方向?；镜袷降?步

選取初始點(diǎn),k:=0;第2步

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

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

若x

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

設(shè)是非空凸集，如果對任意的有則稱f是S上的凸函數(shù)，或f在S上是凸的。有則稱f是S上的嚴(yán)格凸函數(shù)，或f在S上是嚴(yán)格凸的。如果對于任意的若–f是S上的（嚴(yán)格）凸函數(shù)，則稱f是S上的（嚴(yán)格）凹函數(shù)或f在S上是（嚴(yán)格）凹的例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è)是非空凸集，是凸函數(shù)，，則集合是凸集。證：水平集又因f是S上的凸函數(shù)，所以凸函數(shù)的性質(zhì)定理3

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

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

充分性.設(shè)定理4

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

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

n,A是一個(gè)n階對稱矩陣，所以當(dāng)且僅當(dāng)A為半正定矩陣時(shí)，f(x)是凸函數(shù)。A為正定矩陣時(shí)，f(x)是嚴(yán)格凸函數(shù)。例二、凸規(guī)劃及其性質(zhì)約束集如果(P)的約束集D是凸集，目標(biāo)函數(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ù)，所以矛盾例：驗(yàn)證下列規(guī)劃為凸規(guī)劃

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

Goldstein法

Armijo法★精確一維搜索方法

0.618法

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

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

(2)

(3)

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

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

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

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

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

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

，求出最小的n。第2步

由前面公式求前兩個(gè)測試點(diǎn)第3步計(jì)算第4步

計(jì)算迭代公式：第5步

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

=0.08四、Newton法基本思想：用在探索點(diǎn)tk處的二階Taylor展開式g(t)近似替代其中用g(t)的最小點(diǎn)作為新的探測點(diǎn)。因此，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án)格局部最優(yōu)解。局部最優(yōu)解，則一、無約束問題的最優(yōu)性條件定理4

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

選取初始點(diǎn)x0,給定終止誤差

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

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

選取初始點(diǎn)x0,給定終止誤差

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

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

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

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