关于非线性鞍点问题的一个新的非线性不精确Uzawa算法.pdf

应用数学MATHEMATICA APPLICATA2024,37(2):489-495关于非线性鞍点问题的一个新的非线性不精确Uzawa算法豆铨煜,耿宏瑞,关宏波(郑州轻工业大学数学与信息科学学院,河南 郑州 450002)摘要：本文针对非线性鞍点问题,借助于一个非线性映射,构造了一个新的非线性不精确Uzawa算法,该算法避免了传统Uzawa方法所必需的求逆运算.并通过精细分析得到了该算法在能量范数意义下收敛的充分条件,最后给出的数值实验验证了该方法的有效性.关键词：非线性鞍点问题;非线性不精确Uzawa算法;收敛性分析中图分类号：O241AMS(2010)主题分类：65F10;65N22文献标识码：A文章编号：1001-9847(2024)02-0489-071.引言本文考虑如下非线性鞍点问题:H(x,y)=F(x)+BTy fBx Cy g=0,(1.1)其中B是一个m n的行满秩的矩阵(m n),BT是B的转置矩阵,C是一个m m的半正定矩阵.f是Rn中的一个向量,g是Rm中的一个向量,F:Rn Rn是一个非线性严格单调且处处可微的函数.非线性鞍点问题广泛出现在电磁学中的Maxwell方程8和非线性最优化问题9中,例如minxRnJ(x)(f,x),s.t.Bx Cy=g,这里,J(x)是目标函数,J(x)=F(x).当F(x)=Ax时,方程(1.1)退化为线性鞍点问题ABTBCxy=fg.(1.2)求解鞍点问题(1.2)最经典的算法是Uzawa算法1,该方法与松弛块SOR迭代法类似.为了避免Uzawa迭代格式中的A1运算,Elman和Golub在文2提出了预处理不精确Uzawa方法.文3提出了求解问题(1.2)的非线性不精确Uzawa算法.文4将文2中的方法应用于求解非线性的鞍点问题,给出了标准范数意义的收敛性分析.但是,每一步计算x 都需要求解一个非线性方程F(x)=b,而此非线性方程的求解需要比较大的工作量.文5将文3中方法推广应用于求解非线性鞍点问题(1.1),给出了能量范数意义的收敛性分析.然而此方法计算x时每一收稿日期：2023-04-12基金项目：河南省自然科学基金面上项目(222300420585);河南省青年骨干教师基金(2020GGJS126);郑州轻工业大学博士科研基金(13501050020);河南省自然科学基金面上项目(232300420117)通讯作者：关宏波,男,汉族,河南人,教授,研究方向:数值代数.490应用数学2024步也需要求解非线性方程组F(x)=b.另外,该方法仅适用于C=0的情况.文10 提出了求解C=0时的非线性鞍点问题的不精确Uzawa方法:算法1.110给定初始向量x0 Rn,y0 Rm,对i=1,2,3,直到迭代序列xi,yi收敛,计算xi+1=xi+(f (F(xi)+BTyi),yi+1=yi+Q1B(Bxi+1 Cyi g).(1.3)但此方法计算y时需要求解矩阵的逆,计算成本较高.本文在此基础上提出了一种新的求解非线性鞍点问题的非线性不精确Uzawa方法,该方法通过引入一个非线性映射,避免了矩阵求逆,大大提高了计算效率.随后给出了能量范数意义下算法收敛的充分条件,最后的数值实验验证了算法的有效性和可行性.2.算法设计为方便后面分析,先说明一些记号和理论.设Rn为n维欧几里得空间,对任意的n n正定矩阵G,其对称部分为Gs=12(G+GT),xGs=(Gsx,x)12为Gs诱导的能量范数.如果A是一个正定矩阵,As是一个对称正定矩阵,则当 1时,对任意的向量v和w,As满足下面的不等式(Av,w)(Asv,v)1/2(Asw,w)1/2.(2.1)对于非线性鞍点问题(1.1),假设F(x)是处处可导、Lipschitzian连续而且倍严格单调递增函数,即,Rn,都有(F()F(),)2.(2.2)设DF表示有F的所有可导的点构成的点集,F()表示F在 DF处的梯度.按照文7中的定义,F在点x处的广义Jacobi是F(x)=coBF(x),其中coBF(x)表示集合BF(x)=limx,DFF(x)的凸包.由严格单调性质(2.2)知,对任意的 Rn,F()中的矩阵都是正定的,即,对任意的V F(),不等式(V,)(,)都是成立的.则 Rn,存在一个正定矩阵QA BF(+),使得lim0F(+)F()QA=0.上面关于F的性质都是l2范数意义下的性质,而文5给出了F在能量范数意义下的性质:设x,y是方程(1.1)的精确解,对任意的,存在一个正定矩阵A BF(+),使得F满足lim0F(+)F()AA1A=0.(2.3)下面给出的算法2.1为一个新的求解非线性鞍点问题的非线性不精确Uzawa算法,其优势在于避免求解矩阵的逆,能够提高计算效率.算法2.1给定初始向量x0 Rn,y0 Rm,对i=1,2,3,直到迭代序列xi,yi收敛,计算xi+1=xi+(f (F(xi)+BTyi),yi+1=yi+(Bxi+1 Cyi g),其中(v)是方程A=v的根的近似值,(u)是方程QB=u的根的近似值.非线性算子满足条件(v)A1vAs A1vAs v(A1)s,(2.4)其中 (0,1).同时,满足(u)Q1BuQB Q1BuQB uQ1B,(2.5)第 2 期豆铨煜等：关于非线性鞍点问题的一个新的非线性不精确Uzawa算法491其中 (0,1).对于非对称矩阵A,采用GMRES方法11求解满足条件(2.4)的近似逆.类似地,采用共轭梯度法(CG)求解对称矩阵的近似逆时,能够使条件(2.5)成立.另外,对于对称正定矩阵QB,以及任意的y Rm,存在一个正数 (0,1)使得(1 )(QBy,y)(B(As)1BT+C)y,y)(QBy,y).(2.6)3.收敛性分析本节给出算法2.1的收敛性定理.为了证明该定理,我们先重述文6,10已经给出的一些结论,这些结论和性质在我们后面的收敛性分析中起着重要的作用.引理3.16假设A是一个可逆的线性算子,它的对称部分As是正定的且满足条件(2.1),那么(A1)s也是正定的且对任意的w满足(A1)sw,w)(As)1w,w)2(A1)sw,w).(3.1)引理3.210对任意的向量v Rn,如果A是正定的,QB是对称正定的,且(2.6)式成立,则成立不等式BvQ1B vAs.(3.2)引理3.310假设A是正定的,它的对称部分As满足(2.1).QB是一个对称正定的算子满足(2.6),当=(2 (2(1 )/2)12时,有(I Q1B(BA1BT+C)vQB vQB.(3.3)另外,如果0 12,那么 1.基于以上三个引理,我们给出算法2.1的收敛性分析,得到本文主要结论如下:定理3.1假设不等式(2.1)和(2.6)成立,F是一个处处可导的函数,(x,y)是方程(1.1)的精确解,(xi,yi)是通过算法2.1求出的数值解.定义残差exi=xi x,eyi=yi y.令=(2 (2(1 )/2)12,那么xi,yi分别收敛到x,y,如果0 12,0 1 21 ,0 1 +(2)3 +(2 ),0 0.显然,M的谱半径等于它的正特征值,的表达式由(3.6)给出.容易验证如果(3.4)式成立,那么 1,到此定理得证.4.数值实验为了验证算法2.1的有效性,本节考虑文10中的数值算例.令Im是一个m m单位矩阵,Tm是一个m m矩阵,它的元素是tij=1,|i j|=1,0,|i j|=1.当n=2m时,定义一个nn矩阵E,mn行满秩矩阵B和一个mm对称半正定矩阵C,如下:E=(52Im14TmImIm52Im14Tm),B=(0,2Im Tm),C=(Im/2000).对所有x=(x1,x2,xn)T Rn,非线性映射F的定义是F(x)=Ex+15(x11+x21,x21+x22,xn1+x2n)T.容易证明F是严格单调的且Lipschitzian连续的,对任意给定的f Rn和g Rm,方程组(1.1)都有唯一解.另外,A=E+15diag(1 x21(1+x21)2,1 x22(1+x22)2,1 x2n(1+x2n)2),满足452(A,)2152.把精确解设定为x=(1,1,1)T,y=(1,12,1m)T,494应用数学2024把它们代入方程(1.1)即可得到f和g.在数值实验中,初始向量(x0,y0)选为零向量,算法的停止准则是Error=f F(xi)BTyi2+g Bxi+Cyi2f2+g212 106.选择预处理子QB=54BBT+C以确保不等式(2.6)成立.通过5步预处理共轭梯度法来定义映射,预处理子是M=LLT,其中L 是E的不完全Cholesky分解因子,即E=LLT R,舍入容许误差是0.01.通过CG方法定义映射.所有计算均在一台CPU为2.50GHz和内存为4.0GB的计算机上完成的.图1给出了算法2.1求解不同m对应的非线性鞍点问题的误差随迭代步数的变化图,误差图进一步说明新的算法对于求解非线性鞍点问题是有效的,同时验证了理论分析的正确性.表1给出了算法1.1和2.1求解非线性鞍点所需的迭代步数(IT)、时间(CPU)和误差(ERR).数值实验结果说明新的算法2.1是收敛有效的,而且计算效果优于算法1.1.需要指出的是本文提出的算法2.1每一步的误差都比算法1.1误差小.另外,CPU平均运行时间约为算法1.1运行时间的50%左右,节省了将近一半的工作量.m=100m=1000m=4000m=9000图1误差随迭代步数的变化图表1算法1.1和2.1的数值结果算法1.1算法2.1mITCPUERRITCPUERR100280.03107.73e-7270.01507.62e-7400260.18209.16e-7260.09409.02e-7800250.49509.95e-7250.25009.79e-71000250.65308.91e-7250.35908.76e-74000241.98006.85e-7231.55806.73e-78000234.91507.44e-7224.11737.31e-79000225.20607.02e-7224.41806.89e-7第 2 期豆铨煜等：关于非线性鞍点问题的一个新的非线性不精确Uzawa算法4955.结论本文构造了一个新的求解非线性鞍点问题的非线性不精确Uzawa算法,理论分析建立了算法的收敛性,数值结果表明新算法求解非线性鞍点问题是有效可行的.参考文献：1 ARROW K,HURWICZ L,UZAWA H.Studies in Linear and Nonlinear ProgrammingM.Palo Alto:Stanford University Press,1958.2 ELMAN H C,GOLUB G H.Inexact and preconditioned Uzawa algorithms for saddle point problem-sJ.Siam Journal on Numerical Analysis,1994,31:1645-1661.3 HU Q Y,ZOU J.Two new variants of nonlinear inexact Uzawa algorithms for saddle point problem-sJ.Numerische Mathematik,2002,93:333-359.4 CHEN X J.Global and superlinear convergence of inexact Uzawa methods for saddle point problemswith nondifferentiable mappingsJ.Siam Journal on Numerical Analysis,1998,35:1130-1148.5 HU Q Y,ZOU J.Nonlinear inexact Uzawa algorithms for linear and nonlinear saddle point problem-sJ.Siam Journal On Optimization,2006,16:798-825.6 BRAMBLE J H,PASCIAK J E,VASSILEV A T.Uzawa type algorithms for nonsymmetric saddlepoint problemsJ.Mathematics Of Computation,1999,69:667-689.7 CLARKE F H.Optimization and Nonsmooth AnalysisM.Hoboken,NJ:Wiley,1983.8 CHEN Z,DU Q,ZOU J.Finite element methods with matching and nonmatching meshes for Maxwellequations with discontinuous coefficientsJ.Siam Journal on Numerical Analysis,2000,37:1542-1570.9 FLETCHER R.Practical Methods of OptimizationM.Second Edition.Hoboken,NJ:John Wiley,1987.10 LI J L,HUANG T Z,LI L.Analysis of the ineaxct Uzawa algorithms for nonlinear saddle pointproblemsJ.Anziam Journal,2010,51:369-382.11 SAAD Y,SCHULTZ M H.GMRES:a generalized minimal residual algorithm for solving nonsym-metric linear systemsJ.Siam Journal On Scientific Computing,1986,7:856-869.A New Nonlinear Inexact Uzawa Algorithm for NonlinearSaddle Point ProblemsDOU Quanyu,GENG Hongrui,GUAN Hongbo(School of Mathematics and Information Science,Zhengzhou University of Light Industry,Zhengzhou 450002,China)Abstract:A new nonliear inexact Uzawa algorithm for solving nonlinear saddle point problems isproposed by constructing nonlinear mapping in this paper.The algorithm avoids the inverse operationnecessary for the traditional Uzawa method.The sufficient condition for the convergence of the algorithmis obtained by careful analysis in the sense of energy norm.Finally,a numerical experiment is given toshow high efficiency of the proposed algorithm.Key words:Nonlinear saddle point problem;Nonlinear inexact Uzawa algorithm;Convergenceanalysis