管理運(yùn)籌學(xué) 課件 11有約束非線性規(guī)劃

1OperationalResearch

運(yùn)籌學(xué)哈爾濱理工大學(xué)管理學(xué)院SchoolofManagement

HarbinUniversityofScienceandTechnology田世海教授2Chapter11第11章ConstrainedOptimization約束極值問題OperationalResearchNonlinearProgramming非線性規(guī)劃3ConstrainedOptimization約束極值及最優(yōu)性條件不等式約束一般約束問題主要內(nèi)容等式約束約束極值問題的算法內(nèi)點(diǎn)法乘子法外點(diǎn)法41、約束極值問題的表示一、約束極值問題的最優(yōu)性條件562約束極值及最優(yōu)性條件——Kuhn-Tucker條件（1）等式約束性問題的最優(yōu)性條件

考慮minf(x)s.t.h(x)=0

回顧高等數(shù)學(xué)中所學(xué)的條件極值：

問題求z=f(x,y)極值，在ф(x,y)=0的條件下。即：minf(x,y)s.t.ф(x,y)=0

引入Lagrange乘子：λ

Lagrange函數(shù)L(x,y;λ)=f(x,y)+λф(x,y)7若x*是其的最優(yōu)解,則存在υ*∈Rl

使8

幾何意義：考慮一個(gè)約束的情況：x'

最優(yōu)性條件即：9(2)不等式約束極值問題的最優(yōu)性條件可行方向:①可行方向與積極約束:10積極約束:例:或起作用約束（緊約束\積極約束\有效約束）。11②如何判斷一個(gè)方向是可行方向?12證明:定理1:可行下降方向:13定理2:定理3:證略③極值點(diǎn)的必要條件:1415161718定理4(K-T條件):192021222324252627282930313233作業(yè):

求約束極值問題34353637（一）懲罰函數(shù)法（SUMT）二、約束極值問題的算法

將有約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題進(jìn)行求解。（SequentialUnconstrainedMinimizationTechnique-SUMT）1、算法思想：2、算法類型：

外點(diǎn)法（外懲法）內(nèi)點(diǎn)法（內(nèi)懲法）383、問題：394、外點(diǎn)法（外部懲罰函數(shù)法）40414243（1）幾何解釋44（2）算法步驟（外點(diǎn)法）：45yesNo（3）外點(diǎn)法框圖46（4）應(yīng)注意的問題47例:

484950

（5）一般模型的外點(diǎn)法

算法步驟相同51例:

525354555、內(nèi)點(diǎn)法（閘函數(shù)法、障礙函數(shù)法）（1）集合結(jié)構(gòu)56（2）算法思想

內(nèi)點(diǎn)法（障礙函數(shù)法）的迭代點(diǎn)是在可行域點(diǎn)集內(nèi)部移動(dòng)的，對接近可行域邊界上的點(diǎn)施加越來越大的懲罰，對可行域邊界上的點(diǎn)施加無限大的懲罰，這好比邊界是一道障礙物，阻礙迭代點(diǎn)穿越邊界。

內(nèi)點(diǎn)法要求可行點(diǎn)集的內(nèi)點(diǎn)集合非空，否則算法無法運(yùn)行。這樣一來內(nèi)點(diǎn)法只對不等式約束的優(yōu)化問題才可能有效。57（3）算法分析5859（4）算法步驟（內(nèi)點(diǎn)法）：60內(nèi)點(diǎn)法框圖yesNo61例解6263例解6465例解66（5）罰函數(shù)法的缺點(diǎn)67(6)內(nèi)、外點(diǎn)法的優(yōu)缺點(diǎn)的比較1.x(0)∈S02.等式約束不適用3.障礙函數(shù)B(x)在S0的可微階數(shù)與gi(x)相同(可選用的無約束最優(yōu)化方法廣)4.迭代中x（k）∈R

（隨時(shí)可取x（k）≈x*）5.非凸規(guī)劃適用1.任意x(0)∈Rn2.等式約束適用3.懲罰項(xiàng)的二階偏導(dǎo)在S的邊界上不存在4.5.非凸規(guī)劃適用內(nèi)點(diǎn)法外點(diǎn)法迭代中x（k）R?686.乘子法乘子罰函數(shù):乘子罰函數(shù)與Langrange函數(shù)及懲罰函數(shù)的區(qū)別：多一項(xiàng)。

(1)等式約束69乘子罰函數(shù):70(2)等式、不等式約束71算法步驟（乘子罰函數(shù)法）：72解：1.懲罰函數(shù)法。對于懲罰函數(shù)例：問題的最優(yōu)解為x*=(0.25,0.75),分別用懲罰函數(shù)法和乘子法求它的迭代點(diǎn)列。

可求得最優(yōu)解為：

2.乘子法。對于乘子罰函數(shù)73可求得最優(yōu)解為：74

從表中可見，xk*比

xk近于x*的速度慢得多，用乘子法迭代6次就達(dá)