非线性规划理论与算法.ppt
1,非线性规划理论与算法,非线性规划及其最优性条件对偶理论外点罚函数法内点罚函数法,非线性规划及其最优性条件,3,约束集或可行域:,非线性规划,x*是整体(全局)极小点,x*是严格整体(全局)极小点,x*是局部极小点,x*是严格局部极小点,非线性规划向量化表示,p=q=0即无约束规划,4,非线性规划的几个概念,线性化可行方向:,可行方向锥,5,定义3:积极约束:,或起作用约束（紧约束积极约束有效约束）。,6,证明:,定理1:,定义4:可行下降方向,7,定理2:,定理3:,证略,极值点的必要条件:,8,严格凸组合,严格凸,线性组合,为凸规划。,若f(x)是凸函数，S是凸集，,一般要求,当i=1,2,p时为凸函数，当i=p+1,p+q时为线性函数。,凸规划的局部解是整体解！,9,10,定理：可微函数解的必要条件：x*是局部解,则：,最优性条件,无约束规划,x*是驻点(稳定点),可微凸函数解的充要条件：x*是整体极小解当且仅当,11,约束规划最优性条件的几何表述,梯度共线,12,共面梯度被线性标示,约束规划最优性条件的几何表述,13,结论：在解处仅等式(紧)约束有效！,约束规划最优性条件的几何表述,14,对约束,定义7.有效约束(紧约束、积极约束)active constraint,在x*处有,则称在x*处ci(x)是紧约束。,x*处有效约束指标集,梯度的负线性表示!,15,向量化表示,约束规划最优性必要条件,Karush-Kuhn-Tucker条件KKT条件,16,Lagrange函数,Karush-Kuhn-Tucker条件KKT条件,Lagrange乘子：,互补松弛条件：,约束规格约束限制(规范)条件,17,约束规划最优性充分条件,鞍点条件,同时,的最优解！,证明：,由 的任意性知:,且,进一步由不等式的后两部分知:,18,凸规划最优性充要条件,Karush-Kuhn-Tucker条件KKT条件,19,定理(Fritz John条件):,其他最优性条件,20,Fritz John 条件与KKT条件的区别:Fritz John 条件可能出现w0=0的情形。这时Fritz John 条件中实际上不包含目标函数的任何数据，只是把起作用约束的梯度组合成零向量。这样的条件，对于问题的解的描述，没有多大价值。我们感兴趣的是w00的情形，所以为了保证 w00，还需要对约束施加某种限制。这种限制条件通常称为约束规格。在上一个定理中，如果增加紧约束的梯度线性无关的约束规格，则给出问题的KKT条件。,21,1)所有规划解的最优性必要条件=KKT条件+约束规格,2)凸规划解的最优性充分条件=KKT条件,最优性条件总结,最优性必要条件证明：需要用到凸集分离定理、择一性定理(Farkas引理,凸规划最优性充分条件证明较简单，但对非凸规划结果没有实际指导意义，蕴含着对偶原理Langrange对偶,22,例:求约束极值问题,23,24,25,26,最优性条件举例,线性规划,最优性条件,是充分的？是必要的？,标准形式：,练习：推广形式的最优性条件,27,最优性条件举例,二次规划,最优性条件,什么条件下是充分的？,什么条件下是必要的？,推广一：,推广二：,简化：,对偶理论,29,最大最小对偶,目标函数:,x方的目标是无论y怎样，都应使F越小越好；y方的目标是无论x怎样，都应使F越大越好；,立于不败之地的决策方法,保守主义决策,相关结论：,一对对偶问题,弱对偶定理,对偶间隙,30,最大最小对偶举例博弈,31,最大最小对偶,鞍点条件:对,相关结论：,弱对偶定理,对偶间隙,若有点,则称(x*,y*)满足鞍点条件。,强对偶定理,满足鞍点条件。,32,原规划:,Lagrange对偶,Lagrange函数,Lagrange对偶,弱对偶性:,弱对偶定理,对偶间隙,原规划,凹函数,33,Lagrange对偶举例,34,像集,35,36,37,连续可微凸规划:,强对偶定理：连续可微凸规划，满足一约束规格，则,Lagrange对偶的强对偶定理,f、g可微凸，h线性,1)：若原问题有解，则对偶问题也有解；,2)：若原问题与对偶问题分别有可行解，则他们是最优解的充分必要条件是他们对应相同的目标值(对偶间隙为0).,证1)：即证可微凸规划的最优解,与其KKT条件的乘子,满足鞍点条件！,证2)：利用鞍点条件可得。,3)：对偶问题无上界，则原问题不可行；原问题无下界，则对偶问题不可行。,38,连续可微凸规划:,Wolfe对偶：,Wolfe对偶,f、g可微凸，h线性,1)：若原问题有解，则对偶问题也有解；,2)：若原问题与对偶问题分别有可行解，则他们是最优解得充分必要条件是他们对应相同的目标值(对偶间隙为0).,Lagrange函数,Wolfe对偶定理：连续可微凸规划，满足一约束规格，则,39,凸规划对偶举例(Q正定),二次规划(Q正定),推广一：,推广二：,Lagrange对偶,共轭对偶、广义Lagrange对偶,参阅非线性规划及其理论(应玖茜、魏权龄)第6章,罚函数法,41,惩罚函数法,将有约束优化问题转化为一系列无约束优化问题进行求解。（Sequential Unconstrained Minimization Technique-SUMT）,1、算法思想：,2、算法类型：,外点法（外惩法）内点法（内惩法）,3、问题：,42,4、外点法（外部惩罚函数法）,43,44,45,（1）几何解释,46,（2）算法步骤（外点法）：,47,yes,No,（3）外点法框图,48,（4）应注意的问题,49,例:,50,参阅P207例2关于2个约束的例子!,51,（5）一般模型的外点法,算法步骤相同,52,(6)算法收敛性,详见P202，引理8.1，定理8.2.,详见P203，定理8.4.,53,5、内点法（障碍函数法）,（1）集合结构,54,（2）算法思想,内点法（障碍函数法）的迭代点是在可行域点集内部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。,内点法要求可行点集的内点集合非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。,55,（3）算法分析,56,57,（4）算法步骤（内点法）：,58,内点法框图,yes,No,59,例,解,60,用对数罚函数会更简单,其他例子见P217-218.,61,（5）算法收敛性：,（6）罚函数法的缺点,62,(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.惩罚项的二阶偏导在S的边界上不存在 4.迭代中x(k)R5.非凸规划适用,内点法,外点法,作业：P246.1,2,4,7,8,9,10.补充求2、9、10、11中规划的KKT点.,63,6.乘子法,乘子罚函数:,乘子罚函数与Langrange函数及惩罚函数的区别：多一项。,(1)等式约束,64,乘子罚函数:,65,(2)等式、不等式约束,66,算法步骤（乘子罚函数法）：,67,解：1.惩罚函数法。对于惩罚函数,例：问题,的最优解为x*=(0.25,0.75),分别用惩罚函数法和乘子法 求它的迭代点列。,可求得最优解为：,2.乘子法。对于乘子罚函数,可求得最优解为：,68,从表中可见，xk*比 xk 近于x*的速度慢得多，用乘子法迭代6次就达到惩罚函数法迭代15次的效 这里，惩罚因子在惩罚函数法中要增大到u153276.8，而在乘子法中只要增大到u6=6.4 相比之下，乘子法不需过分地增大惩罚因子，确实比惩罚函数法有效很多.,69,Matlab求解约束非线性规划,其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是约束向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。,70,函数 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(),71,解:(1)写成标准形式：,例1,72,(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,73,解：约束条件的标准形式为,（1）在MATLAB编辑器中建立非线性约束函数文件：function c,ceq=nlcon(x)c=(x(1)-1)2-x(2);ceq=;%无等式约束,74,（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=;%无线性等式约束beq=;lb=;%x没有下、上界ub=;x,fval,exitflag,output,lambda,grad,hessian=fmincon(fun2,x0,A,b,Aeq,beq,lb,ub,nlcon),75,则结果为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,76,二次规划问题（quadratic programming）的Matlab解,77,函数 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=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满足等约束条件,78,在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),79,80,考核要点,基础知识优化问题的模型表示、梯度计算、凸函数判定等一维搜索方法无约束优化方法线性规划单纯形方法两阶段M方法等非线性规划KKT条件、外点法、内点法等注重方法掌握，难度类似作业.,考试时间：元月9号上午8:30-11:303小时时间充裕，有繁琐计算的话不要心急。,
