管理运筹学 课件 11有约束非线性规划

1OperationalResearch

运筹学哈尔滨理工大学管理学院SchoolofManagement

HarbinUniversityofScienceandTechnology田世海教授2Chapter11第11章ConstrainedOptimization约束极值问题OperationalResearchNonlinearProgramming非线性规划3ConstrainedOptimization约束极值及最优性条件不等式约束一般约束问题主要内容等式约束约束极值问题的算法内点法乘子法外点法41、约束极值问题的表示一、约束极值问题的最优性条件562约束极值及最优性条件——Kuhn-Tucker条件（1）等式约束性问题的最优性条件

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

回顾高等数学中所学的条件极值：

问题求z=f(x,y)极值，在ф(x,y)=0的条件下。即：minf(x,y)s.t.ф(x,y)=0

引入Lagrange乘子：λ

Lagrange函数L(x,y;λ)=f(x,y)+λф(x,y)7若x*是其的最优解,则存在υ*∈Rl

使8

几何意义：考虑一个约束的情况：x'

最优性条件即：9(2)不等式约束极值问题的最优性条件可行方向:①可行方向与积极约束:10积极约束:例:或起作用约束（紧约束\积极约束\有效约束）。11②如何判断一个方向是可行方向?12证明:定理1:可行下降方向:13定理2:定理3:证略③极值点的必要条件:1415161718定理4(K-T条件):192021222324252627282930313233作业:

求约束极值问题34353637（一）惩罚函数法（SUMT）二、约束极值问题的算法

将有约束优化问题转化为一系列无约束优化问题进行求解。（SequentialUnconstrainedMinimizationTechnique-SUMT）1、算法思想：2、算法类型：

外点法（外惩法）内点法（内惩法）383、问题：394、外点法（外部惩罚函数法）40414243（1）几何解释44（2）算法步骤（外点法）：45yesNo（3）外点法框图46（4）应注意的问题47例:

484950

（5）一般模型的外点法

算法步骤相同51例:

525354555、内点法（闸函数法、障碍函数法）（1）集合结构56（2）算法思想

内点法（障碍函数法）的迭代点是在可行域点集内部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。

内点法要求可行点集的内点集合非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。57（3）算法分析5859（4）算法步骤（内点法）：60内点法框图yesNo61例解6263例解6465例解66（5）罚函数法的缺点67(6)内、外点法的优缺点的比较1.x(0)∈S02.等式约束不适用3.障碍函数B(x)在S0的可微阶数与gi(x)相同(可选用的无约束最优化方法广)4.迭代中x（k）∈R

（随时可取x（k）≈x*）5.非凸规划适用1.任意x(0)∈Rn2.等式约束适用3.惩罚项的二阶偏导在S的边界上不存在4.5.非凸规划适用内点法外点法迭代中x（k）RÏ686.乘子法乘子罚函数:乘子罚函数与Langrange函数及惩罚函数的区别：多一项。

(1)等式约束69乘子罚函数:70(2)等式、不等式约束71算法步骤（乘子罚函数法）：72解：1.惩罚函数法。对于惩罚函数例：问题的最优解为x*=(0.25,0.75),分别用惩罚函数法和乘子法求它的迭代点列。

可求得最优解为：

2.乘子法。对于乘子罚函数73可求得最优解为：74

从表中可见，xk*比

xk近于x*的速度慢得多，用乘子法迭代6次就达