非线性规划理论与算法

关于非线性规划理论与算法第一页，共八十一页，编辑于2023年，星期四非线性规划及其最优性条件第二页，共八十一页，编辑于2023年，星期四3约束集或可行域:非线性规划x*是整体(全局)极小点x*是严格整体(全局)极小点x*是局部极小点x*是严格局部极小点非线性规划向量化表示p=q=0即无约束规划第三页，共八十一页，编辑于2023年，星期四4非线性规划的几个概念线性化可行方向:可行方向锥第四页，共八十一页，编辑于2023年，星期四5定义3:积极约束:或起作用约束（紧约束\积极约束\有效约束）。第五页，共八十一页，编辑于2023年，星期四6证明:定理1:定义4:可行下降方向第六页，共八十一页，编辑于2023年，星期四7定理2:定理3:证略③极值点的必要条件:第七页，共八十一页，编辑于2023年，星期四8严格凸组合严格凸线性组合为凸规划。若f(x)是凸函数，S是凸集，一般要求当i=1,2,…,p时为凸函数，当i=p+1,…,p+q时为线性函数。凸规划的局部解是整体解！第八页，共八十一页，编辑于2023年，星期四9第九页，共八十一页，编辑于2023年，星期四10定理：可微函数解的必要条件：x*是局部解,则：最优性条件无约束规划x*是驻点(稳定点)可微凸函数解的充要条件：x*是整体极小解当且仅当第十页，共八十一页，编辑于2023年，星期四11约束规划最优性条件的几何表述梯度共线第十一页，共八十一页，编辑于2023年，星期四12共面梯度被线性标示约束规划最优性条件的几何表述第十二页，共八十一页，编辑于2023年，星期四13结论：在解处仅等式(紧)约束有效！约束规划最优性条件的几何表述第十三页，共八十一页，编辑于2023年，星期四14对约束定义7.有效约束(紧约束、积极约束)——activeconstraint在x*处有则称在x*处ci(x)是紧约束。x*处有效约束指标集梯度的负线性表示!第十四页，共八十一页，编辑于2023年，星期四15向量化表示约束规划最优性必要条件Karush-Kuhn-Tucker条件——KKT条件互补松弛条件第十五页，共八十一页，编辑于2023年，星期四16Lagrange函数Karush-Kuhn-Tucker条件——KKT条件Lagrange乘子：互补松弛条件：约束规格——约束限制(规范)条件第十六页，共八十一页，编辑于2023年，星期四17约束规划最优性充分条件鞍点条件同时的最优解！证明：由的任意性知:且进一步由不等式的后两部分知:第十七页，共八十一页，编辑于2023年，星期四18凸规划最优性充要条件Karush-Kuhn-Tucker条件——KKT条件第十八页，共八十一页，编辑于2023年，星期四19定理(FritzJohn条件):其他最优性条件第十九页，共八十一页，编辑于2023年，星期四20FritzJohn条件与KKT条件的区别:FritzJohn条件可能出现w0=0的情形。这时FritzJohn条件中实际上不包含目标函数的任何数据，只是把起作用约束的梯度组合成零向量。这样的条件，对于问题的解的描述，没有多大价值。我们感兴趣的是w0≠0的情形，所以为了保证w0≠0，还需要对约束施加某种限制。这种限制条件通常称为约束规格。在上一个定理中，如果增加紧约束的梯度线性无关的约束规格，则给出问题的KKT条件。第二十页，共八十一页，编辑于2023年，星期四211)所有规划解的最优性必要条件=KKT条件+约束规格2)凸规划解的最优性充分条件=KKT条件最优性条件总结最优性必要条件证明：需要用到凸集分离定理、择一性定理(Farkas引理凸规划最优性充分条件证明较简单，但对非凸规划结果没有实际指导意义，蕴含着对偶原理——Langrange对偶第二十一页，共八十一页，编辑于2023年，星期四22例:

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

（5）一般模型的外点法

算法步骤相同第五十一页，共八十一页，编辑于2023年，星期四52(6)算法收敛性详见P202，引理8.1，定理8.2.详见P203，定理8.4.第五十二页，共八十一页，编辑于2023年，星期四535、内点法（障碍函数法）（1）集合结构第五十三页，共八十一页，编辑于2023年，星期四54（2）算法思想

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

内点法要求可行点集的内点集合非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。第五十四页，共八十一页，编辑于2023年，星期四55（3）算法分析第五十五页，共八十一页，编辑于2023年，星期四56第五十六页，共八十一页，编辑于2023年，星期四57（4）算法步骤（内点法）：第五十七页，共八十一页，编辑于2023年，星期四58内点法框图yesNo第五十八页，共八十一页，编辑于2023年，星期四59例解第五十九页，共八十一页，编辑于2023年，星期四60用对数罚函数会更简单其他例子见P217-218.第六十页，共八十一页，编辑于2023年，星期四61（5）算法收敛性：（6）罚函数法的缺点第六十一页，共八十一页，编辑于2023年，星期四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点.第六十二页，共八十一页，编辑于2023年，星期四636.乘子法乘子罚函数:乘子罚函数与Langrange函数及惩罚函数的区别：多一项。

(1)等式约束第六十三页，共八十一页，编辑于2023年，星期四64乘子罚函数:第六十四页，共八十一页，编辑于2023年，星期四65(2)等式、不等式约束第六十五页，共八十一页，编辑于2023年，星期四66算法步骤（乘子罚函数法）：第六十六页，共八十一页，编辑于2023年，星期四67解：1.惩罚函数法。对于惩罚函数例：问题的最优解为x*=(0.25,0.75),分别用惩罚函数法和乘子法求它的迭代点列。

可求得最优解为：

2.乘子法。对于乘子罚函数可求得最优解为：第六十七页，共八十一页，编辑于2023年，星期四68

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

第六十九页，共八十一页，编辑于2023年，星期四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(…)第七十页，共八十一页，编辑于2023年，星期四71解:(1)写成标准形式：例1第七十一页，共八十一页，编辑于2023年，星期四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第七十二页，共八十一页，编辑于2023年，星期四73解：约束条件的标准形式为（1）在MATLAB编辑器中建立非线性约束函数文件：function[c,ceq]=nlcon(x)c=(x(1)-1)^2-x(2);ceq=[];%无等式约束第七十三页，共八十一页，编辑于2023年，星期四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)

第七十四页，共八十一页，编辑于2023年，星期四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第七十五页，共八十一页，编辑于2023年，星期四76二次规划问题（quadraticprogramming）的Matlab解

第七十六页，共八十一页，编辑于2023年，星期四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=qua