A primal-dual fixed point algorithm for convex separable minimizaion with applications

交替极小化算法交替极小化算法（Alternating Direction Method of Multipliers，ADMM）是一种用于解决带有线性或者凸二次约束的优化问题的迭代算法。

它最初由Gabriel Peyré和Stéphane Mallat在2010年提出，并在之后的几年里得到了广泛的应用和研究。

ADMM算法的基本思想是将原始问题转化为一系列等价的子问题，然后通过交替优化这些子问题来逐步逼近原始问题的最优解。

具体来说，ADMM算法将原始问题表示为如下形式：$$\min_{x,z} f(x) + g(z)$$$$\text{s.t. } Ax+Bz=c$$其中$f(x)$和$g(z)$分别是$x$和$z$的凸函数，$A,B$是线性变换矩阵，$c$是常数向量。

ADMM算法通过增加一个拉格朗日乘子项$\frac{\rho}{2}\|Ax+Bz-c+\lambda\|^2$将上述问题转化为如下形式：$$\min_{x,z} f(x) + g(z) + \frac{\rho}{2}\|Ax+Bz-c+\lambda\|^2$$其中$\rho>0$是一个常数，$\lambda$是拉格朗日乘子向量。

然后，ADMM算法通过交替优化以下三个子问题来求解上述问题：1. $x$子问题：$$x^{k+1} = \arg\min_x f(x) +\frac{\rho}{2}\|Ax^{k}+Bz^k-c+\lambda^k\|^2$$2. $z$子问题：$$z^{k+1} = \arg\min_z g(z) +\frac{\rho}{2}\|Ax^{k+1}+Bz-c+\lambda^k\|^2$$3. $\lambda$子问题：$$\lambda^{k+1} = \lambda^k +Ax^{k+1}+Bz^{k+1}-c$$其中$k$是迭代次数。

ADMM算法的优点在于它可以处理大规模的优化问题，并且可以应用于分布式计算环境中。

摘要随着科学和工程技术的发展，越来越多的问题需要求解大规模的线性方程组，对这类方程的快速求解已成为数值代数研究的热点之一，特别是具有稀疏结构的大型方程组的求解。

基于Galerkin原理的Arnoldi算法是求解这种线性代数方程组的近似算法，以下称这种方法为广义极小残余算法(GMRES算法)。

GMRES 方法是目前求解大型稀疏非对称线性方程组最为流行的一种迭代方法。

GMRES算法在迭代过程中通常表现出一种加速收敛行为，随着迭代次数的增加，这种加速收敛现象越明显，即残量收敛会随着迭代步数的增加而逐渐得到改善。

在CG方法中，这种加速收敛与Ritz值有密切关系。

通过分析，我们发现GMRES的加速收敛与其斜投影过程中产生的Ritz值对特征值的逼近程度有关系。

在实际应用中，为了减少存储量和计算量，我们通常使用GMRES算法的重新开始版本来求解大型非对称线性方程组。

本文描绘了GMRES和GMRES(m)的加速收敛现象，并通过实验给予解释。

关键字：广义最小残量； Krylov子空间； Ritz值；加速收敛；正交投影方法；非对称线性方程组On The Superlinear Convergence of GMRESAbstractWit h the d evelo p me nt o f science and p ro ject techno lo g y,mo re and mo re q uestio ns need the so lut io n o f b ig linear syste ms. T h is so lut io n is o ne o f the fastest ways fo r researchin g nu mer ica l algeb ra,esp ecia lly fo r the b ig sparse matr ix. The way o f Arno ld i is b ased up o n the p rinc ip le o f Galerk in, wh ich is clo se d to the so lut io n o f the linear nu mer ica l system.Here, we call the so lut io n as Generalized Min imu m Res id ua l (GMRES).GMRES is o ne o f the mo st p op u lar iterat ive met ho d s fo r the so lut io n o f b ig no ns in gu lar no nsy mmetr ic linear syste ms.It us ua lly has a so-called sup er linear co n vergence b ehav io r.The rate o f co nverge nce seems to imp ro ve as the iterat io n p ro ceed s.F o r ano ther say,the rate o f resid ua l var iab le w ill b e imp ro ved as we increase its iterat io n.F o r the co nju gate grad ie nts metho d, th is met ho d has b een related to a d egree o f co nverge nce o f t he Rit z va lue. Thro u g h so me ana lys is,we fo und that fo r GMRES to o, changes in co n vergence b ehav io r seem to be related to the co nverge nce o f R it z va lue. In o ur p ractica l app licat io n,we also usua lly use GMRES(m) fo r red uc in g sto rage and co unter so lv in g b ig linear systems.Th is p ap er stud ies the sup erlinear co nvergence b ehav io r o f GMRES and GMRES(m),and sup p lies exp la in thro u g h exp erimen t.Key wo rd: GMRES; K ry lo v sub sp ace; R it z va lue; sup er linear co nverge nce;o rtho go na lizat io n metho d; no nsy mmetr ic linear system目录摘要 (I)A B S T RA C T ................................................. I I 第一章引言.. (1)第二章G M R E S算法基础知识 (3)§2.1向量范数 (3)§2.2线性方程组最小二乘问题 (4)§2.2.1Gr a m-S ch m id t正交化方法 (4)§2.2.2Gi v en s变换 (4)第三章G M R E S算法理论 (6)§3.1K RYLOV子空间方法的基本理论 (6)§3.2A RNOLDI算法 (7)§3.3G MR E S算法结构 (8)第四章G M R E S算法的加速收敛现象分析 (9)第五章数值示例与算法实现 (19)§5.1数值实验 (19)§5.2算法改进与实现 (22)§5.2.1预处理技术 (22)§5.2.2算法实现 (24)§5.3实验总结 (34)致谢 (35)参考文献 (38)R E P O RT OF LI T E RA T UR E (39)文献报告 (43)第一章 引言关于线性方程组的数值解法一般分为两大类:直接法和迭代法。

CG算法的预处理技术：、为什么要对A进行预处理：其收敛速度依赖于对称正定阵A的特征值分布特征值如何影响收敛性：特征值分布在较小的范围内，从而加速CG的收敛性特征值和特征向量的定义是什么？（见笔记本以及收藏的网页）求解特征值和特征向量的方法：Davidson方法：Davidson 方法是用矩阵( D - θI)- 1( A - θI) 产生子空间，这里D 是A 的对角元所组成的对角矩阵。

θ是由Rayleigh-Ritz 过程所得到的A的近似特征值。

什么是子空间法：Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi 的迭代形式来求解。

这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。

如何取正定矩阵Mk为：Span是什么？:设x_(1,)...,x_m∈V ,称它们的线性组合∑_(i=1)^m?〖k_i x_i \|k_i∈K,i=1,2...m〗为向量x_(1,)...,x_m的生成子空间，也称为由x_(1,)...,x_m张成的子空间。

记为L（x_(1,)...,x_m），也可以记为Span（x_(1,)...,x_m）什么是Jacobi迭代法：什么是G_S迭代法：请见PPT《迭代法求解线性方程组》什么是SOR迭代法：什么是收敛速度：什么是可约矩阵与不可约矩阵？：不可约矩阵（irreducible matrix）和可约矩阵（reducible matrix）两个相对的概念。

定义1：对于n 阶方阵A 而言，如果存在一个排列阵P 使得P'AP 为一个分块上三角阵，我们就称矩阵A 是可约的；否则称矩阵A 是不可约的。

定义2：对于n 阶方阵A=(aij) 而言，如果指标集{1，2，...，n} 能够被划分成两个不相交的非空指标集J 和K，使得对任意的j∈J 和任意的k∈K 都有ajk=0, 则称矩阵 A 是可约的；否则称矩阵A 是不可约的。

习题 11. 执行下列指令，观察其运算结果, 理解其意义： (1) [1 2;3 4]+10-2i(2) [1 2; 3 4].*[0.1 0.2; 0.3 0.4] (3) [1 2; 3 4].\[20 10;9 2] (4) [1 2; 3 4].^2 (5) exp([1 2; 3 4]) (6)log([1 10 100]) (7)prod([1 2;3 4])(8)[a,b]=min([10 20;30 40]) (9)abs([1 2;3 4]-pi)(10) [1 2;3 4]>=[4,3;2 1](11)find([10 20;30 40]>=[40,30;20 10])(12) [a,b]=find([10 20;30 40]>=[40,30;20 10]) (提示：a 为行号，b 为列号) (13) all([1 2;3 4]>1) (14) any([1 2;3 4]>1) (15) linspace(3,4,5) (16) A=[1 2;3 4];A(:,2)2. 执行下列指令，观察其运算结果、变量类型和字节数，理解其意义： (1) clear; a=1,b=num2str(a),c=a>0, a= =b, a= =c, b= =c (2) clear; fun='abs(x)',x=-2,eval(fun),double(fun)3. 本金K 以每年n 次，每次p %的增值率(n 与p 的乘积为每年增值额的百分比)增加，当增加到rK 时所花费的时间为)01.01ln(ln p n rT +=(单位：年)用MA TLAB 表达式写出该公式并用下列数据计算：r =2, p =0.5, n =12.4．已知函数f (x )=x 4-2x 在(-2, 2)内有两个根。

取步长h =0.05, 通过计算函数值求得函数的最小值点和两个根的近似解。