非线性规划理论与算法

关于非线性规划理论与算法非线性规划及其最优性条件第2页,共81页，2024年2月25日，星期天3约束集或可行域:非线性规划x*是整体(全局)极小点x*是严格整体(全局)极小点x*是局部极小点x*是严格局部极小点非线性规划向量化表示p=q=0即无约束规划第3页,共81页，2024年2月25日，星期天4非线性规划的几个概念线性化可行方向:可行方向锥第4页,共81页，2024年2月25日，星期天5定义3:积极约束:或起作用约束（紧约束\积极约束\有效约束）。第5页,共81页，2024年2月25日，星期天6证明:定理1:定义4:可行下降方向第6页,共81页，2024年2月25日，星期天7定理2:定理3:证略③极值点的必要条件:第7页,共81页，2024年2月25日，星期天8严格凸组合严格凸线性组合为凸规划。若f(x)是凸函数，S是凸集，一般要求当i=1,2,…,p时为凸函数，当i=p+1,…,p+q时为线性函数。凸规划的局部解是整体解！第8页,共81页，2024年2月25日，星期天9第9页,共81页，2024年2月25日，星期天10定理：可微函数解的必要条件：x*是局部解,则：最优性条件无约束规划x*是驻点(稳定点)可微凸函数解的充要条件：x*是整体极小解当且仅当第10页,共81页，2024年2月25日，星期天11约束规划最优性条件的几何表述梯度共线第11页,共81页，2024年2月25日，星期天12共面

梯度被线性标示约束规划最优性条件的几何表述第12页,共81页，2024年2月25日，星期天13结论：在解处仅等式(紧)约束有效！约束规划最优性条件的几何表述第13页,共81页，2024年2月25日，星期天14对约束定义7.有效约束(紧约束、积极约束)——activeconstraint在x*处有则称在x*处ci(x)是紧约束。x*处有效约束指标集梯度的负线性表示!第14页,共81页，2024年2月25日，星期天15向量化表示约束规划最优性必要条件Karush-Kuhn-Tucker条件——KKT条件互补松弛条件第15页,共81页，2024年2月25日，星期天16Lagrange函数Karush-Kuhn-Tucker条件——KKT条件Lagrange乘子：互补松弛条件：约束规格——约束限制(规范)条件第16页,共81页，2024年2月25日，星期天17约束规划最优性充分条件鞍点条件同时的最优解！证明：由的任意性知:且进一步由不等式的后两部分知:第17页,共81页，2024年2月25日，星期天18凸规划最优性充要条件Karush-Kuhn-Tucker条件——KKT条件第18页,共81页，2024年2月25日，星期天19定理(FritzJohn条件):其他最优性条件第19页,共81页，2024年2月25日，星期天20FritzJohn条件与KKT条件的区别:FritzJohn条件可能出现w0=0的情形。这时FritzJohn条件中实际上不包含目标函数的任何数据，只是把起作用约束的梯度组合成零向量。这样的条件，对于问题的解的描述，没有多大价值。我们感兴趣的是w0≠0的情形，所以为了保证w0≠0，还需要对约束施加某种限制。这种限制条件通常称为约束规格。在上一个定理中，如果增加紧约束的梯度线性无关的约束规格，则给出问题的KKT条件。第20页,共81页，2024年2月25日，星期天211)所有规划解的最优性必要条件=KKT条件+约束规格2)凸规划解的最优性充分条件=KKT条件最优性条件总结最优性必要条件证明：需要用到凸集分离定理、择一性定理(Farkas引理凸规划最优性充分条件证明较简单，但对非凸规划结果没有实际指导意义，蕴含着对偶原理——Langrange对偶第21页,共81页，2024年2月25日，星期天22例:

求约束极值问题第22页,共81页，2024年2月25日，星期天23第23页,共81页，2024年2月25日，星期天24第24页,共81页，2024年2月25日，星期天25第25页,共81页，2024年2月25日，星期天26最优性条件举例线性规划最优性条件是充分的？是必要的？标准形式：练习：推广形式的最优性条件第26页,共81页，2024年2月25日，星期天27最优性条件举例二次规划最优性条件什么条件下是充分的？什么条件下是必要的？推广一：推广二：简化：第27页,共81页，2024年2月25日，星期天对偶理论第28页,共81页，2024年2月25日，星期天29最大最小对偶目标函数:x方的目标是无论y怎样，都应使F越小越好；y方的目标是无论x怎样，都应使F越大越好；立于不败之地的决策方法——保守主义决策相关结论：——一对对偶问题——弱对偶定理——对偶间隙第29页,共81页，2024年2月25日，星期天30最大最小对偶举例——博弈第30页,共81页，2024年2月25日，星期天31最大最小对偶鞍点条件:对相关结论：——弱对偶定理——对偶间隙若有点则称(x*,y*)满足鞍点条件。——强对偶定理满足鞍点条件。第31页,共81页，2024年2月25日，星期天32原规划:Lagrange对偶Lagrange函数Lagrange对偶弱对偶性:——弱对偶定理——对偶间隙原规划凹函数第32页,共81页，2024年2月25日，星期天33Lagrange对偶举例第33页,共81页，2024年2月25日，星期天34像集第34页,共81页，2024年2月25日，星期天35第35页,共81页，2024年2月25日，星期天36第36页,共81页，2024年2月25日，星期天37连续可微凸规划:强对偶定理：连续可微凸规划，满足一约束规格，则Lagrange对偶的强对偶定理f、g可微凸，h线性1)：若原问题有解，则对偶问题也有解；2)：若原问题与对偶问题分别有可行解，则他们是最优解的充分必要条件是他们对应相同的目标值(对偶间隙为0).证1)：即证可微凸规划的最优解与其KKT条件的乘子满足鞍点条件！证2)：利用鞍点条件可得。3)：对偶问题无上界，则原问题不可行；原问题无下界，则对偶问题不可行。第37页,共81页，2024年2月25日，星期天38连续可微凸规划:Wolfe对偶：Wolfe对偶f、g可微凸，h线性1)：若原问题有解，则对偶问题也有解；2)：若原问题与对偶问题分别有可行解，则他们是最优解得充分必要条件是他们对应相同的目标值(对偶间隙为0).Lagrange函数Wolfe对偶定理：连续可微凸规划，满足一约束规格，则第38页,共81页，2024年2月25日，星期天39凸规划对偶举例(Q正定)二次规划(Q正定)推广一：推广二：Lagrange对偶共轭对偶、广义Lagrange对偶——参阅《非线性规划及其理论》(应玖茜、魏权龄)第6章第39页,共81页，2024年2月25日，星期天罚函数法第40页,共81页，2024年2月25日，星期天41惩罚函数法将有约束优化问题转化为一系列无约束优化问题进行求解。（SequentialUnconstrainedMinimizationTechnique-SUMT）1、算法思想：2、算法类型：外点法（外惩法）内点法（内惩法）3、问题：第41页,共81页，2024年2月25日，星期天424、外点法（外部惩罚函数法）第42页,共81页，2024年2月25日，星期天43第43页,共81页，2024年2月25日，星期天44第44页,共81页，2024年2月25日，星期天45（1）几何解释第45页,共81页，2024年2月25日，星期天46（2）算法步骤（外点法）：第46页,共81页，2024年2月25日，星期天47yesNo（3）外点法框图第47页,共81页，2024年2月25日，星期天48（4）应注意的问题第48页,共81页，2024年2月25日，星期天49例:第49页,共81页，2024年2月25日，星期天50参阅P207——例2关于2个约束的例子!第50页,共81页，2024年2月25日，星期天51

（5）一般模型的外点法

算法步骤相同第51页,共81页，2024年2月25日，星期天52(6)算法收敛性详见P202，引理8.1，定理8.2.详见P203，定理8.4.第52页,共81页，2024年2月25日，星期天535、内点法（障碍函数法）（1）集合结构第53页,共81页，2024年2月25日，星期天54（2）算法思想

内点法（障碍函数法）的迭代点是在可行域点集内部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。

内点法要求可行点集的内点集合非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。第54页,共81页，2024年2月25日，星期天55（3）算法分析第55页,共81页，2024年2月25日，星期天56第56页,共81页，2024年2月25日，星期天57（4）算法步骤（内点法）：第57页,共81页，2024年2月25日，星期天58内点法框图yesNo第58页,共81页，2024年2月25日，星期天59例解第59页,共81页，2024年2月25日，星期天60用对数罚函数会更简单其他例子见P217-218.第60页,共81页，2024年2月25日，星期天61（5）算法收敛性：（6）罚函数法的缺点第61页,共81页，2024年2月25日，星期天62(7)内、外点法的优缺点的比较1.x(0)∈S0(参阅P220讨论内点的选取)2.等式约束不适用3.障碍函数B(x)在S0的可微阶数与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点.第62页,共81页，2024年2月25日，星期天636.乘子法乘子罚函数:乘子罚函数与Langrange函数及惩罚函数的区别：多一项。

(1)等式约束第63页,共81页，2024年2月25日，星期天64乘子罚函数:第64页,共81页，2024年2月25日，星期天65(2)等式、不等式约束第65页,共81页，2024年2月25日，星期天66算法步骤（乘子罚函数法）：第66页,共81页，2024年2月25日，星期天67解：1.惩罚函数法。对于惩罚函数例：问题的最优解为x*=(0.25,0.75),分别用惩罚函数法和乘子法求它的迭代点列。

可求得最优解为：

2.乘子法。对于乘子罚函数可求得最优解为：第67页,共81页，2024年2月25日，星期天68

从表中可见，xk*比xk近于x*的速度慢得多，用乘子法迭代6次就达到惩罚函数法迭代15次的效．这里，惩罚因子在惩罚函数法中要增大到u15＝3276.8，而在乘子法中只要增大到u6=6.4．相比之下，乘子法不需过分地增大惩罚因子，确实比惩罚函数法有效很多.第68页,共81页，2024年2月25日，星期天69Matlab求解约束非线性规划其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是约束向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。

第69页,共81页，2024年2月25日，星期天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(…)第70页,共81页，2024年2月25日，星期天71解:(1)写成标准形式：例1第71页,共81页，2024年2月25日，星期天72(2)先建立M-文件fun1.m:

functionf=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=[23;14];b=[6;5];Aeq=[];beq=[];LB=[0;0];UB=[];[x,fval]=fmincon('fun1',x0,A,b,Aeq,beq,LB,UB)(4)在命令窗口中输入youh1,得运算结果为：

x=0.76471.0588fval=-2.0294第72页,共81页，2024年2月25日，星期天73解：约束条件的标准形式为（1）在MATLAB编辑器中建立非线性约束函数文件：function[c,ceq]=nlcon(x)c=(x(1)-1)^2-x(2);ceq=[];%无等式约束第73页,共81页，2024年2月25日，星期天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=[01];A=[-23];%线性不等式约束b=6;Aeq=[];%无线性等式约束beq=[];lb=[];%x没有下、上界ub=[];[x,fval,exitflag,output,lambda,grad,hessian]=fmincon(fun2,x0,A,b,Aeq,beq,lb,ub,@nlcon)

第74页,共81页，2024年2月25日，星期天75则结果为x=34fval=-13exitflag=%解收敛

1output=iterations:2funcCount:9stepsize:1algorithm:'medium-scale:SQP,Quasi-Newton,line-search'firstorderopt:[]cgiterations:[]lambda=lower:[2x1double]%x下界有效情况，通过lambda.lower可查看。

upper:[2x1double]%x上界有效情况，为0表示约束无效。

eqlin:[0x1double]%线性等式约束有效情况，不为0表示约束有效。

eqnonlin:[0x1double]%非线性等式约束有效情况。

ineqlin:2.5081e-008%线性不等式约束有效情况。

ineqnonlin:6.1938e-008%非线性不等式约束有效情况。grad=%目标函数在最小值点的梯度

1.0e-006*-0.17760hessian=%目标函数在最小值点的Hessian值

1.0000-0.0000-0.00001.0000第75页,共81页，2024年2月25日，星期天76二次规划问题（quadraticprogramming）的Matlab解

第76页,共81页，2024年2月25日，星期天77函数

quadprogx=quadprog(H,f,A,b,Aeq,beq,lb,ub)%lb,ub分别为为x的下上界。x=quadprog(H,f,A,b,Aeq