《第五章约束问题的最优化方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《第五章约束问题的最优化方法ppt课件.ppt（63页珍藏版）》请在三一办公上搜索。
1、1,第七讲 约束非线性规划,约束极值及最优性条件 等式约束 不等式约束 一般约束问题 约束极值问题的算法 外点法 内点法 乘子法,2,1、约束极值问题的表示,一 、约束极值问题的最优性条件,3,4,2 约束极值及最优性条件Kuhn-Tucker 条件,（1）等式约束性问题的最优性条件,考虑 min f(x) s.t. h(x)=0 回顾高等数学中所学的条件极值： 问题 求 z = f(x,y)极值，在(x,y)=0的条件下。 即： min f(x,y) s.t. (x,y)=0 引入Lagrange乘子： Lagrange函数 L(x,y;)= f(x,y)+ (x,y),5,若x*是其的最优
2、解 , 则存在* Rl 使,6,几何意义：考虑一个约束的情况：,x,最优性条件即：,7,(2)不等式约束极值问题的最优性条件,可行方向:,可行方向与积极约束:,8,积极约束:,例:,或 起作用约束（紧约束积极约束有效约束）。,9,如何判断一个方向是可行方向?,10,证明:,定理1:,可行下降方向:,11,定理2:,定理3:,证略,极值点的必要条件:,12,13,14,15,16,定理4(K-T条件):,17,18,例: 求约束极值问题,19,20,21,22,定理5(Fritz John条件):,23,定理 (K-T条件):,24,（一）惩罚函数法（SUMT）,二、约束极值问题的算法,将有约束
3、优化问题转化为一系列无约束优化问题进行求解。（Sequential Unconstrained Minimization Technique - SUMT）,1、算法思想：,2、算法类型：,外点法（外惩法） 内点法（内惩法）,25,3、问题：,26,4、外点法（外部惩罚函数法）,27,28,29,（1）几何解释,30,（3）算法步骤（外点法）：,31,yes,No,外点法框图,32,（4）应注意的问题,33,例:,34,35,（7）一般模型的外点法,算法步骤相同,36,(8)算法收敛性,37,5、内点法（障碍函数法）,（1）集合结构,38,（2）算法思想,内点法（障碍函数法）的迭代点是在可行域
4、点集内部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。,内点法要求可行点集的内点集合非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。,39,（3）算法分析,40,41,（4）算法步骤（内点法）：,42,内点法框图,yes,No,43,例,解,44,45,（5）算法收敛性：,（6）罚函数法的缺点,46,(7)内、外点法的优缺点的比较,1. x(0)S 02.等式约束不适用3.障碍函数B(x) 在S 0的可微阶数与gi(x)相同(可选用的无约束最优化方法广)4.迭代中x（k）R （随时可取
5、x（k）x*）5.非凸规划适用,1.任意x(0)Rn2.等式约束适用3.惩罚项的二阶偏导在S的边界上不存在 4.5.非凸规划适用,内点法,外点法,47,6. 乘子法,乘子罚函数:,乘子罚函数与Langrange函数及惩罚函数的区别：多一项。,(1)等式约束,48,乘子罚函数:,49,(2)等式、不等式约束,50,算法步骤（乘子罚函数法）：,51,解：1. 惩罚函数法。对于惩罚函数,例： 问题,的最优解为x* =(0.25, 0.75),分别用惩罚函数法和乘子法 求它的迭代点列。,可求得最优解为：,2. 乘子法。对于乘子罚函数,可求得最优解为：,52,从表中可见，xk*比 xk 近于x*的速度慢
6、得多，用乘子法迭代6次就达到惩罚函数法迭代15次的效 这里，惩罚因子在惩罚函数法中要增大到u153276.8，而在乘子法中只要增大到u6=6.4 相比之下，乘子法不需过分地增大惩罚因子，确实比惩罚函数法有效很多.,53,Matlab求解约束非线性规划,其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是约束向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。,54,函数 fmincon格式 x = fmincon(fun,x0,A,b)x = fmincon(fun,x0,A,b,Aeq,beq)x = fmincon(fun,x0,
7、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,fval,exitflag,output,lambda = fmincon()x,fval,exitflag,output,lambda,grad = fmincon()x,fval,exitflag,ou
8、tput,lambda,grad,hessian = fmincon(),55,解: (1)写成标准形式：,例1,56,(2)先建立M-文件 fun1.m: function f=fun1(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,(3)再建立主程序youh1.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; LB=0;0; UB=; x,fval=fmincon(fun1,x0,A,b,Aeq,beq,LB,UB),(4)在命令窗口中输入youh1,得运算结果为： x = 0.7647 1.0588 fval = -
9、2.0294,57,解：约束条件的标准形式为,（1）在MATLAB编辑器中建立非线性约束函数文件：function c, ceq=nlcon (x)c=(x(1)-1)2-x(2);ceq= ; %无等式约束,58,（1）在MATLAB编辑器中建立非线性约束函数文件：function c, ceq=nlcon (x)c=(x(1)-1)2-x(2);ceq= ; %无等式约束,（2）在命令窗口键入如下命令或建立M文件：fun2=x(1)2+x(2)2-x(1)*x(2)-2*x(1)-5*x(2); %目标函数x0=0 1;A=-2 3; %线性不等式约束b=6;Aeq= ; %无线性等式约束
10、beq= ;lb= ; % x没有下、上界ub= ;x,fval,exitflag,output,lambda,grad,hessian=fmincon(fun2,x0,A,b,Aeq,beq,lb,ub,nlcon),59,则结果为x = 3 4fval = -13exitflag = %解收敛 1output = iterations: 2 funcCount: 9 stepsize: 1 algorithm: medium-scale: SQP, Quasi-Newton, line-search firstorderopt: cgiterations: lambda = lower:
11、2x1 double %x下界有效情况，通过lambda.lower可查看。 upper: 2x1 double %x上界有效情况，为0表示约束无效。 eqlin: 0 x1 double %线性等式约束有效情况，不为0表示约束有效。 eqnonlin: 0 x1 double %非线性等式约束有效情况。 ineqlin: 2.5081e-008 %线性不等式约束有效情况。 ineqnonlin: 6.1938e-008 %非线性不等式约束有效情况。grad = %目标函数在最小值点的梯度 1.0e-006 * -0.1776 0hessian = %目标函数在最小值点的Hessian值 1.
12、0000 -0.0000 -0.0000 1.0000,60,二次规划问题（quadratic programming）的Matlab解,61,函数 quadprog,x = quadprog(H,f,A,b,Aeq,beq,lb,ub) % lb,ub分别为为x的下上界。x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) %x0为设置的初值x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) % options为指定的优化参数x,fval = quadprog() %fval为目标函数最优值x,fval,exitflag =
13、quadprog() % exitflag与线性规划中参数意义相同x,fval,exitflag,output = quadprog() % output与线性规划中参数意义相同x,fval,exitflag,output,lambda = quadprog() % lambda与线性规划中参数意义相同,格式: x = quadprog(H,f,A,b) %其中H,f,A,b为标准形中的参数，x为目标函数的最小值。x = quadprog(H,f,A,b,Aeq,beq) %Aeq,beq满足等约束条件,62,在MATLAB中实现如下：H = 1 -1; -1 2 ;f = -2; -6;A = 1 1; -1 2; 2 1;b = 2; 2; 3;lb = zeros(2,1);x,fval,exitflag,output,lambda = quadprog(H,f,A,b, , ,lb),63,
