二次规划子问题的一种非精确光滑牛顿法.pdf

第44卷第2期2023年6月淮北师范大学学报（自然科学版）Journal of Huaibei Normal University(Natural Sciences)Vol.44 No.2Jun.2023二次规划子问题的一种非精确光滑牛顿法朱子旋，芮绍平，蔡玉玉（淮北师范大学 数学科学学院，安徽 淮北 235000）摘要：二次规划子问题的求解是解决规划问题的关键。针对二次规划子问题，利用最优性条件，借助光滑逼近函数将其转化为光滑方程组，结合非精确牛顿法得到一种求解二次规划子问题的非精确光滑牛顿法。一定条件下证明其全局收敛性。数值实验表明此算法对二次规划子问题有效。关键词：二次规划子问题；全局收敛性；非精确牛顿法中图分类号：O 221.2文献标识码：A文章编号：2095-0691（2023）02-0021-050引言非线性规划1-2是指在目标函数或者约束条件里包含非线性函数的一类规划问题，是最优化中一个重要分支。上世纪五十年代，由Kuhn-Tucker提出关于非线性规划问题的最优性条件3-4，为非线性规划问题的求解提供基础。非线性规划问题如下：minf(x),s.t.gi(x)0,i=1,2,m,hj(x)=0,j=1,2,l。（1）其中f:RnR,xRn,g:RnRm,h:RnRl连续且可微。相较于线性规划问题来说，求解非线性规划问题难度较大，许多学者进行研究1-5，其中序列二次规划（Sequential Quadratic Programming，简记为SQP）方法5-6是求解非线性规划问题的有效方法之一，在SQP方法中，一般都需要求解一个二次规划子问题来确定当前迭代点xk的校正步长dk，从而产生一个可行的下降方向，所谓二次规划子问题：min12dTBkd+f(xk)Td,s.t.h(xk)+AEkd=0,g(xk)+AIkd0。（2）其中:d是二次规划子问题的解,Bk为对称正定矩阵,AEk=h(xk)T,AIk=g(xk)T,E=1,2,l,I=1,2,m。对于二次规划子问题（2）的求解，常见求解方法包括精确光滑牛顿法7、滤子SQP法8、可行方向法9、内点法10等，但这些方法都存在一些局限性，限制适用范围。利用非精确牛顿法11-12进行研究，简化传统求解方法，效率更高更适合大范围推广。本文提出的求解二次规划子问题的非精确光滑牛顿法，将二次规划子问题通过最优性条件（Kuhn-Tucher条件，简记为KT），借助一个光滑逼近函数，将其转化成为光滑方程组，结合非精确牛顿法求解该方程组，进而求解二次规划子问题。收稿日期：2022-10-26基金项目：安徽省高等学校自然科学研究项目（KJ2020A0024）；淮北师范大学实验室开放项目（2022sykf016）作者简介：朱子旋（1997），女，安徽淮北人，硕士生，研究方向为优化理论算法与应用。通信作者：芮绍平（1978），男，安徽潜山人，博士，教授，研究方向为优化理论算法与应用。淮北师范大学学报（自然科学版）2023年1基础知识记非线性规划问题（1）的可行域为:=xRn|gi(x)0,i=1,2,m,hj(x)=0,j=1,2,l，且问题（1）的Lagrange函数L0:Rn+m+l-,+),L0:=L0(x,),=f(x)+i=1migi(x)+j=1lihi(x),0,-,0时是强半光滑的，并且在(),a,b R+RnRn是连续可微的，且其雅可比矩阵为：(,a,b)=ab=(cos-sin)(a+b)-(acos+bsin)(bcos-asin)+(asin+bcos)(acos-bsin)+2(acos+bsin)2+(asin+bcos)2+22(cos+sin)-(acos+bsin)cos+(asin+bcos)sin(acos+bsin)2+(asin+bcos)2+22(cos+sin)-(acos+bsin)sin+(asin+bcos)cos(acos+bsin)2+(asin+bcos)2+22。（7）令:=(,d)R+RmRlRn，S():=S(,d)=H1(d,)H2(d,)1(,d,)=0。（8）其中1:=1(,d)=1(,d,)2(,d,)m(,d,),i(,d,)=(cos+sin)(gi(xk)+(AIk)id+i)-(gi(xk)+(AIk)id)cos+isin2+(gi(xk)+(AIk)id)sin+icos2+22,xk=(xk1,xk2,xkn)T，k=(k1,k2,kl)T，k=(k1,k2,km)T,22第2期朱子旋等：二次规划子问题的一种非精确光滑牛顿法Sk:=S(k)=S(k,k,k,dk)。于是，通过FB光滑函数，求解子问题（2）就转化成求解与之等价的方程组（8）。当0时，S()是连续可微的，且其Jacobian矩阵为S()=10000Bk-(AEk)T-(AIk)T0AEk00D2(z)AIk0D1(z)RN1N1，（9）其中：N1=1+l+m+n。Bk为Hesse矩阵，v=(v1,L,vm)T=(,d,),vi由下式确定vi=(cos-sin)i+(gi(xk)+(AIk)id)-T1(gi(xk)+(AIk)id)cos-isin)+T2(icos-(gi(xk)+(AIk)id)sin)+2(T1)2+(T2)2+22,T1=(icos+(gi(xk)+(AIk)id)sin)，T2=(isin+(gi(xk)+(AIk)id)cos),其中D1(z),D2(z)为对角元素是ai(z),bi(z)的对角阵，ai(z),bi(z)由下式确定：bi(z)=(cos+sin)-T2cos+T1sin(T1)2+(T2)2+22,ai(z)=(cos+sin)-T1cos+T2sin(T1)2+(T2)2+22。2非精确光滑牛顿算法及收敛性基于以上等价转换方法，给出求解二次规划子问题的非精确光滑牛顿法。算法1（二次规划子问题的非精确光滑牛顿法）步骤 0选取常数(0,1)，(0,1)，(0,1)。定义函数():=S()min1,S()使得00，得到以下解:=(,d)R+RmRlRn时。可证线性方程组S()=0（12）23淮北师范大学学报（自然科学版）2023年只有零解，即证=0,=0,=0,d=0。由方程（10）和方程（11）可得：=0,(AEk)T=0,AIk+Bkd=0。（13）对于矩阵M=ID2(z)(AIk)T-(AIk)TBk，由于Bk是对称正定的且(AIk)T是行满秩的，易证明矩阵M是非奇异的。同时由于(AEk)T是行满秩的，于是=0,=0,d=0,故=(,d)=(0,0,0,0)，可以得到矩阵S()是非奇异的。算法1中的步骤2和步骤3的适定性证明与参考文献 7 中类似，不再赘述。定理37设函数S()是二次连续可微的，并且 k为算法1所产生的迭代点列，*=(*,*,*,d*)为迭代序列的一个聚点。如果二次规划子问题的解集是非空有界的，则（1）S(k)是一个单调下降的序列且收敛到零；（2）limkk=0，且序列S(k)有界；（3）迭代序列 k的每一个聚点都是二次规划子问题的一个解。证明定理证明与文献 7 中定理2证明类似，不再赘述。3数值实验针子问题（2），为验证算法1具的有效性，在Matlab 9.0环境下进行仿真编程，本节在极小点给出的情况下求取最优解，比较最优解与极小点的一致程度，并给出算法1的数据实验结果。所求算例的实验结果均列在表1和表2中，其中d和val分别代表最优解和最优值，,为乘子向量，k是迭代次数，xi*代表算例i的极小点，EmptyMatrix用#代表。用NSM,INSM分别代表光滑牛顿法和非精确光滑牛顿法。通过数据实验进行比较迭代次数k和CPU时间，数值越小说明实验效果越好。CPU时间为多次测试的平均结果，单位为秒（s）。在算法的测试中参数具体取值为：=0.05，=0.2，=0.5，0=0.05，停机标准是S(w)10-6。测试函数均来自于文献 6，如下：算例1min f(x)=x21+2x22+x1x2-6x1-2x2-12x3,s.t.x1+x2+x3-4-2=0,x1-2x2+30,x1,x2,x30。算例2min f(x)=x21+2x22+x23-2x1x2+x3,s.t.x1+x2+x3=4,2x1-x2+x3=2。算例3min f(x)(x1-2)2+x22,s.t.-x1+x2=0,x1-x220。从表1和表2所给出的数据实验结果可以看出，非精确牛顿法求解子问题（2）稳定可靠，所需迭代次数k和CPU运算时间都相对较少，非精确光滑牛顿法（INSM）所需的计算成本较低于光滑牛顿法（NSM），并且拥有良好的收敛速度。数值实验说明非精确牛顿法是求解二次规划子问题的一种较好的方法。表1算例数值实验结果极小点x1*=(0,0,2)Tx2*=(2111,4322,322)Tx3*=(0,1)Td(0.000,0.000,2.000)T(1.909,1.954,0.136)T(0.000,1.000)T(0,4,8,0)T#()0,1,0,0T12.000()2.636,-1.363T#24第2期朱子旋等：二次规划子问题的一种非精确光滑牛顿法表2算例数值实验结果算例1算例2算例3NSMk638CPU0.005 30.067 20.058 5val-24.0003.9770.500INSMk627CPU0.003 40.033 80.035 1val-24.00 03.9770.5004结语对于求解二次规划子问题，采用光滑技术与非精确牛顿法相结合，有效克服过度求解情况并且降低计算成本，配有线搜索技术满足了算法的全局收敛性的需求。通过初步的数值实验表明，非精确光滑牛顿法提高了针对求解二次规划子问题的速度并且保持了较好的稳健性，此方法是有效可行的。参考文献：1GROSAN C，ABRAHAM A.A new approach for solving nonlinear equations systems J.IEEE Transactions on Systems，2008，38（3）：698-714.2MICHAILIDIS I，BALDI S，KOSMATOPOULOS E B，et al.Adaptive optimal control for large-scale nonlinear systems J.IEEE Transactions on Automatic Control，2017，62（11）：5567-5577.3苏孟龙，赵立芹，吕显瑞.组合极大熵同伦方法求解一类非凸非线性规划问题的K-K-T点 J.吉林大学学报（理学版），2006，44（5）：710-714.4FRENCH M.General conditions for solving optimization problems：karush-kuhn-tucker conditions M.West Lafayette:Springer，2018：143-157.5LEE J H，JUNG Y M，YUAN Y，et al.A subspace SQP method for equality constrained optimization J.Computational Optimization and Applications，2019，74（1）：177-194.6马昌凤.最优化计算方法及其Matlab程序实现 M.北京：科学出版社，2010：180-202.7谢亚君，马昌凤.求解非线性规划问题的光滑牛顿法 J.福建师范大学学报（自然科学版），2011，27（5）：17-22.8刘美玲.带等式约束二次规划子问题的滤子SQP算法 J.数学的实践与认识，2015，45（14）：272-279.9ZHU Zhibin.An efficient sequential quadratic programming algorithm for nonlinear programming J.Journal of Computational and Applied Mathematics，2005，175（2）：447-464.10ARIAS C A，MARTNEZ H J，PREZ R.Global inexact quasi-Newton method for a nonlinear system of equations withconstraints J.Applied Numerical Mathematics，2020，150：559-575.11MEZZADRI F，GALLIGANI E.An inexact Newton method for solving complementarity problems in hydrodynamic lubrication J.Calcolo，2018，55（1）：1-28.12NEJDAWI I M，CLEMENTS K A，DAVIS P W.An efficient interior point method for sequential quadratic programmingbased optimal power flow J.IEEE Transactions on Power Systems，2000，15（4）：1179-1183.13林贵华.非线性最优化基础 M.北京：科学出版社，2011：95-98.14韩继业，修乃华，戚厚铎.非线性互补理论与方法 M.上海：上海科学出版社，2006：48-72.15TANG Jingyong，HE Guoping，LI Dong.A new one-step smoothing newton method for second-order cone programmingJ.Applications of Mathematics，2012，57（4）：311-331.An Inexact Smoothing Newton Method forQuadratic Programming SubproblemZHU Zixuan，RUI Shaoping，CAI Yuyu（School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China）Abstract：The solution of the quadratic programming sub problem is the key to solving the planning problem.In this paper，an inexact smooth Newton method for solving the quadratic programming sub problem is obtained by transforming it into a smooth system of equations with the help of smooth approximation functionsusing optimality conditions and combining it with an inexact Newton method.Its global convergence is provedunder certain conditions.Numerical experiments show that this algorithm is effective for quadratic programming sub problems.Key words：quadratic programming sub problem；global convergence；inexact Newton method25