非线性规划理论与算法.ppt

《非线性规划理论与算法.ppt》由会员分享，可在线阅读，更多相关《非线性规划理论与算法.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、非线性规划理论与算法非线性规划理论与算法非线性规划及其最优性条件非线性规划及其最优性条件对偶理论对偶理论外点罚函数法外点罚函数法内点罚函数法内点罚函数法123非线性规划的几个概念非线性规划的几个概念4定义定义3:积极约束积极约束:或起作用约束起作用约束（紧约束紧约束积极约束积极约束有效约束有效约束）。）。5证明:定理定理1:定义定义4:可行下降方向可行下降方向6定理2:定理3:证略极值点的必要条件:7891011121314互补互补松弛松弛条件条件15161718定理定理(Fritz John条件条件):19Fritz John 条件与条件与KKT条件的区别条件的区别:Fritz John 条

2、件可能出现条件可能出现w0=0的情形。这的情形。这时时Fritz John 条件中实际上不包含目标函数的条件中实际上不包含目标函数的任何数据，只是把起作用约束的梯度组合成零任何数据，只是把起作用约束的梯度组合成零向量。这样的条件，对于问题的解的描述，没向量。这样的条件，对于问题的解的描述，没有多大价值。我们感兴趣的是有多大价值。我们感兴趣的是w00的情形，所的情形，所以为了保证以为了保证 w00，还需要对约束施加某种限，还需要对约束施加某种限制。这种限制条件通常称为制。这种限制条件通常称为约束规格约束规格。在上一。在上一个定理中，如果增加个定理中，如果增加紧约束紧约束的梯度线性无关的的梯度线性

3、无关的约束规格约束规格，则给出问题的，则给出问题的KKT条件。条件。2021例例:求约束极值问题求约束极值问题22232425262728293031原规划原规划凹函数凹函数323334353637383940惩罚函数法惩罚函数法 将有约束优化问题转化为一系列无约束优化问题进行求解。将有约束优化问题转化为一系列无约束优化问题进行求解。（Sequential Unconstrained Minimization Technique-SUMT）1 1、算法思想：、算法思想：2 2、算法类型：、算法类型：q 外点法（外惩法）外点法（外惩法）q 内点法（内惩法内点法（内惩法）3 3、问题：、问题：41

4、4 4、外点法（外部惩罚函数法）、外点法（外部惩罚函数法）424344（1 1）几何解释）几何解释45（2 2）算法步骤（外点法）：）算法步骤（外点法）：46yesNo（3 3 3 3）外点法框图外点法框图外点法框图外点法框图47（4 4）应注意的问题）应注意的问题48例:4950q （5 5）一般模型的外点法）一般模型的外点法q q 算法步骤相同算法步骤相同51(6)(6)算法收敛性算法收敛性525 5、内点法（障碍函数法）、内点法（障碍函数法）（1 1）集合结构）集合结构53（2 2）算法思想）算法思想 内点法（障碍函数法）的迭代点是在可行域点集内内点法（障碍函数法）的迭代点是在可行域点集

5、内部移动的，对接近可行域边界上的点施加越来越大的惩部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。界是一道障碍物，阻碍迭代点穿越边界。内点法要求可行点集的内点法要求可行点集的内点集合非空内点集合非空，否则算法无法，否则算法无法运行。这样一来运行。这样一来内点法只对不等式约束的优化问题内点法只对不等式约束的优化问题才可能才可能有效。有效。54（3 3）算法分析）算法分析5556（4 4）算法步骤（内点法）：）算法步骤（内点法）：57内点法框图内点法框图内点法框图内点

6、法框图yesNo58例解5960（5 5）算法收敛性：）算法收敛性：（6 6 6 6）罚函数法的缺点）罚函数法的缺点）罚函数法的缺点）罚函数法的缺点61(7)(7)内、外点法的优缺点的比较内、外点法的优缺点的比较1.x(0)S 0(参参阅P220讨论内点的内点的选取取)2.等式等式约束束不适用不适用3.障碍函数障碍函数B(x)在在S 0的可微的可微阶数与数与gi(x)相同相同(可可选用的无用的无约束最束最优化方法广化方法广)4.迭代中迭代中x（k）R(随随时可取可取x（k）x*)5.非凸非凸规划适用划适用1.任意任意x(0)Rn2.等式约束适用等式约束适用3.惩罚项的二阶偏导在惩罚项的二阶偏导

7、在S的边界的边界上不存在上不存在 4.迭代中迭代中x(k)R5.非凸非凸规划适用划适用内点法内点法外点法外点法626.6.乘子法乘子法乘子法乘子法乘子罚函数乘子罚函数:乘子罚函数与乘子罚函数与LangrangeLangrange函数及惩罚函数的区别：函数及惩罚函数的区别：多一项多一项。(1)(1)等式约束等式约束63乘子罚函数:64(2)等式、不等式约束等式、不等式约束65算法步骤（乘子罚函数法）：算法步骤（乘子罚函数法）：66解：1.惩罚函数法。对于惩罚函数惩罚函数法。对于惩罚函数例：问题 的最优解为的最优解为x x*=(0.25,0.75),=(0.25,0.75),分别分别用惩罚函数法和

8、乘子法用惩罚函数法和乘子法 求它的迭代求它的迭代点列。点列。可求得最优解为：可求得最优解为：2.乘子法。对于乘子罚函数乘子法。对于乘子罚函数可求得最优解为：可求得最优解为：67 从表中可见，从表中可见，xk*比比 xk 近于近于x*的的速度慢得多，用乘子法迭代速度慢得多，用乘子法迭代6次就次就达到惩罚函数法迭代达到惩罚函数法迭代15次的效次的效 这里，惩罚因子在惩罚函数法这里，惩罚因子在惩罚函数法中要增大到中要增大到u153276.8，而在乘，而在乘子法中只要增大到子法中只要增大到u6=6.4 相比之下，乘子法不需过分地相比之下，乘子法不需过分地增大惩罚因子，确实比惩罚函数增大惩罚因子，确实比

9、惩罚函数法有效很多法有效很多.68Matlab求解约束非线性规划其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是约束向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。69函数 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,nonlco

10、n,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()70解:(1)写成标准形式：例例171(2)先建立M-文件 fun1.m:function f=fun1(x);f=-x(1)-2*x(2)+(1/2)*x(1)2

11、+(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.029472解：约束条件的标准形式为（1）在MATLAB编辑器中建立非线性约束函数文件：function c,ceq=nlcon(x)c=(x(1)-1)2-x(2);ceq=;%无等式约束73（1 1）在）在MATLABMATLAB编辑器中建立非线性约束函数文件

12、：编辑器中建立非线性约束函数文件：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

13、;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)74则结果为则结果为x=3 4fval=-13exitflag=%解收敛解收敛 1output=iterations:2

14、 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%非线性等式

15、约束有效情况。非线性等式约束有效情况。ineqlin:2.5081e-008%线性不等式约束有效情况。线性不等式约束有效情况。ineqnonlin:6.1938e-008%非线性不等式约束有效情况。非线性不等式约束有效情况。grad=%目标函数在最小值点的梯度目标函数在最小值点的梯度 1.0e-006*-0.1776 0hessian=%目标函数在最小值点的目标函数在最小值点的Hessian值值 1.0000 -0.0000 -0.0000 1.000075二次规划问题（二次规划问题（quadratic programming）的）的Matlab解解 76函数 quadprogx=quadpr

16、og(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,la

17、mbda=quadprog()%lambda与线性规划中参数意义相同格式:x=quadprog(H,f,A,b)%其中H,f,A,b为标准形中的参数，x为目标函数的最小值。x=quadprog(H,f,A,b,Aeq,beq)%Aeq,beq满足等约束条件77在在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)7879考核要点基础知识基础知识优化问题的模型表示、梯度计算、优化问题的模型表示、梯度计算、凸函数判定等凸函数判定等一维搜索方法一维搜索方法无约束优化方法无约束优化方法线性规划线性规划单纯形方法单纯形方法两阶段两阶段M方法等方法等非线性规划非线性规划KKT条件、外点法、内点法等条件、外点法、内点法等注重方法掌握，难度类似作业注重方法掌握，难度类似作业.80