序贯二次规划-西安交通大学

LOGO5.4序贯二次规划（SQP）法化工学院*********Companyname序贯二次规划（SQP）法1.SQP法简介2.二次规划的求解3.一维搜索4.矩阵Qk的校正5.化工中的应用实例Companyname1.SQP法简介SQP法(又称WHP算法）的基本思想是:在某个近似解xk处,将原非线性规划问题(式(5-1))化成如下的规划问题:目标函数是二次的约束条件是二次的min()..()0(1,2,,)()0(1,2,,)ijfx(5-1a)stgxim(5-1b)hxjl(5-1c)LL1min()2..()()0(1,2,,)()()0(1,2,,TTkKTKiiKTKjifxx+xQxstgxxgxim(5-34)hxxhxjLL)l1.SQP法简介Companyname2111nKKKKixx=xx1.1SQP法简介--只有等式约束Companyname,:min()..()0(,,,)()T12lTSQPfx(5-35)sthxhxhxhxhx535fx为了加深对法基本思想的理解以下对只有等式约束的非线性规划问题做一说明。考虑非线性规划问题式中。问题式的最优性必要条件为00hxhx或记作1.1SQP法简介--只有等式约束()()0()()0()()0()0()0()0ljijlljijljnijnnnnnllhxfxExxhxfxExxhxfxExxEhxEhxEhxMM这是一个n+l个方程和n+l个变量的非线性方程组。若有解存在,则可得到惟一解x*,且满足原问题最优解的必要条件。1.1SQP法简介--只有等式约束(,),,: 0kkkkTkkkknnnnlkkkTkkxQ(J)xxE(x)5-37J0E=EEEEEEf(x)+Qx(J)Jx+h(x)LLT若已知某一近似点则根据牛顿法解非线性方程组的思想应有以下迭代公式（）式中（，，，，，，,)，等价于111121(,,,)(Tk1kkk12n=0(5-38)xxxx,,,L这是一个以和)为变量的线性方程组。牛顿迭代求解1.1SQP法简介--只有等式约束,(,),1min()2..()()0kkTTkKTK534xfxx+xQxsthxxhx(5-39)Lagrange按照式的模式在某一近似点处其二次规划问题的形式为其函112TTTkkkkTL=f(x)x+xQx-h(x)h(x)x数为SQP法求解1min()2..()()0(1,2,,)()()0(1,2,,TTkKTKiiKTKjifxx+xQxstgxxgxim(5-34)hxxhxjLL)l1.1SQP法简介--只有等式约束(x)+Qxh(x)dxdLh(x)+h(x)x=0(5-40)d10kkkTkkf(x)+Qx(J)Jx+h(x)=0(5-38)牛顿迭代法1.2SQP法简介—非等式约束Companyname上述思想推广到含有不等式约束非线性规划的一般情形也是正确的。然而,在WHP算法中,并不直接取x作为新的近似点,往往以Δx作为一个搜索方向,通过一维搜索求步长α来确定下一个迭代点,即另外,在WHP算法中,类似于无约束最优化方法中的变尺度法,式(5-34)中的矩阵Qk不直接取广义Lagrange函数的二阶偏导数矩阵。通常取Q0=I(单位矩阵),以后各次计算按一定的格式进行修正。1kkx=xx1.3SQP法计算步骤Companyname将非线性规划问题转化为二次规划问题(式(5-34));3对该二次规划问题进行迭代求解;120,,,TTTn12Tn12minf(x)=Cx+xQx(5-41a)s.t.Axb(5-41b)x(5-41c)x=xxxC=(c,c,,c)b二次规划问题的一般形式为其中Tm1211121n11121n21222n21222nnnnnn1n2n1n2n?nn?n=(b,b,,b)qq,,qaa,,aqq,,qaa,,aQ=A=qq,,qaa,,aMMMMMMMM2.二次规划的求解Companyname22221,2,...,1,2,...,,121,2,...,0ijTTTiiijj541bsim541cjnminf(x)=Cx+xQx5-42as.t.Axsbim5-42bx对式可引进松弛变量或式引进剩余变量t则该二次问题可以写成t121,2,...,,,...,,iiniijnaaa其中A2.二次规划的求解--Lagrange乘子技术Companyname2211112:01,2,...,201,2,.mnTTTiiiijijijnjiijjjjiijLagrangeL(x,s,t,,)=Cx+xQx+Axsbx5-43LLcajn5-44xLsis这样函数就可以写成t函数的稳定点的必要条件22..,201,2,...,01,2,...,01,2,...,jjjTiiijjjjm5-45Ltjn5-46tLAxsbim5-47Lxjn5-48t2.二次规划的求解--Lagrange乘子技术Companyname222:1,2,...,01,2,...,20iiiTiiijTiiiiijiijyysim5-49LAxsb547Ab=-s=yim5-50Lstss定义一组新的变量则方程可以写成以和分别乘式2220,01,2,...,01,2,...,jjjiiiijj545Lt546tsyim5-51=jn5-52和式可得和t2.二次规划的求解--Lagrange乘子技术Companyname2222000TiiiiiiiiijjjjAb=-s=y5-50sy5-51Lx5-48=5-52tt01,2,...,01,2,...,TiiijjAbim5-53xjn5-541101,2,...,1,2,...,01,2,...,nnjjijiijijiTiiijLcdxajn5-55Abyim5-56xjn这样函数稳定点的必要条件可归纳为01,2,...,01,2,...,01,2,...,iij5-57yim5-58im5-59jn01,2,...,01,2,...,iijj5-60yim5-61xjn5-62和2.二次规划的求解--Lagrange乘子技术Companyname个线性方程组得到2.二次规划的求解--Lagrange乘子技术Companyname1101,2,...,1,2,...,01,2,...,nnjjijiijijiTiiijLcdxajn5-55Abyim5-56xjn5-57y函数稳定点的必要条件为01,2,...,01,2,...,01,2,...,iijim5-58im5-59jn01,2,...,01,2,...,iijj5-60yim5-61xjn5-62和2（m+n)个变量和2（m+n)个方程，所以解是唯一的。Q是正定矩阵，因此f(x)一定是一个严格的凸函数，而其可行域是一个凸集（因是线性函数），因而其局部最小也必定是全局最小。此解必定是原二次规划的最优解2.二次规划的求解--Lagrange乘子技术线性方程组的求解--线性规划单纯形二步法的第一步。惟一的约束限制是式(5-61)和式(5-62)必须随时满足。由于此处只是求方程组(5-55)到式(5-62)的一个可行解,这一可行解必定是原二次规划的最优解,因此没有必要继续进行第二步的计算。Companyname11111,01,2,...,,min..01,2,...,jnnjjijiijijjinjjnnjjijiijijjiTiji555nz555cqxazjn5-63Fzstcqxazjn5-64Axybi在式中引入个非负的人工变量到方程中则有这样第一步模型为1,2,...,0,0,0,0mxy2.二次规划的求解--Lagrange乘子技术Companyname，当决定是否将引入到基础解中的时候必须注意如下附加条件:首先保证不在基础解中或者当引入时将从该基础解中换出。关于也要注意相同的问题，以下举一个具体的例子。2.二次规划的求解—例题Companyname二次规划的求解—例题Companyname二次规划的求解—例题根据式(5-55)到式(5-62),该问题的必要条件为-4-λ1+2x1-2x2+2μ1+μ2=00-λ2-2x1+4x2+μ1-4μ2=02x1+x2-6=-y1x1-4x2-0=-y2x1≥0,x2≥0,y1≥0,y2≥0,μ1≥0,μ2≥0,λ1≥0,λ2≥0和μ1y1=0,λ1x1=0，μ2y2=0,λ2x2=0Companyname110000nnjjijiijijiTiiijiicdxa5-55Aby5-56x5-57y5-58000jiijj5-595-60y5-61x5-62和2.二次规划的求解—例题这样,单纯形二步法的第一步模型为minF=z1+z2s.t2x1-2x2+2μ1-λ1+z1=4-2x1+4x2+μ1-4μ2-λ2+z2=02x1+x2+y1=6x1-4x2+y2=0x1≥0,x2≥0,y1≥0