非线性规划LP)的解法 可行方向法、罚函数法、梯度投影法 min d 'Gd+v(x,)'d 逐步二次规划法( Sequential Quadratic Programming) 题 s1. Vh(x,d+h(x n f(x) vg,(x,)d+g,(x)≤0,j=1…1 SQP的基本原理 x是第k次选代的初始点,G是海赛阵VL的近似 构造LNP的拉格朗日函数 gj(x)≤0,j=1 将最优解d作为选代的搜索方向,令x+1=X+akd L(x,,A)=f(x)+2h(x)+∑g,(x) SOP的·求解QP子问题,得d; 用二次函数近似L(x,A)NLP化为QP 基本步骤·用线性搜索计算迭代步长a 再解一系列QP子问题 ·确定矩阵G的迭代公式 min ==f(r) MATLAB求解 =f(x) MATLAB求解s.c1(x)≤0,c2(x)=0, 约束MLP s1.c1(x)≤0,c2(x)=0, 约束MLP A1x≤b1,A2x=b2,V1≤x≤V2 A1x≤h,A2x=b2,n≤x≤v2 alcon.m给出约束, Gradconstr='on时还给出梯度,形式为 Ix, fval, exitflag, output, lambda, grad, hessian] function [cl, c2, GCl, GC2]= alcon(x) rincon(@fun, xO, Al, bl, A 2, b2, vl, v2, @nIcon, options, Pl, P2,. 8 nonlinear inequalities at x fun.m给出函数f,当 Gradobj='on’时必须给出f的梯度 8 nonlinear equalities at x Hessian='on’时还必须给出其 Jacobi矩阵,形式为 if nargout 2 =.. 8 gradients of cl function [f, g, H] fun(x) s gradients of c2 8 objective function value if nargout >1 2x2+1) x2-x2+1.5≤0,xx2+1020 x2+x2-1=0 Exam0s04, m (学学奖 大学费学买验 实例3:供应与选址三 实例3:供应与选址 决策变量tc 分之x-a)2+(-4)32 运量)-12维4∑-4,1=1.6 S之9xy-a2+-)}2改建两个新料场 决策变量 cy=d,i=1-6 c,(xy)-16维 线性规划模型 Shili0803. m: 用例中数 cy se, j=1,2 据计算 c,(料场A) 初始点的选择 最优解为c。(料场B) 用现料场总吨公里数为1362 局部最优解问题 总吨公里数为1362 Shilioso3linn 结果:总吨公里数为853,比使用原料场减少了50.97 非线性规划(NLP)的解法 可行方向法、罚函数法、梯度投影法... 逐步二次规划法(Sequential Quadratic Programming) SQP的基本原理 构造LNP的拉格朗日函数 ( , , ) ( ) ( ) ( ) 1 1 L x f x h x g x j l j j m i ∑ i i ∑ = = µ λ = + µ + λ g x j l s t h x i m f x j i x n ( ) 0, 1,..., . . ( ) 0, 1,..., min ( ) ≤ = = = ∈ℜ 用二次函数近似 L(x,µ,λ), NLP化为QP, 再解一系列QP子问题。 QP子 问题 g x d g x j l st h x d h x i m d G d f x d j k T j k i k T i k T k k T L L ( ) ( ) 0, 1, . . ( ) ( ) 0, 1, ( ) 2 1 min ∇ + ≤ = ∇ + = = + ∇ k x 是第k 次迭代的初始点，Gk 是海赛阵 L 2 ∇ 的近似。 • 求解QP子问题，得 dk； 将最优解dk作为迭代的搜索方向，令 k k k k x = x +α d +1 SQP的 基本步骤 • 确定矩阵Gk的迭代公式。 • 用线性搜索计算迭代步长αk； MATLAB求解 约束NLP [x,fval,exitflag,output,lambda,grad,hessian] = fmincon(@fun,x0,A1,b1,A2,b2,v1,v2,@nlcon,options,P1,P2, ...) fun.m给出函数f，当GradObj=‘on’时必须给出f的梯度， Hessian=‘on’时还必须给出其Jacobi矩阵，形式为 1 1 2 2 1 2 1 2 , , . . ( ) 0, ( ) 0, min ( ) A x b A x b v x v s t c x c x z f x ≤ = ≤ ≤ ≤ = = function [f,g,H] = fun(x) f = ... % objective function value if nargout > 1 g = ... % gradient of the function if nargout > 2 H = ... % Hessian end nlcon.m给出约束,GradConstr=‘on’时还给出梯度,形式为 1 1 2 2 1 2 1 2 , , . . ( ) 0, ( ) 0, min ( ) A x b A x b v x v s t c x c x z f x ≤ = ≤ ≤ ≤ = = function [c1,c2,GC1,GC2] = nlcon(x) c1 = ... % nonlinear inequalities at x c2 = ... % nonlinear equalities at x if nargout > 2 GC1 = ... % gradients of c1 GC2 = ... % gradients of c2 end MATLAB求解 约束NLP 例4 Exam0804.m min (4 2 4 2 1) 1 2 2 2 2 2 1 1 e x + x + x x + x + x 1.5 0, 10 0 x1 x2 − x1 − x2 + ≤ x1 x2 + ≥ 1 0 2 2 x1 + x − = 用例中数 据计算， 最优解为 i 123456 i1 c （料场 A） 350701 i 2 c （料场 B） 0 0 4 0 6 10 总吨公里数为136.2 , 1,2 . . , 1,...,6 min [( ) ( ) ] 6 1 2 1 2 1 6 1 2 2 1/ 2 ≤ = = = − + − ∑ ∑ ∑∑ = = = = c e j s t c d i c x a y b ij j i ij i j j i ij j i j i 线性规划模型 决策变量：ci j (料场j到工地i的 运量）~12维 Shili0803lin.m 实例3: 供应与选址 结果：总吨公里数为85.3，比使用原料场减少了50.9。 初始点的选择 实例3: 供应与选址 , 1,2 . . , 1,...,6 min [( ) ( ) ] 6 1 2 1 2 1 6 1 2 2 1/ 2 ≤ = = = − + − ∑ ∑ ∑∑ = = = = c e j st c d i c x a y b ij j i ij i j j i ij j i j i 决策变量： ci j，(xj ,yj )~16维 用现料场总吨公里数为136.2 改建两个新料场 局部最优解问题 Shili0803.m; shili083fun.m