在过去的三十多年里,由于现实社会实际生产与实践应用的广泛迫切需要,在天气预报、大型飞机研制、油田勘探与开采等诸多领域,数学物理和工程计算问题的数值模拟规模日趋增大,其相应的计算工作陷入了前所未有的极大困境,同时也伴随着或导致了难以承受的工作量。如此状况,使得信息与计算科学工作者切身感受到解决超大规模计算问题的紧迫性,同时也凸显了对计算方法研究的重要性。此外,计算机科学技术的迅猛发展在从根本上改变了落后的计算工具的同时也逆向促进了相关数学基础理论的发展,使得计算数学成为数学学科的一个新兴而活跃的研究领域。本文主要研究以下两类优化问题:时间偏微分方程约束的最优控制问题和结构化的凸优化问题。从计算的角度来说,这两大类问题都具有很高的计算复杂度,并在实际工程计算中具有极其广泛的应用价值。作者主要基于区域分解方法和凸优化理论,构造相关问题的快速算法,证明每个算法的收敛性,并给出相应的数值算例。全文共分为六章。在第一章中,简要叙述与回顾了凸优化和反问题的相关文献,指出了当今科学计算困境的关键之处,并对超级计算机和区域分解方法进行了扼要介绍。特别地,建议读者阅读第二至第五各章的起始部分,这些部分同样也会给出与每章主题相关的文献内容。在第二章中,研究如下结构化的优化问题:其中f为具有Lipschitz连续梯度的凸函数,h和g为适当的、下半连续的凸函数,A:Rd→Rd’是一个线性映射。此外,我们假设临近点算子proxαh和proxαg具有显示表达式,但是临近点算子proxαh+αgoA无法得到显示解（其中α为常数）,此假设和框架适用于大量图像处理和其他学科领域研究所涉及的变分问题。众所周知,如果将g（Au）+h（u）整体看成一个凸函数,可以使用以下邻近-梯度算法来求解模型问题:un+1 = proxαk+αgoA（un-α▽7f（un））.由于算子proxαhαh+αgoA没有显示表达式且其本身仍为一个凸优化问题,因此我们考虑使用凸优化问题的原始-对偶算法来对算子prOXαh+αgoA进行迭代逼近。从理论上来说,对算子proxαh+αgoA的精确逼近需要进行无限多次运算,但在实际计算中是不可能实现的。在计算时,若考虑充分迭代,且使得相关误差达到机器精度,则仍会浪费巨大的计算成本。文献[180]和[59]中考虑了使用单步进行不精确逼近的情况,并给出了相关算法的收敛性证明。我们在本章中考虑采用有限多步的逼近策略,得到以下两个凸优化问题的原始-对偶算法来求解此类问题:嵌套原始-对偶算法Ⅰ（NPDA-Ⅰ）第一步:给定参数0<α<2/L,0<β<1/||A||2和kkmax.选择初始值u0,v-1kmax 和容许误差ε>0,并设 n = 0.第二步:设k:= 0,kmaX-1,进行如下更新:第三步:令unkmax=prox αh（un-α▽f（un）-αATvnkmax）.第四步:令un+1=∑k=1kmaxunk/kmax.第五步:计算相对误差:eps=||un+1-un||2+||vnkmax-vn-1kmax||2.如果eps ≤ ε,则停止迭代并输出u = un+1和v = vnkmax.否则设n:= n +1并返回第二步进行下一次的迭代。嵌套原始-对偶算法Ⅱ（NPDA-Ⅱ）第一步:给定参数0<α<2/L和0<β<1/||A||2.选择初始值u0,v-1 1和容许误差ε>0,并设n = 0.第二步:给定kn ∈ N0.设= 0,,-1,进行如下更新:第三步:令un+1= un kn = proxαh（un-α▽f（un）-αATvnkn）,第四步:计算相对误差:eps = ||un-1-un||2 +||vn1-vn-1 1||2.如果eps≤ε,则停止迭代并输出u = un+1和v =vn 1.否则设n:= n + 1并返回第二步进行下一次的迭代。以上两个算法在实现时只需计算梯度和两个临近点算子,并不需要显式地计算任何算子的逆。在结构上两个算法都包含外迭代和多步内迭代:第一个原始-对偶算法固定内迭代次数,在内迭代结束时还需要计算原始变量的平均值。第二个原始-对偶算法的内迭代次数可以随迭代步数而变化,在理论上可以达到无穷多步。两个算法都推广了文献[180]和[59]中算法。算法的收敛性基于不动点理论和内迭代的热启动策略:第一个算法对偶变量的初始值选取上一内迭代步对偶变量的最终值,而第二个算法则需重启对偶变量。可以证明,对任意α,β>0,模型问题满足如下的一阶最优性条件:在原始和对偶变量的乘积空间上,迭代算法的解和模型问题的最优解之间的误差具有有界性和单调性。从而在与文献[180]相同的条件下,我们可以得到算法在固定参数α和β时的收敛性。更进一步,假定算子A具有强制性并且函数f具有强凸性,可以验证两个算法在目标函数h = 0时的线性收敛率。我们将提出的算法应用于图像去模糊问题,数值算例表明,多步内迭代在噪声较大时比单步内迭代能够更快地收敛。在第三章至第五章中,考虑时间依赖偏微分方程的相关算法,采用有限元方法进行数值离散,以h和Mh表示最大网格单元直径和网格剖分τh上的有限元空间,并以A（w,u）表示双线性形式（▽w,▽v）.在第三章中,研究线性抛物方程的区域分解方法:其中Ω为Rd（1≤d ≤ 3）中一个具有Lipschitz边界（?）Ω的有界开集,系数0<a0<a（x）<a1,b = b（x）,f = f（x,t）和u0 = u0（x）是给定的实值函数。本章考虑Ω为R2中方形区域的情况,一般情况可以参考文献[185,249].众所周知,用显式方法求解问题易于程序设计,实现并行计算也相对方便,但是会不可避免地产生一个与时间步长和空间步长有关的约束条件。该条件限制了问题求解的时间步长,使得计算成本和计算时间都大大增加。当使用隐式方法求解问题时,必须在每个时间层上求解一个线性方程,随着时间离散步长或者空间离散步长的减小,大量的计算成本被浪费在求解方程上。与传统的显式格式相比,显/隐式策略同时具备显式方法和隐式方法的优点,虽然仍然保留了时空的约束条件,但该条件被很大程度放宽。本章基于文献[83]和[249]研究线性抛物方程的二阶显/隐式区域分解算法。我们首先将整体区域分为I个不重叠的子区域,类似于Dawson和Dupont在文献[83]中的思想,定义内边界Γ上外法向导数的一个逼近:B（φ）（x）=-∫2H 2H φ’（τ）▽φ（x + τnΓ）dτ,x ∈ Γi∩Γj,1 ≤ j ≤ I.其中4H是局部平均的宽度,对于显/隐式区域分解算法的稳定性起着重要作用。可以证明以上外法向导数的逼近具有O（H4）的精度。对模型问题使用Green公式得到变分形式:（（?）tu,vh）+ A（u,vh）+（bu,vh）-（a▽▽u · nΓ,[vh]）r =（f,vh）,（?）vh∈ Mh4.其中[v]代表内边界处函数值的跳跃。用B（φ）（x）间来代替上式中的外法向导数,并记g-n-1/2= 1/2（gn+gn-1）和gn-1/2 = 1/2（2gn-1 +gn-2-gn-3）,可以得到如下两个区域分解格式:Crank-Nicolson-显/隐区域分解方法 I（CNEIDDM-I）第一步:给定初始值Un=u0 + n△t（f0 + ▽.（a▽u0）-bu0）,n = 0,1,2.第二步:对n = 3,4,…,N,在每个子区域中并行更新Un ∈Mb:（（?）tUn,V）+ A（Un-1/2,V）+（bUn 1/2,V）-（aB（Un 1/2）,[V]）Γ=（fn-1/2,V）,（?）V ∈Mh.Crank-Nicolson-显/隐区域分解方法 Ⅱ（CNEIDDM-Ⅱ）第一步:对n = 0,1,2,在每个子区域中并行更新Un∈Mh 使得Un|Ωi=Uin∈Mjh满足A（Uin,V）Ωi + κ（Uin,V）Ωi = A（vin,V）Ωi + k（vin,V）Ωi,（?）V∈Mih,其中vn =u0+n△t（∫0+ ▽·（a▽u0））,参数k>760||√a||w1,∞2（Ω）+ 1.第二步:对n = 3,4,…,iV,在每个子区域中并行更新Un ∈ Mh:以上两个算法均为非重叠区域分解方法,在时间方向上采用Crank-Nicolson格式进行离散,在每个子区域中采用守恒的隐式格式,每个时间层上只需要显式地计算内边界处外法向导数的逼近。需要注意的是,当前时间层的计算需要使用前三个时间层上的函数值,但是由于相应的计算只使用内边界附近的函数值,所以相比传统的格式其实只是增加了很少的运算量。本章得到的时间步长与空间步长的约束条件为△t= O（H2）,与 Dawson和Dupont在文献[83]中提出的一阶格式相同,但与传统的显式格式相比,在很大程度上得到了放宽,从而允许使用较大的时间步长进行计算。在先验误差分析中,除了引入常规的椭圆投影外,我们还针对每个算法再定义了一个椭圆投影。通过证明两个椭圆投影辅助问题之间的关系（见引理3.8和引理3.12）,我们得到算法（几乎）最优的收敛阶。本章最后给出一些数值例子来验证理论的准确性。在第四章中,研究控制变量点态受限的线性抛物方程约束最优控制问题:使得其中Ω为R（1≤d≤3）中一个具有Lipschitz边界（?）Ω的有界开集,α>0是一个常数,u∈K = L2（0,T;K）是控制变量,y是状态变量,yd是已知的观测函数,y0是初始观测函数。此外,a = a（x）是扩散系数满足0<a0 ≤ a ≤ a1,yd=yd（x,t）,y0=y0（x和f = f（x,t）是给定的实值函数。本章仅考虑K={u≥0}的情形。文献[256]中,我们先对模型问题进行数值离散,再推导得到对应的全离散最优性条件,提出了求解该最优控制问题的一阶区域分解算法。本章考虑模型问题的二阶显/隐式区域分解算法,对比文献[256]中先离散问题后得到全离散的最优性条件的方法,我们先推导得到模型问题的连续最优性条件:该最优性条件是一个由控制变量有关的正向方程、状态变量有关的倒向方程和变分不等式组成的耦合系统。我们结合第三章提出的二阶显/隐格式对最优性条件进行数值离散,得到以下离散格式:状态方程:第0层:A（Y0-y0,V）+ k（Y0-y0,V）= 0（?）V∈ Mh;Y10 = Y0;第1层:第2层:第n层:对偶状态方程:第N层:p1N = pN = 0;第N-1层:第N-2层:第n层:变分不等式:（αUn-1/2 + Pn-1/2,Z-Un-1/2）>≥0,（?）Z ∈ KhU,n=1,2,,N.以上离散系统至少存在一个解,且对于状态方程与对偶状态方程初始值的选取与第三章所使用的方法不同,本章对初始值的离散是通过迭代方法来实现的。虽然该离散系统已经进行了区域分解,但仍无法进行并行求解,我们引入外迭代对该系统进行解耦,得到如下并行迭代区域分解算法:二阶并行迭代区域分解方法（PDDIA）第一步:给出初始值{U0n-1/2}n=1N（?）Uhu 取定ε>0为容许误差,并设k = 0.第二步:在Ωi（1 ≤ i ≤ I）上进行并行更新{Yk-1m}n=0M（?）Mh:第0层:第1层:第2层:第n层:第三步:在Ωi（1 ≤ i ≤ I）上进行并行更新{Pk-1n}n=0N（?）Mh:第N层:第N-1层:第N-2层:第n层:第四步:更新{UhU,k=1 n-1/2}n=1N（?）Uhu使得其中ρ是一个常数,满足0<ρ<1,QhU是一个从Uhu到KhU的投影。第五步:计算相对误差:如果eps≤ε,则停止迭代并输出Um-1/2= Uk+1m-1/2,m = 1,2,…,N,和Yn = Yk+1n,Pn = Pk+1n,n = 0,1,2,…,N.否则设k:= + 1并返回第二步进行下一次的迭代。基于对离散最优性系统初始值的分析,我们得到离散最优性条件的解与精确解之间的先验误差。基乎压缩映射原理,我们证明了迭代并行区域分解算法对于离散最优性系统的解的收敛性和离散最优性系统的解的存在性。本章最后给出一个数值例子来验证理论的准确性。在第五章中,研究如下波动方程的区域分解算法:其中Ω为Rd（1 ≤ d ≤ 3）中一个具有Lipschitz边界（?）Ω的有界开集,系数矩阵A= aij（x））d×d∈Rd×d为一致正定的矩阵函数,即存在0<a0≤a1<∞使得a0∑i=1dεi2≤∑i,j=1d aij（x）εiεj≤a1 ∑i=1dεi2,（?）x∈Ω,ε∈Rd.i=1 i,j=1 i=1函数f,φ0和φ1是给定的具有足够光滑性的函数。一般来说,利用差分对时间进行离散之后,我们需要在每个时间层上用有限元方法或其他数值方法求解一个椭圆问题。在时间步长较小时,之前时间层上计算所得到的函数值可以作为当前需要计算时间层上函数值的预估值。因此,预估-矫正方法成为设计数值算法的自然思想。本章采取的预估-矫正策略基于标准有限元方法,单位分解函数{{φj}jJ=1分别在预估和矫正时引入,使得整体区域上全局问题的求解被合理地分解为J个子区域上的子问题进行计算或者矫正。我们得到如下两种重叠型区域分解算法:非迭代并行施瓦茨区域分解方法I（NIPSDDS-I）给定初始值W0和W1.设n = 2,3,…,N.算法NIPSDDS-I对Wn∈Mh进行如下两步更新:第一步:对j = 1,2,…,J并行更新Ejn∈Mjh使得a（Ejn,V）= △t2（fn,1/4,Lh（φjhV））-△t2A（Wn-1,Ih（φjh V））,（?）V V ∈ Mjh.第二步:设Wn = 2Wn1-1-Wn-2 + ∑j=1 J Ejn.非迭代并行施瓦茨区域分解方法Ⅱ（NIPSDDS-Ⅱ）给定初始值W0和W1.设n = 2,3,…,N.算法NIPSDDS-Ⅱ对Wn ∈Mh进行如下两步更新:第一步:对j = 1,2,…,J并行更新εjn∈Mjh使得a（εjn,V）= △t2（fn,1/4）-△t2A（Wn-1,V）,（?）V ∈ Mjh.第二步:设Wn = 2Wn-1-Wn-2+ ∑j=1 J Ih（φjh εjn）.其中a（w,v）为双线性型（w,v）+△t2/4A（w,v）.对区域分解方法的每个子区域而言,因不能先验地知道子区域内边界处函数的相关信息,所以越靠近内边界往往计算所得到的误差越大。本章提出的区域分解方法的相关误差在内边界处具有指数阶衰减性（见引理5.4）,此外我们采用满足以下条件的单位分解函数{φj}jJ=1:dis（supp（φj）,（?）Ωj\Γ）>δ/2 and δ ≥ h.其中δ为子区域的重叠度,Γ为所有内边界组成的集合,因此我们在实际计算过程中使用的是每个子区域上较为准确的函数值。对于重叠型区域分解方法,计算时所需要的信息交换主要来自相邻子区域的重叠部分,重叠度的大小直接影响子区域之间信息的交换量,本章提出的区域分解方法的重叠度为O（max{h,△t2/h} |ln（h△t）|）,与网格大小成比例,允许使用大量的处理器同时进行计算。基于以上的两个算法与标准有限元方法之间的误差的递推关系式（见引理5.6）,我们证明了算法的先验误差估计。从数值算例中可以看出,算法适用于复杂解的情况,与标准有限元方法之间的误差是标准有限元方法与方程精确解之间误差的高阶量。在第六章中,对第二章到第五章的内容做出了总结,并提出了一些将来可以继续进行的工作。