最优性条件和罚函数法公开课一等奖优质课大赛微课获奖课件.pptx

约束极值及最优性条件约束极值及最优性条件 等式约束等式约束 不等式约束不等式约束 普通约束问题普通约束问题 可行方向法可行方向法 既约梯度法既约梯度法 广义既约梯度法广义既约梯度法 处分函数法处分函数法 外点法外点法 内点法内点法 乘子法乘子法第六章第六章 约束最优化办法约束最优化办法第1页第1页1 1、约束极值问题表示、约束极值问题表示一一 、约束极值问题最优性条件、约束极值问题最优性条件第2页第2页第3页第3页2 约束极值及最优性条件约束极值及最优性条件Kuhn-Tucker 条件条件（1 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)第4页第4页若若x*是其最优解是其最优解 ,则存在则存在*Rl 使使第5页第5页 几何意义几何意义：考虑一个约束情况：考虑一个约束情况：x 最优性条件即：最优性条件即：第6页第6页(2)(2)不等式约束极值问题最优性条件不等式约束极值问题最优性条件可行方向可行方向:可行方向与积极约束可行方向与积极约束:第7页第7页积极约束积极约束:例:或起作用约束起作用约束（紧约束紧约束积极约束积极约束有效约束有效约束）。）。第8页第8页如何判断一个方向是可行方向如何判断一个方向是可行方向?第9页第9页证实:定理定理1:可行下降方向可行下降方向:第10页第10页定理2:定理3:证略极值点必要条件:第11页第11页第12页第12页第13页第13页第14页第14页第15页第15页定理定理4(K-T条件条件):第16页第16页第17页第17页例例:求约束极值问题求约束极值问题第18页第18页第19页第19页第20页第20页第21页第21页定理定理5(Fritz John条件条件):第22页第22页定理(K-T条件):第23页第23页二、解线性约束问题既约梯度法二、解线性约束问题既约梯度法第24页第24页第25页第25页第26页第26页第27页第27页第28页第28页第29页第29页第30页第30页算法：算法：x(1)S,k=1k=k+1Jk=j|xj为x(k)中最大m个正分量之一B=,aj(jJk),N=,aj(jJk),YNT=NfT(x(k)-BfT(x(k)B-1NdB=-B-1NdN解得 x(k+1)=x(k)+kdd=0?YNStop;x(k)K-T点 第31页第31页第32页第32页二、广义既约梯度法二、广义既约梯度法第33页第33页第34页第34页（一）处分函数法（一）处分函数法（SUMTSUMT）将有约束优化问题转化为一系列无约束优化问题进行求解。将有约束优化问题转化为一系列无约束优化问题进行求解。（Sequential Unconstrained Minimization Technique-SUMT）1 1、算法思想：、算法思想：2 2、算法类型：、算法类型：q 外点法（外惩法）外点法（外惩法）q 内点法（内惩法）内点法（内惩法）三、约束极值问题算法三、约束极值问题算法第35页第35页3 3、问题：、问题：第36页第36页4 4、外点法（外部处分函数法）、外点法（外部处分函数法）第37页第37页第38页第38页第39页第39页（1 1）几何解释）几何解释第40页第40页（2 2）算法环节（外点法）：）算法环节（外点法）：第41页第41页yesNo（2 2）外点法框图外点法框图第42页第42页（4 4）应注意问题）应注意问题第43页第43页例:第44页第44页第45页第45页q （7 7）普通模型外点法）普通模型外点法q q 算法环节相同算法环节相同第46页第46页(8)(8)算法收敛性算法收敛性第47页第47页5 5、内点法（障碍函数法）、内点法（障碍函数法）（1 1）集合结构）集合结构第48页第48页（2 2）算法思想）算法思想 内点法（障碍函数法）迭代点是在可行域点集内部内点法（障碍函数法）迭代点是在可行域点集内部移动，对靠近可行域边界上点施加越来越大处分，对可移动，对靠近可行域边界上点施加越来越大处分，对可行域边界上点施加无限大处分，这好比边界是一道障碍行域边界上点施加无限大处分，这好比边界是一道障碍物，阻碍迭代点穿越边界。物，阻碍迭代点穿越边界。内点法要求可行点集内点集合非空，不然算法无法运内点法要求可行点集内点集合非空，不然算法无法运营。这样一来营。这样一来内点法只对不等式约束优化问题内点法只对不等式约束优化问题才也许有效。才也许有效。第49页第49页（3 3）算法分析）算法分析第50页第50页第51页第51页（4 4）算法环节（内点法）：）算法环节（内点法）：第52页第52页内点法框图内点法框图yesNo第53页第53页例解第54页第54页第55页第55页（5 5）算法收敛性：）算法收敛性：（6 6）罚函数法缺点）罚函数法缺点第56页第56页(7)(7)内、外点法优缺点比较内、外点法优缺点比较1.x(0)S 02.2.等式等式约约束不合用束不合用3.3.障碍函数障碍函数B(x)在在S 0可微可微阶阶数数与与gi(x)相同相同(可可选选取无取无约约束最束最优优化化办办法广法广)4.迭代中迭代中x（k）R（随（随时时可取可取x（k）x*）5.5.非凸非凸规规划合用划合用1.任意任意x(0)Rn2.等式约束合用等式约束合用3.处分项二阶偏导在处分项二阶偏导在S边界边界上不存在上不存在 4.4.5.5.非凸非凸规规划合用划合用内点法内点法外点法外点法迭代中迭代中x（k）R 第57页第57页6.乘子法乘子法乘子罚函数乘子罚函数:乘子罚函数与乘子罚函数与LangrangeLangrange函数及处分函数区别：函数及处分函数区别：多一项。多一项。(1)(1)等式约束等式约束第58页第58页乘子罚函数:第59页第59页(2)等式、不等式约束等式、不等式约束第60页第60页算法环节（乘子罚函数法）：算法环节（乘子罚函数法）：第61页第61页解：1.处分函数法。对于处分函数处分函数法。对于处分函数例：问题 最优解为最优解为x x*=(0.25,0.75),=(0.25,0.75),分别用分别用处分函数法和乘子法处分函数法和乘子法 求它迭代点列。求它迭代点列。可求得最优解为：可求得最优解为：2.乘子法。对于乘子罚函数乘子法。对于乘子罚函数可求得最优解为：可求得最优解为：第62页第62页 从表中可见，从表中可见，xk*比比 xk 近于近于x*速速度慢得多，用乘子法迭代度慢得多，用乘子法迭代6次就达次就达到处分函数法迭代到处分函数法迭代15次效次效 这里，处分因子在处分函数法这里，处分因子在处分函数法中要增大到中要增大到u153276.8，而在乘，而在乘子法中只要增大到子法中只要增大到u6=6.4 相比之下，乘子法不需过度地相比之下，乘子法不需过度地增大处分因子，确实比处分函数增大处分因子，确实比处分函数法有效诸多法有效诸多.第63页第63页Matlab求解约束非线性规划其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是约束向量函数，f(x)为目的函数，f(x)、C(x)、Ceq(x)能够是非线性函数。第64页第64页函数 fmincon格式 x=fmincon(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,fval,exitflag,output,lambda=fmincon()x,fval,exitflag,output,lambda,grad=fmincon()x,fval,exitflag,output,lambda,grad,hessian=fmincon()第65页第65页解:(1)写成原则形式：例例1第66页第66页(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=-2.0294第67页第67页解：约束条件原则形式为（1）在MATLAB编辑器中建立非线性约束函数文献：function c,ceq=nlcon(x)c=(x(1)-1)2-x(2);ceq=;%无等式约束第68页第68页（1 1）在）在MATLABMATLAB编辑器中建立非线性约束函数文献：编辑器中建立非线性约束函数文献：function c,ceq=nlcon(x)function c,ceq=nlcon(x)c=(x(1)-1)2-x(2);c=(x(1)-1)2-x(2);ceq=;%ceq=;%无等式约束无等式约束（2 2）在命令窗口键入下列命令或建立）在命令窗口键入下列命令或建立MM文献：文献：fun2=x(1)2+x(2)2-x(1)*x(2)-2*x(1)-5*x(2);%fun2=x(1)2+x(2)2-x(1)*x(2)-2*x(1)-5*x(2);%目的函数目的函数x0=0 1;x0=0 1;A=-2 3;%A=-2 3;%线性不等式约束线性不等式约束b=6;b=6;Aeq=;%Aeq=;%无线性等式约束无线性等式约束beq=;beq=;lb=;%lb=;%x x没有下、上界没有下、上界ub=;ub=;x,fval,exitflag,output,lambda,grad,hessianx,fval,exitflag,output,lambda,grad,hessian=fmincon(fun2,x0,A,b,Aeq,beq,lb,ub,nlcon)=fmincon(fun2,x0,A,b,Aeq,beq,lb,ub,nlcon)第69页第69页则结果为则结果为x=3 4fval=-13exitflag=%解收敛解收敛 1output=iterations:2 funcCount:9 stepsize:1 algorithm:medium-scale:SQP,Quasi-Newton,line-search firstorderopt:cgiterations:lambda=lower: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.0000 -0.0000 -0.0000 1.0000第70页第70页二次规划问题（二次规划问题（quadratic programming）Matlab解解 第71页第71页函数 quadprogx=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=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满足等约束条件第72页第72页在在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)第73页第73页第74页第74页