资源描述：
《约束非线性规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第八讲约束非线性规划约束极值及最优性条件等式约束不等式约束一般约束问题约束极值问题的算法外点法内点法乘子法11、约束极值问题的表示一、约束极值问题的最优性条件232约束极值及最优性条件——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)4若x*是
2、其的最优解,则存在υ*∈Rl使5几何意义：考虑一个约束的情况：x'最优性条件即：6(2)不等式约束极值问题的最优性条件可行方向:①可行方向与积极约束:7积极约束:例:或起作用约束（紧约束积极约束有效约束）。8②如何判断一个方向是可行方向?9证明:定理1:可行下降方向:10定理2:定理3:证略③极值点的必要条件:1112131415定理4(K-T条件):1617例:求约束极值问题18192021定理5(FritzJohn条件):22定理(K-T条件):23（一）惩罚函数法（SUMT）二、约束极值问题的算法将有约束
3、优化问题转化为一系列无约束优化问题进行求解。（SequentialUnconstrainedMinimizationTechnique-SUMT）1、算法思想：2、算法类型：外点法（外惩法）内点法（内惩法）243、问题：254、外点法（外部惩罚函数法）262728（1）几何解释29（3）算法步骤（外点法）：30yesNo外点法框图31（4）应注意的问题32例:3334（7）一般模型的外点法算法步骤相同35(8)算法收敛性365、内点法（障碍函数法）（1）集合结构37（2）算法思想内点法（障碍函数法）的迭代点是在可行
4、域点集内部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。内点法要求可行点集的内点集合非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。38（3）算法分析3940（4）算法步骤（内点法）：41内点法框图yesNo42例解4344（5）算法收敛性：（6）罚函数法的缺点45(7)内、外点法的优缺点的比较1.x(0)∈S02.等式约束不适用3.障碍函数B(x)在S0的可微阶数与gi(x)相同(可选用的无约束最优化方法
5、广)4.迭代中x（k）∈R（随时可取x（k）≈x*）5.非凸规划适用1.任意x(0)∈Rn2.等式约束适用3.惩罚项的二阶偏导在S的边界上不存在4.5.非凸规划适用内点法外点法迭代中x（k）RÏ466.乘子法乘子罚函数:乘子罚函数与Langrange函数及惩罚函数的区别：多一项。(1)等式约束47乘子罚函数:48(2)等式、不等式约束49算法步骤（乘子罚函数法）：50解：1.惩罚函数法。对于惩罚函数例：问题的最优解为x*=(0.25,0.75),分别用惩罚函数法和乘子法求它的迭代点列。可求得最优解为：2.乘子法。对
6、于乘子罚函数可求得最优解为：51从表中可见，xk*比xk近于x*的速度慢得多，用乘子法迭代6次就达到惩罚函数法迭代15次的效．这里，惩罚因子在惩罚函数法中要增大到u15＝3276.8，而在乘子法中只要增大到u6=6.4．相比之下，乘子法不需过分地增大惩罚因子，确实比惩罚函数法有效很多.52Matlab求解约束非线性规划其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是约束向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。53函数fmincon格式x=f
7、mincon(fun,x0,A,b)x=fmincon(fun,x0,A,b,Aeq,beq)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)[x,fval]=fmincon(…)[x,fval,exitflag]=fmincon(…)[x,fval,exitflag,output]=fmincon(…)[x
8、,fval,exitflag,output,lambda]=fmincon(…)[x,fval,exitflag,output,lambda,grad]=fmincon(…)[x,fval,exitflag,output,lambda,grad,hessian]=fmincon(…)54解:(1)写成标准形式：例155(2)先建立M-文件fun1.m:fun
