非线性规划理论和算法

1、关于非线性规划理论与算法第一张，PPT共八十一页，创作于2022年6月非线性规划及其最优性条件第二张，PPT共八十一页，创作于2022年6月3约束集或可行域:非线性规划x*是整体(全局)极小点x*是严格整体(全局)极小点x*是局部极小点x*是严格局部极小点非线性规划向量化表示p=q=0即无约束规划第三张，PPT共八十一页，创作于2022年6月4非线性规划的几个概念线性化可行方向:可行方向锥第四张，PPT共八十一页，创作于2022年6月5定义3: 积极约束:或起作用约束（紧约束积极约束有效约束）。第五张，PPT共八十一页，创作于2022年6月6证明:定理1:定义4: 可行下降方向第六张，PPT共

2、八十一页，创作于2022年6月7定理2:定理3:证略极值点的必要条件:第七张，PPT共八十一页，创作于2022年6月8严格凸组合严格凸线性组合为凸规划。若f(x)是凸函数，S是凸集，一般要求当i=1,2,p时为凸函数，当i=p+1,p+q时为线性函数。凸规划的局部解是整体解！第八张，PPT共八十一页，创作于2022年6月9第九张，PPT共八十一页，创作于2022年6月10定理：可微函数解的必要条件：x*是局部解,则：最优性条件无约束规划x*是驻点(稳定点)可微凸函数解的充要条件：x*是整体极小解当且仅当第十张，PPT共八十一页，创作于2022年6月11约束规划最优性条件的几何表述梯度共线第十一

3、张，PPT共八十一页，创作于2022年6月12共面梯度被线性标示约束规划最优性条件的几何表述第十二张，PPT共八十一页，创作于2022年6月13结论：在解处仅等式(紧)约束有效！约束规划最优性条件的几何表述第十三张，PPT共八十一页，创作于2022年6月14对约束定义7. 有效约束(紧约束、积极约束)active constraint在x*处有则称在x*处ci(x)是紧约束。x*处有效约束指标集梯度的负线性表示!第十四张，PPT共八十一页，创作于2022年6月15向量化表示约束规划最优性必要条件Karush-Kuhn-Tucker条件KKT条件互补松弛条件第十五张，PPT共八十一页，创作于20

4、22年6月16Lagrange函数Karush-Kuhn-Tucker条件KKT条件Lagrange乘子：互补松弛条件：约束规格约束限制(规范)条件第十六张，PPT共八十一页，创作于2022年6月17约束规划最优性充分条件鞍点条件同时的最优解！证明：由 的任意性知:且进一步由不等式的后两部分知:第十七张，PPT共八十一页，创作于2022年6月18凸规划最优性充要条件Karush-Kuhn-Tucker条件KKT条件第十八张，PPT共八十一页，创作于2022年6月19定理 (Fritz John条件):其他最优性条件第十九张，PPT共八十一页，创作于2022年6月20Fritz John 条件与

5、KKT条件的区别: Fritz John 条件可能出现w0=0的情形。这时Fritz John 条件中实际上不包含目标函数的任何数据，只是把起作用约束的梯度组合成零向量。这样的条件，对于问题的解的描述，没有多大价值。我们感兴趣的是w00的情形，所以为了保证 w00 ，还需要对约束施加某种限制。这种限制条件通常称为约束规格。在上一个定理中，如果增加紧约束的梯度线性无关的约束规格，则给出问题的KKT条件。第二十张，PPT共八十一页，创作于2022年6月211) 所有规划解的最优性必要条件=KKT条件+约束规格2) 凸规划解的最优性充分条件=KKT条件最优性条件总结最优性必要条件证明：需要用到凸集分

6、离定理、择一性定理(Farkas引理凸规划最优性充分条件证明较简单，但对非凸规划结果没有实际指导意义，蕴含着对偶原理Langrange对偶第二十一张，PPT共八十一页，创作于2022年6月22例: 求约束极值问题第二十二张，PPT共八十一页，创作于2022年6月23第二十三张，PPT共八十一页，创作于2022年6月24第二十四张，PPT共八十一页，创作于2022年6月25第二十五张，PPT共八十一页，创作于2022年6月26最优性条件举例线性规划最优性条件是充分的？是必要的？标准形式：练习：推广形式的最优性条件第二十六张，PPT共八十一页，创作于2022年6月27最优性条件举例二次规划最优性条

7、件什么条件下是充分的？什么条件下是必要的？推广一：推广二：简化：第二十七张，PPT共八十一页，创作于2022年6月对偶理论第二十八张，PPT共八十一页，创作于2022年6月29最大最小对偶目标函数:x方的目标是无论y怎样，都应使F越小越好；y方的目标是无论x怎样，都应使F越大越好；立于不败之地的决策方法保守主义决策相关结论：一对对偶问题弱对偶定理对偶间隙第二十九张，PPT共八十一页，创作于2022年6月30最大最小对偶举例博弈第三十张，PPT共八十一页，创作于2022年6月31最大最小对偶鞍点条件: 对相关结论：弱对偶定理对偶间隙若有点则称(x*,y*)满足鞍点条件。强对偶定理满足鞍点条件。第

8、三十一张，PPT共八十一页，创作于2022年6月32原规划:Lagrange对偶Lagrange函数Lagrange对偶弱对偶性:弱对偶定理对偶间隙原规划凹函数第三十二张，PPT共八十一页，创作于2022年6月33Lagrange对偶举例第三十三张，PPT共八十一页，创作于2022年6月34像集第三十四张，PPT共八十一页，创作于2022年6月35第三十五张，PPT共八十一页，创作于2022年6月36第三十六张，PPT共八十一页，创作于2022年6月37连续可微凸规划:强对偶定理：连续可微凸规划，满足一约束规格，则Lagrange对偶的强对偶定理f、g可微凸，h线性1)：若原问题有解，则对偶问

9、题也有解；2)：若原问题与对偶问题分别有可行解，则他们是最优解的充分必要条件是他们对应相同的目标值(对偶间隙为0).证1)：即证可微凸规划的最优解与其KKT条件的乘子满足鞍点条件！证2)：利用鞍点条件可得。3)：对偶问题无上界，则原问题不可行；原问题无下界，则对偶问题不可行。第三十七张，PPT共八十一页，创作于2022年6月38连续可微凸规划:Wolfe对偶：Wolfe对偶f、g可微凸，h线性1)：若原问题有解，则对偶问题也有解；2)：若原问题与对偶问题分别有可行解，则他们是最优解得充分必要条件是他们对应相同的目标值(对偶间隙为0).Lagrange函数Wolfe对偶定理：连续可微凸规划，满足

10、一约束规格，则第三十八张，PPT共八十一页，创作于2022年6月39凸规划对偶举例(Q正定)二次规划(Q正定)推广一：推广二：Lagrange对偶共轭对偶、广义Lagrange对偶参阅非线性规划及其理论 (应玖茜、魏权龄)第6章第三十九张，PPT共八十一页，创作于2022年6月罚函数法第四十张，PPT共八十一页，创作于2022年6月41惩罚函数法 将有约束优化问题转化为一系列无约束优化问题进行求解。（Sequential Unconstrained Minimization Technique - SUMT）1、算法思想：2、算法类型： 外点法（外惩法） 内点法（内惩法）3、问题：第四十一张，

11、PPT共八十一页，创作于2022年6月424、外点法（外部惩罚函数法）第四十二张，PPT共八十一页，创作于2022年6月43第四十三张，PPT共八十一页，创作于2022年6月44第四十四张，PPT共八十一页，创作于2022年6月45（1）几何解释第四十五张，PPT共八十一页，创作于2022年6月46（2）算法步骤（外点法）：第四十六张，PPT共八十一页，创作于2022年6月47yesNo（3）外点法框图第四十七张，PPT共八十一页，创作于2022年6月48（4）应注意的问题第四十八张，PPT共八十一页，创作于2022年6月49例: 第四十九张，PPT共八十一页，创作于2022年6月50参阅P2

12、07例2关于2个约束的例子!第五十张，PPT共八十一页，创作于2022年6月51 （5）一般模型的外点法 算法步骤相同第五十一张，PPT共八十一页，创作于2022年6月52(6)算法收敛性详见P202，引理8.1，定理8.2.详见P203， 定理8.4.第五十二张，PPT共八十一页，创作于2022年6月535、内点法（障碍函数法）（1）集合结构第五十三张，PPT共八十一页，创作于2022年6月54（2）算法思想 内点法（障碍函数法）的迭代点是在可行域点集内部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。 内点法

13、要求可行点集的内点集合非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。第五十四张，PPT共八十一页，创作于2022年6月55（3）算法分析第五十五张，PPT共八十一页，创作于2022年6月56第五十六张，PPT共八十一页，创作于2022年6月57（4）算法步骤（内点法）：第五十七张，PPT共八十一页，创作于2022年6月58内点法框图yesNo第五十八张，PPT共八十一页，创作于2022年6月59例解第五十九张，PPT共八十一页，创作于2022年6月60用对数罚函数会更简单其他例子见P217-218.第六十张，PPT共八十一页，创作于2022年6月61（5）算法收敛性

14、：（6）罚函数法的缺点第六十一张，PPT共八十一页，创作于2022年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点.第六十二张，PPT共八十一页，创作于2022年6月636. 乘

15、子法乘子罚函数:乘子罚函数与Langrange函数及惩罚函数的区别：多一项。 (1)等式约束第六十三张，PPT共八十一页，创作于2022年6月64乘子罚函数:第六十四张，PPT共八十一页，创作于2022年6月65(2)等式、不等式约束第六十五张，PPT共八十一页，创作于2022年6月66算法步骤（乘子罚函数法）：第六十六张，PPT共八十一页，创作于2022年6月67解：1. 惩罚函数法。对于惩罚函数例： 问题 的最优解为x* =(0.25, 0.75),分别用惩罚函数法和乘子法 求它的迭代点列。 可求得最优解为： 2. 乘子法。对于乘子罚函数可求得最优解为：第六十七张，PPT共八十一页，创作于

16、2022年6月68 从表中可见，xk*比 xk 近于x*的速度慢得多，用乘子法迭代6次就达到惩罚函数法迭代15次的效 这里，惩罚因子在惩罚函数法中要增大到u153276.8，而在乘子法中只要增大到u6=6.4 相比之下，乘子法不需过分地增大惩罚因子，确实比惩罚函数法有效很多. 第六十八张，PPT共八十一页，创作于2022年6月69Matlab求解约束非线性规划其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是约束向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。 第六十九张，PPT共八十一页，创作于2022年6月70函数 fmin

17、con格式 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,lam

18、bda = fmincon()x,fval,exitflag,output,lambda,grad = fmincon()x,fval,exitflag,output,lambda,grad,hessian = fmincon()第七十张，PPT共八十一页，创作于2022年6月71解: (1)写成标准形式：例1第七十一张，PPT共八十一页，创作于2022年6月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=

19、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第七十二张，PPT共八十一页，创作于2022年6月73解：约束条件的标准形式为（1）在MATLAB编辑器中建立非线性约束函数文件：function c, ceq=nlcon (x)c=(x(1)-1)2-x(2);ceq= ; %无等式约束第七十三张，PPT共八十一页，创作于2022年6月74（1）在MATLAB编辑器中建立非线性约束函数文件：

20、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) 第七十四张，PPT共八十一页，创作于2022年6月

21、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表

22、示约束有效。 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第七十五张，PPT共八十一页，创作于2022年6月76二次规划问题（quadratic programming）的Matlab解 第七十六张，PPT共八十一页，创作于2022年6月77函数 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,