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

《非线性规划理论与算法.ppt》由会员分享，可在线阅读，更多相关《非线性规划理论与算法.ppt（80页珍藏版）》请在装配图网上搜索。

1、1,非线性规划理论与算法,非线性规划及其最优性条件 对偶理论 外点罚函数法 内点罚函数法,非线性规划及其最优性条件,3,约束集或可行域:,非线性规划,x*是整体(全局)极小点,x*是严格整体(全局)极小点,x*是局部极小点,x*是严格局部极小点,非线性规划向量化表示,p=q=0即无约束规划,4,非线性规划的几个概念,线性化可行方向:,可行方向锥,5,定义3: 积极约束:,或起作用约束（紧约束积极约束有效约束）。,6,证明:,定理1:,定义4: 可行下降方向,7,定理2:,定理3:,证略,极值点的必要条件:,8,严格凸组合,严格凸,线性组合,为凸规划。,若f(x)是凸函数，S是凸集，,一般要求,

2、当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,

3、向量化表示,约束规划最优性必要条件,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的情形

4、。这时Fritz John 条件中实际上不包含目标函数的任何数据，只是把起作用约束的梯度组合成零向量。这样的条件，对于问题的解的描述，没有多大价值。我们感兴趣的是w00的情形，所以为了保证 w00 ，还需要对约束施加某种限制。这种限制条件通常称为约束规格。在上一个定理中，如果增加紧约束的梯度线性无关的约束规格，则给出问题的KKT条件。,21,1) 所有规划解的最优性必要条件=KKT条件+约束规格,2) 凸规划解的最优性充分条件=KKT条件,最优性条件总结,最优性必要条件证明：需要用到凸集分离定理、择一性定理(Farkas引理,凸规划最优性充分条件证明较简单，但对非凸规划结果没有实际指导意义，蕴

5、含着对偶原理Langrange对偶,22,例: 求约束极值问题,23,24,25,26,最优性条件举例,线性规划,最优性条件,是充分的？是必要的？,标准形式：,练习：推广形式的最优性条件,27,最优性条件举例,二次规划,最优性条件,什么条件下是充分的？,什么条件下是必要的？,推广一：,推广二：,简化：,对偶理论,29,最大最小对偶,目标函数:,x方的目标是无论y怎样，都应使F越小越好； y方的目标是无论x怎样，都应使F越大越好；,立于不败之地的决策方法,保守主义决策,相关结论：,一对对偶问题,弱对偶定理,对偶间隙,30,最大最小对偶举例博弈,31,最大最小对偶,鞍点条件: 对,相关结论：,弱对

6、偶定理,对偶间隙,若有点,则称(x*,y*)满足鞍点条件。,强对偶定理,满足鞍点条件。,32,原规划:,Lagrange对偶,Lagrange函数,Lagrange对偶,弱对偶性:,弱对偶定理,对偶间隙,原规划,凹函数,33,Lagrange对偶举例,34,像集,35,36,37,连续可微凸规划:,强对偶定理：连续可微凸规划，满足一约束规格，则,Lagrange对偶的强对偶定理,f、g可微凸，h线性,1)：若原问题有解，则对偶问题也有解；,2)：若原问题与对偶问题分别有可行解，则他们是最优解的充分必要条件是他们对应相同的目标值(对偶间隙为0).,证1)：即证可微凸规划的最优解,与其KKT条件的

7、乘子,满足鞍点条件！,证2)：利用鞍点条件可得。,3)：对偶问题无上界，则原问题不可行；原问题无下界，则对偶问题不可行。,38,连续可微凸规划:,Wolfe对偶：,Wolfe对偶,f、g可微凸，h线性,1)：若原问题有解，则对偶问题也有解；,2)：若原问题与对偶问题分别有可行解，则他们是最优解得充分必要条件是他们对应相同的目标值(对偶间隙为0).,Lagrange函数,Wolfe对偶定理：连续可微凸规划，满足一约束规格，则,39,凸规划对偶举例(Q正定),二次规划(Q正定),推广一：,推广二：,Lagrange对偶,共轭对偶、广义Lagrange对偶,参阅非线性规划及其理论 (应玖茜、魏权龄)

8、第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，

9、定理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）罚函数

10、法的缺点,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)Rn 2.等式约束适用 3.惩罚项的二阶偏导在S的边界上不存在 4.迭代中x(k) R 5.非凸规划适用,内点法,外点法,作业：P246. 1,2,4,7,8,9,10. 补充求2、9、10、11中规划的KKT点.,63,6. 乘子法,乘子罚函数:,乘子罚函数与Langrange函数及惩罚函数的区别：多一项。

11、,(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求解约束

12、非线性规划,其中： 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,option

13、s) 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

14、*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= ; %无等式约束,

15、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

16、,beq,lb,ub,nlcon),75,则结果为 x = 3 4 fval = -13 exitflag = %解收敛 1 output = 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

17、double %线性等式约束有效情况，不为0表示约束有效。 eqnonlin: 0 x1 double %非线性等式约束有效情况。 ineqlin: 2.5081e-008 %线性不等式约束有效情况。 ineqnonlin: 6.1938e-008 %非线性不等式约束有效情况。 grad = %目标函数在最小值点的梯度 1.0e-006 * -0.1776 0 hessian = %目标函数在最小值点的Hessian值 1.0000 -0.0000 -0.0000 1.0000,76,二次规划问题（quadratic programming）的Matlab解,77,函数 quadprog,x

18、= 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与线性规

19、划中参数意义相同 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小时 时间充裕，有繁琐计算的话不要心急。,