共轭梯度算法

共轭梯度算法（共9篇）

共轭梯度算法 篇1

1 引言

正交频分复用技术OFDM, 是用一组相互正交的子载波来传输数据流的。与其他的多载波调制技术相比, 具有频率利用高、抗多径效应带来的码间串扰以及可以利用数字信号处理技术实现等很多优点, 因此, OFDM技术成为了当前多载波调制的研究热点。但由于OFDM信号在时域上表现为N个正交子载波的叠加, 因此具有很高的峰均值比 (PARP) [1]。高峰均功率比 (PARP) 的存在, 是OFDM系统应用过程要解决的关键技术问题。相对于单载波系统而言, OFDM发射机的输出信号的瞬时值会有较大幅度的波动。这就要求系统内的一些器件, 例如功率放大器、A/D, D/A转换器等具有很大线性动态围。而反过来, 这些器件的非线性也会对动态范围较大的信号产生非线性失真, 所产生的谐波会造成子信道的相互干扰从而影响系统的性能, 因此有必要对OFDM的峰均功率比进行降低。目前, 已经提出很多种降低PARP的方法[2,3,4,5]。最常见的有3种:

(1) 限幅类方法; (2) 编码类方法; (3) 概率类的方法。而概率类方法可以在不产生信号畸变的情况下, 大大改善OFDM信号的PAPR性能。比较常用的概率类的方法有:最小PARP门限值、选择性映射方法 ( (SLM) 、部分传输序列方法 ( (PTS) 。其中SLM方法和PTS方法是两种最典型的概率类方法。虽然PTS和SLM算法都是无失真的算法, 但需要进行多次额外的IFFT运算, 因此它们的计算量很大。而且都需要在接收机一端精确地了解发射机所采用的辅助加权信息, 所以这一切都是会增加系统复杂度的。

用障碍函数法 (IPM) 来解决OFAM系统的PARP问题[6], 在限定星座误差向量级数 (EVM) 和超额功率 (power overhead) 的条件下[7], IPM方法通过几次迭代就能够有效地降低系统的PARP。

2 用共轭梯度 (Fletcher-Reeves) 来降低PARP

2.1 基于IPM算法来解决PARP问题

用IPM的算法思想来处理OFDM系统PARP问题[9], 可以由最优化问题得到最小PARP的OFDM数学模型[10]。最优化目标是最小化OFAM系统时域里的峰值, 然后由不同的约束条件建立不同的障碍函数。一般以3方面的约束条件来构造障碍函数:首先是保证每次迭代后的星座点的峰值不能超过迭代前的峰值;接着是限制星座图的误差, 不能让它跳出可判断的范围;最后是在前面两个条件下去最小化系统的PARP[11]。一般OFDM数学模型[10]可建立如下:

其中c0为调制过后的理想星座点, c0∈Cn;修正过后的星座点为:c=c0+∆;△由初始点决定, ∆∈Cn;时域信号, 是由c通过L倍过采样的IFFT变换得到的[5]。, 为复变量的内积, 它的定义如下:

那么, ℜ, 就为内积的实部。是由最大误差向量级数EVM确定的[6];对角矩阵S∈Rn×n, 结构如下[7]:

式 (1) 的问题用内部点 (IPM) 法解决[9], 将约束最小化问题通过增广函数而化成无约束问题。而增广函数可以通过多种无约束极小化算法来求解[9], 文献[12]运用Newton算法。虽然Newton法产生的点列收敛于平稳点, 且收敛速度是2价的。但是Newton法对初始点和函数的要求非常高, 需要一个比较好的初始点和比较多的存储单元, 进行矩阵求逆的运算。

所以本文提出用共轭梯度法 (Fletcher-Reeves) 来求解。这种算法是收敛速度虽然低于Newton法, 但是超线性的, 优于最佳下降法[9,10], 而且对初始点的要求不高, 不进行矩阵运算, 对存储量要求少。

2.2 用共轭梯度 (Fletcher-Reeves) 来降低PARP

最优化Fletcher-Reeves共轭梯度法算法是最重要的共轭方向法之一, 其主要思想是利用上一次的搜索方向和本次出发点的负梯度的线性组合来生成共轭方向, 计算量和存储量都比较小。在运用过程中, 由于OFDM所对应的变量是复变量, 所以首先有必要对向量c∈Cn进行扩展, 变为2n的向量, 如下:

其中C为傅立叶变换前的星座点, 进行扩展后2n的向量对应的分别是星座点的实部和虚部。由于目标函数f (x) 为OFDM的峰值P, 而相应地要把对应的傅立叶系数矢量也进行扩展, 变为2n的向量, 如下:

由于用Fletcher-Reeves共轭梯度法算法求最佳需要求导, 那么为了计算的方便, 需要把 (1) 式形式进行改变。最小化目标为:p2。那么峰值p2的表达式为:

||S△||≤, 变成, i=1, 2, 3, ….n;

对于条件||xi||≤p i=1, 2, 3….n的限制, 在进行障碍函数构造的时候, 由于要进行的运算, 为了避免求导时分母为0, 每次迭代后选取:

其中∂>1。上述展开的公式是以没有考虑过采样为前提的。

用共轭梯度法 (Fletcher-Reeves) 来降低PARP算法如下[11]:

的表达式在附录中。变量X为逆傅立叶变换之前的星座点C。

(2) 求解一维搜索问题

(3) 如果Xk+1满足终止准则, 输出Xk+1, 计算停止;否则, 转4;

(4) 如果k=n-1, 令X0=Xk+1, k=0, 转1;否则, 转5

(6) 如果∇f (Xk+1) Qk+1≥0, 令X0=Xk+1, 转1;否则, k=k+1, 转2。

通过每次迭代, 我们都会得到新的峰值p*, 新的星座点c*, 新的经过采样和逆傅立叶变换之后得到的序列x*, 它们的关系如下:

由于要保证算法的可行性, 每次要而∂要尽量靠近1, 在附录中会加已说明。用FletcherR e e v e s共轭梯度法算法去处理O F D M的PA R会比用Newton法带来新的问题, 虽然这种方法对初始点的要求并不高, 不用进行矩阵逆运算。但它对步长的要求却非常的苛刻, 如果步长太大就很难在规定范围找到最佳点, 如果太小会增加搜索的次数。

3 仿真实验

下面用所提出的方法在OFDM的5GHz无线局域网标准基础上对进行仿真分析。

3.1 基于OFDM的5GHz无线局域网标准

1990年 (IEEE) 802局域网/城域网 (LAN/MAN) 标准委员会建立了802.11工作组以制订一个无线局域网标准。第一份标准于1997年公布, 数据速率为1 Mb/s和2 Mb/s。自首次公布之后对无线传感网络的物理层的标准经过几次修改和改进, 现在包括5种物理层标准[13]:

(1) 红外, 1 Mbit/s, 可选2 Mbit/s

(2) 2.4GHz, 跳频扩频, 1 Mbit/s, 可选2Mbit/s

(3) 2.4GHz, 直接序列扩频, 从1 Mbit/s至11 Mbit/s

(4) 5GHz, 正交频分复用 (O F D M) , 最高至54 Mbit/s

(5) 2.4 G H z, 直接序列扩频或O F D M, 最高至54 Mbit/s

其中关于5GHz无线局域网OFDM的标准的参数如表1所示。

3.2 不同的传输方式的峰均比率 (PARP)

图1用互补累积分布函数结果来表示不同的调制方式不同的码率的OFDM系统峰均比率的结果。从图中可以得到, 64QAM, 码率为3/4的编码方法比其他两种编码方法有可能带来相对高的峰均比率, 说明随着码率和多进制信号调制的增加, 系统的峰均比有稍微的增大。但由于传输子载波的数目固定, 因此3种编码方法对峰均率比的影响不明显。但总的来说都具有很高的峰均比率。

在Fletcher-Reeves共轭梯度法算法里的最佳步长比较难求。如果每次迭代对步长进行修正的, 会带来计算的复杂度, 因此考虑用代定步长的方法。图2表示在52个子载波、3个不同传输序列条件下达到最佳点的时候, 迭代次数与选择步长的关系;图3表示以不同步长来解决峰均比的结果。从图2, 图3可以看出, Fletcher-Reeves共轭梯度法算法对步长要求非常苛刻:步长太小, 虽然能够很有效地降低峰均比, 但迭代次数会相应增加;步长太大, 峰均比降低效果不好, 而且迭代次数不稳定, 这是因为步长过大即可能过早跳出循环, 也可能增加找寻最佳点的次数。所以我们必须选择一个折中点。通过多次仿真发现步长绝对值在0.005~0.01之间效果比较稳定。

图4, 图5, 图6在5GHz无线局域网OFDM的标准下, 用Fletcher-Reeves共轭梯度法算法来降低信号的PA R的结果, 它们的方式分别为:1 6-Q A M码率为1/2、64-QAM码率为1/2和用64-QAM码率为3/4, 选取步长=0.008。从图中可以看出, 经过3~5次迭代, 3种编码方法信号的峰均比都能够成功地压制在3 dB左右, 说明用Fletcher-Reeves共轭梯度法算法方法做无约束极小化能够很有效地降低系统信号的PAR, 而且可以看出在子载波固定的情况下码率和调制方式对算法的影响不大。

图7, 图8分别是16QAM和64QAM的星座图上的变化。从图中可以看出用Fletcher-Reeves共轭梯度法算法去寻找最佳点, 通过障碍函数B (X) 的限制, 16QAM和64QAM星座点能够很好地控制在判别的范围内, 并且均匀地分布在原信号附近, 而且有效地降低系统的PARP;对于空子载波并没有受到星座图的限制。

4 结论

主要介绍了如何在IPM思想算法下, 用FletcherReeves共轭梯度法算法来解决OFDM的PAR问题。通过OFDM的5GHz无线局域网标准下的仿真实验可得, 在星座向量级误差限制下, Fletcher-Reeves共轭梯度法算法能够有效地找到最佳的星座点, 但是它也带来了一定的计算复杂。随着子载波数的增加, Fletcher-Reeves共轭梯度法算法的最佳步长会变得越来越难求。因此考虑用代定步长的方法。来解决它的步长问题, 通过多次实验发现步长绝对值取在0.005~0.01之间的时候效果比较明显。

附录:

B (x) 的表达式:

上述式子的X*∈Cn表示每次迭代后得到的新星座点。X0∈Cn表示理想的星座点, 根据星座范围和子载波的数目来决定。那么∇f (x i) 的表达式为:

其中

向量b (i) =[ℜfi1, -ℑfi1, ℜfi2, -ℑfi2, ......ℜfin, -ℑfin], 向量e等同于 (7) 式, b (max) , e (max) 两向量对应的都是最大峰值的傅立叶系数;A (j) =Nj;B (j) =MjE (:, i) =b (i) T;H (:, i) =e (i) T;从上式 (14) 可以看到求导之后变为分母, 所以每次迭代后要选取一个∂, 使才保证分母大于零, 运算才可行。

参考文献

[1]卢光跃, 邵朝, 周诠.OFDM系统新的无损峰均值比降低方案, 通讯学报.2005

[2]F.H.Raab, P.Asbeck, S.Cripps, P.B.Kenington, Z.B.Popovi′c, N.Pothecary, et al., “Power amplifiers and transmitters for RF andmicrowave, ”IEEE Transactions on Microwave Theory and Techniques, vol.50, no.3, pp.814–826, Mar.2002

[3]L.J.Cimini, Jr.and N.R.Sollenberger, “Peak-to-average power ratio reduction of an OFDM signal using partial transmit sequences, ”IEEE Communications Letters, vol.4, no.3, pp.86–88, Mar.2000.

[4]J.Armstrong, “Peak-to-average power reduction for OFDM by repeated clipping and frequency domain filtering, ”Electronics Letters, vol.38, no.5, pp.246–247, Feb.2002

[5]A.Jayalath and C.Tellambura, “Peak-to-average power ratio of IEEE802.11a PHY layer signals, ”in Proc.International Symposium on DSP for Communication Systems, Australia, Jan.2002, pp.31–36.

[6]A.Aggarwal and T.H.Meng, “Minimizing the peak-to-average power ratio of OFDM signals via convex optimization, ”in Proc.IEEE Globe-com Conference, vol.4, San Francisco, CA, Dec.2003, pp.2385–2389.

[7]A.Aggarwal and T.H.Meng, “A convex interior-point method for optimal OFDM PAR reduction, ”in Proc.IEEE International Conference on Communications, vol.3, Seoul, South Korea, May2005, pp.1985–1990.

[8]Babak Hassibi and Haris Vikalo, “On the Sphere-Decoding Algorithm I.Expected Complexity”in IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL.53, NO.8, AUGUST2005

[9]S.Boyd and L.Vandenberghe, Convex Optimization.Cambridge University Press, 2003.[Online].Available:http://www.stanford.edu/_boyd/cvxbook.htm.

[10]M.S.Lobo, L.Vandenberghe, S.Boyd, and H.Lebret, “Applications of second-order cone programming, ”Linear Algebra and Its Applications, vol.284, no.1-3, pp.193–228, Nov.1998.[Online].Available:http://www.

[11]A.Aggarwal and T.H.Meng, “Minimizing the Peak-to-Average Power Ratio of OFDM Signals using Convex Optimization”IEEE Transactions on Signal Processing, v54, n8, August, 2006, p3099-3110

[12]LIAN Shujun, WANG Changyu and LI Jibao“Convergence Properties of Conjugate Gradient Methods”工程数学学报2003

共轭梯度算法 篇2

Armijo型线搜索下一种共轭梯度法的收敛性

对无约束非线性规划问题,本文分别在两种不同的.Armijo型线搜索下证明了Liu-Storey共轭梯度法的所有搜索方向都是充分下降的,并进一步证明了该算法是全局强收敛的.对另一种放松了函数值下降条件可以获得更大步长的Armijo型线搜索,本文还证明了该算法是全局强收敛的.

作 者：周光明 ZHOU Guang-ming 作者单位：湘潭大学数学与计算科学学院,湘潭,411105刊 名：工程数学学报 ISTIC PKU英文刊名：CHINESE JOURNAL OF ENGINEERING MATHEMATICS年，卷(期)：200825(3)分类号：O221.1关键词：共轭梯度法 Armijo型线搜索 收敛性

共轭梯度算法 篇3

关键词 无约束优化；谱共轭梯度法；下降性；全局收敛

中图分类号 O224 文献标识码 A

1 引 言

1952年Hestenes和Stiefel提出求解线性方程组Ax=b（x∈Rn）的共轭梯度法.当矩阵A对称正定时，解此方程组等价于求n元二次函数

的极小值点，1964年Fletcher和Reeves将该方法推广应用于解决非线性无约束优化问题，得到求一般函数极小值的共轭梯度法.因具有结构简单、计算机存储需要小等优点，共轭梯度法已经发展成为科学、工程、经济等领域中求解大规模优化问题的一类有效方法，至今对其研究依然很活跃.

考虑无约束优化问题

共轭梯度算法 篇4

关键词：BP神经网络,Matlab,神经网络工具箱,共轭梯度

0 引 言

人工神经网络(ArtificialNeuralNetwork,ANN)是基于模仿生物大脑的结构和功能而构成的一种信息处理系统。它具有大规模并行数据处理能力,分布式存储能力,自适应学习能力等特性,已经广泛应用于信息处理,模式识别,智能控制及系统建模等领域。尤其是基于误差反向传播(Back-Propagation,BP)算法的多层前馈网络,即BP网络是目前应用最多的神经网络[1,2,3]。近年来为了克服标准BP神经网络收敛速度慢,易陷入局部最小值,学习过程会出现震荡等缺点,出现了一系列的改进算法[4,5]。应用Matlab集成的神经网络工具箱(NeuraNetworkToolbox,NNTool)只需掌握网络学习训练函数就能实现算法的仿真,其中提供了丰富的网络学习和训练函数,而且包括了各种常用的神经网络改进算法[6,7]。这为神经网络的仿真提供了极大的方便。节省了程序设计,调试及网络学习训练所需的时间,提高了研究的效率。在此利用简单程序及函数对两种BP神经网络算法做了对比讨论。

1 BP神经网络两种算法

1.1 BP神经网络的梯度下降法

函数的梯度方向指向该函数增加最快的方向,因而函数沿负梯度方向下降得最快,为此取负梯度方向作为下降算法的方向。对于给定的目标函数f[$\overrightarrow{z}$],函数沿负梯度方向下降的最快,所以从任意选定的初始点出发,每次搜索方向沿着目标函数在该点的负梯度方向进行。从迭代点$\overrightarrow{z}$(k)出发,沿着负梯度方向$\overrightarrow{s}(k)=-\nabla f[\overrightarrow{z}(k)]$进行一维搜索,这里ᐁf[$\overrightarrow{z}$(k)]为点$\overrightarrow{z}$(k)的梯度向量,得到下一个迭代点$\overrightarrow{z}(k+1)=\overrightarrow{z}(k)+\overrightarrow{a}(k)\overrightarrow{s}(k)‚\overrightarrow{a}(k)$为最优步长,终止条件为梯度模满足一定的精度$\parallel \text{Δ}\overrightarrow{z}(k)\parallel <\epsilon$,这就是梯度法。梯度法的优点是方法简单,每迭代一次的工作量小,所要求的存储量少,但是梯度法是以某点的负梯度方向作为搜索方向的,因此常不能指向最优点,为此引入了共轭梯度法[8,9,10]。

1.2 BP神经网络的共轭梯度法

共轭梯度法是一种改进搜索方向的方法,它是把前一点的梯度乘以适当的系数,加到该点的梯度上,得到新的搜索方向。因此,可以说共轭梯度法是把过去的梯度和现在某点的梯度信息综合利用,用它的线性组合来构造更好的搜索方向。共轭梯度算法的Fletcher-Reeves算法(Traincgf)如下:

$\overrightarrow{z}(k+1)=\overrightarrow{z}(k)+\overrightarrow{a}(k)\overrightarrow{\mathit{s}}(k)(1)$

式中:搜索方向$\overrightarrow{\mathit{s}}$(k)是一组共轭向量;$\overrightarrow{a}$(k)是步长,且:

$\begin{array}{l}\overrightarrow{\mathit{s}}(k+1)=-\overrightarrow{g}(k)+\beta (k)\overrightarrow{\mathit{s}}(k)\\ \beta (k)=\frac{[\overrightarrow{g}(k+1)]{}^{\text{Τ}}\overrightarrow{g}(k+1)}{[\overrightarrow{g}(k)]{}^{\text{Τ}}\overrightarrow{g}(k)}\end{array}$

式中:$\overrightarrow{g}(k)=\nabla f[\overrightarrow{z}(k)]$。

函数traincgf的训练参数包括:epochs,show,goal,time,min_grad,max_fail,srchFcn,scal_tol,alpha,beta,delta,gama,low_lim,maxstep,minstep,bmax。其中参数srchFcn表示线性搜寻函数。

2应用Matlab神经网络工具箱对上述两种BP算法的分析比较

(1) 建立图1所示形式1-35-1 BP神经网络逼近函数:

$f(x)=\sin (2\text{π}x)+\cos (2\text{π}x)(2)$

在图1所示形式的1-35-1网络中:输入神经元1个,中间层35个,输出层1个;中间层传递函数为正切S形函数tansig;输出层传递函数为线性函数purelin。

(2) 梯度下降算法程序:

程序运行结果如图2所示。

(3) 共轭梯度算法程序:

程序运行结果如图3所示。

对比图2与图3,直观显示共轭梯度算法收敛只需135步,而传统梯度下降算法用了14 044步,可以看出:共轭梯度算法比传统梯度下降算法在收敛速度上提高了两个数量级从而印证了共轭梯度算法的优越性。

3 网络容错泛化能力的进一步测试

进一步对上述两训练后网络各自相应位置的一个权值调整10%,即对网络进行一定程度的破坏,再以另外一组检验数据对进行测试,检验其泛化能力。其中,检验数据对由如下语句生成:

p=[-1:.08:1];

t=sin(2*pi*p)+cos(2*pi*p)。

测试函数采用Matlab工具箱中 postreg函数。函数postreg利用了线性回归的方法,分析了网络输出和目标输出的关系,即网络输出变化相对于目标输出变化的变化率,从而评估了网络的训练结果。梯度下降算法程序和共轭梯度算法程序运行后可以用如下指令:

a=sim(net,p);

[m,b,r]=postreg(a,t)

运行结果如图4和图5。

其返回值m和b分别表示最优回归直线的斜率和y轴截距。当m等于1,b等于0的时候,网络输出与目标输出完全相同,此时的网络具有最优的性能。r表示网络输出与目标输出的相关系数,它越接近于1,表示网络输出与目标输出越接近,网络性能越好。

由图4,图5看到两种算法的容错泛化能力都很好,两图中A为网络输出T为目标输出;两图中m值分别为0.988和0.994都接近1;b值分别为-0.026和-0.023 5都接近0;而r值分别为0.993和0.994都接近1。既从另一角度印证了ANN对自身小的损伤的容错能力,更说明了共轭梯度算法在大幅提高训练速度同时保持了良好的泛化能力。

4 结 语

从前面的分析结果,可以看出共轭梯度算法有着梯度下降法所无法比拟的优点。共轭梯度算法收敛的速度比梯度下降法快两个数量级,采用共轭梯度算法同时保持了良好的泛化能力,所以对于训练具有大规模权值的BP神经网络是一个非常好的选择。

参考文献

[1]周开利,康耀红.神经网络模型及其Matlab仿真程序设计[M].北京:清华大学出版社,2005.

[2]张磊,胡春,钱锋.BP算法局部极小问题改进的研究发展[J].工业控制计算机,2004,17(9):33-34.

[3]吕俊,张兴华.几种快速BP算法的比较研究[J].现代电子技术,2003,26(24):96-99.

[4]Hecht-NielsenR.Theory of the Back Propagation Neural-network[A].Proc.of IJCNN[C].1989.

[5]刘晋刚,李华玲,韩燮.BP神经网络改进算法的应用[J].华北工学院学报,2003,23(6):449-451.

[6]苏高利,邓芳萍.论基于Matlab语言的BP神经网络的改进算法[J].科技通报,2003,19(2):130-135.

[7]闻新,周露,李翔,等.Matlab神经网络仿真与应用[M].北京:科学出版社,2003.

[8]王贇松,许洪国.快速收敛的BP神经网络算法[J].吉林大学学报:工学版,2003,33(4):79-84.

[9]胡金滨,唐旭清.人工神经网络的BP算法及其应用[J].信息技术,2004(4):1-4.

[10]王红霞.神经网络BP算法在网络搜索中的应用[J].微计算机信息,2007,23(15):101-102.

共轭梯度算法 篇5

电容层析成像 (Electrical Capacitance Tomography, ECT) 技术是基于电容敏感场特性的一种过程层析成像技术。其基本原理是:根据不同多相介质具有不同的介电常数这一物理特性, 通过电容传感器阵列形成一个旋转的空间敏感场, 然后从不同方向的观测视角对包含多相介质的管道进行快速扫描, 获得被测管道的各相介质的介电常数分布情况。在此基础上, 运用一种合适的图像重建算法, 显示出被测管道的二维或三维介质分布图像。

电容层析成像技术不仅在实验室研究, 而且在工业生产应用中, 都展示出良好的应用前景。目前, 电容层析成像技术被广泛应用于国内外各类行业的工业生产中, 如:不同流型下的空隙率测量及其流型辨识、矿石, 水泥, 谷物, 煤粉等的气力输送过程、火焰成像、冻土样品中的物质分布及动态变化过程可视化等。

1 研究原因分析

电容层析成像技术的研究, 关键在于以下2点:

(1) 获得更多、更准确的被测物场介质分布信息; (2) 寻求一种速度与精度更高的图像重建算法。介质分布信息的获取受硬件条件的限制较多, 因此, 对图像重建算法的研究, 寻找一种重建图像速度和重建图像质量都能满足工业应用要求的图像重建算法是十分必要的。在图像重建领域, 信赖域方法是一类新颖的研究方向[1], 本文在共轭梯度算法基础上, 提出一种基于信赖域技巧的共轭梯度算法, 提高了成像速度与质量。

2 算法的提出

2.1 共轭梯度算法

共轭梯度 (CG) 法介于最速下降法与牛顿法之间的一个方法, 最初由Hesteness和Stiefel在求解线性方程组过程中提出的。由于其具有较好的收敛性和稳定性, Fletcher和Reevesd等人后来把该算法用于求解一般目标函数的极小值。

共轭梯度算法求解图像恢复问题, 即求下面的离散化问题:

式中:K∈Rm2×n2为一对称正定矩阵, f∈Rn2为待求的输入, h∈Rm2为测量或观测到的输出。

这里的目的是使:

即, 极小化目标函数:

显然目标函数是二次型, 可表达为:

其梯度和Hessianz阵可以显式地计算为:

共轭梯度法本身是一种迭代法, 同时也是一种Krylov子空间方法, 该算法的优点在于, 它可以将复杂问题转化为阶段性的易于计算的子问题。但是其迭代终止条件是要求梯度足够小, 这样需要很多次迭代才能够完成, 使得算的解远远偏离于原问题的真实解。

2.2 基于信赖域法的共轭梯度方法

信赖域方法是这样的一类方法, 它在确保问题全局收敛的情况下还要求问题在局部具有快速收敛性。信赖域方法求解式 (3) , 首先需要求解以下的信赖域子问题 (TRS) :

在信赖域算法的每一次迭代过程中, 都需要精确和非精确地求解子问题式 (6) 来获得下一次迭代点的一试探步。取目标函数的下降量和对逼近模型的预估下降量的比值r作为检测试探步是否值得依赖的标准。

令sk为式 (6) 的一预估解, 记为:

为逼近模型的预估下降量;记:

为目标函数的预估下降量。

则:

用rk的大小来判定是否接受信赖域试探步以及是否调整信赖半径。对于二次模型问题, 发现比值rk≡1。根据目标泛函的极小化过程, 泛函值J[fk+sk]至少不会比J[fk]更差。因此, 不管目标泛函下降量多少, 总是接受试探步sk, 这样可以不放弃求得的任何一个好点。

3 数值测试

仿真电容层析成像系统设计为半径200 mm管道型结构, 激励和检测功能由8电极电容传感器完成, 因此可获得28个测量值, 利用有限元法将被测场剖分成512个单元。设置4种典型流型分布用于仿真试验:二气泡、中心流、单气泡、环状流采用共轭梯度法和带有信赖域技巧的共轭梯度算法进行图像重建, 并在同一条件下, 比较两种算法在成像质量和成像速度上效果, 得出表1, 表2中的测试数据。

%

s

4 结语

本文针对共轭梯度算法提出了一种基于信赖域技巧的共轭梯度算法, 并应用Matlab软件进行了算法实现。实验结果表明, 基于信赖域的共轭梯度算法相比共轭梯度算法在成像速度上与成像质量上都有了很大的提高, 为图像重建提供了一种有效的更精确的算法。

摘要：图像重建算法是电容层析成像系统研究的关键技术, 寻找一种重建图像速度和重建图像质量都能满足工业应用要求的图像重建算法是十分必要的。基于信赖域方法的共轭梯度算法是在普通共轭梯度算法的基础上提出的一种新的图像重建算法, 提高了图像重建的质量与速度。

共轭梯度算法 篇6

关键词：共轭梯度法,OpenMP解决方案,并行加速

1 前言

共轭梯度法 (Conjugate Gradient) 是解决最优化问题的常见方法。 其计算难易程度和实现规模介于最速下降法与牛顿法之间。 共轭梯度法仅利用一阶求导, 克服了收敛慢 (比如最速下降法) 的缺点, 又避免了需要存储和计算多极值矩阵并求逆 (比如牛顿法) 的缺点, 共轭梯度法即是解决大型线性方程组最有用的方法, 也是解大型非线性最优化最有效的算法之一。 在各种优化算法中, 共轭梯度法是非常重要的一种。 其优点是所需存储量小, 具有步收敛性, 稳定性高, 而且不需要任何外来参数。

在天气动力、 物理海洋等数值计算中方法的使用线性和非线性共轭梯度法, 解决各种问题, 比如陈红霞等[1]利用非线性共轭梯度法在东海黑潮流计算中的应用实现海洋数据的比对检验, 张少波等[2]利用预处理共轭梯度法在实现VVP三维风场反演中的应用等。 在此过程中均发现随着计算规模的不断发展和历史资料的大量积累, 共轭梯度法的计算量大幅度提高, 甚至成为利用该方法实现业务化应用的瓶颈。 为此, 选取常用的并行优化方法Open MP技术, 对共轭梯度法进行并行加速优化, 为共轭梯度法的广泛应用提供了新的计算解决方案。

2 问题提出

2.1 共轭梯度法

共轭梯度法于1952 年为求解线性方程组而提出的。 后来, 人们把这种方法用于求解无约束最优化问题, 使之成为一种重要的最优化方法。 共轭梯度法的基本思想是把共轭性与最速下降方法相结合, 利用已知点处的梯度构造一组共轭方向, 并沿这组方向进行搜素, 求出目标函数的极小点。 根据共轭方向基本性质, 这种方法具有二次终止性。

2.2 算法原理

共轭梯度法算法如下:

假设选取x0作为Ax=b的解的初始猜测值, 与之对应的残差为r0=b-Ax0, 则p0=r0, 设循环变量k=0, 即开始如下循环:

如果残差已经足够小, 则推出循环, 否则继续。

3 设计与实现

3.1 Open MP简介

用于并行程序开发的编程模型主要分为两类: 消息传递模型和共享主存模型。 共享主存模型使程序员可以不必进行数据划分和分布, Open MP (Open Multi Processing) API规范, 是用户对共享主存编程模型最新要求的全面反映, 可解决旧规范的种种局限性。 Open MP使用fork-join并行机制, 程序开始串行执行, 此时只有一个主线程, 然后在遇到用户定义的并行区域时创建出一组线程。 在并行区域之内, 多个线程可以执行相同的代码块, 或使用工作共享结构体并行执行不同的任务[3]。

3.2 实验数据

实验数据文件input.txt中存储了矩阵A和b。 其中矩阵A是一个83334 乘83334 的矩阵, 非0 元素共有6010480 个, 数据稀疏度为0.085%。 数据存储为文本文件, 第一个元素是行 (列) 数N, 第二个元素是非0 元素的个数length。 接下来是length个三元组数据 (行优先, 即每个数据的行号不会大于之前数据的行号) , 三元组里分别是数据A [i] [j] 的行号i、 列号j、 值val, 存储格式为int, int, double。 再接下来是N个随机生成的double值, 分别是b的每一维。

3.3 并行实现

采用Open MP实现并行化。 可并行化的地方有:

(1) 向量加法。 形如xk+1=xk+∝kPk的操作由于每一维间没有影响, 因此可以并行化。 如图1 所示

(2) 矩阵向量乘法。 迭代中需要计算APk, 这里使用行划分来进行并行计算, 则每个CPU处理器只需要得到A的第行与Pk则可得到最终结果APk的第i维。 又因为APk在计算中出现了两次, 因此采用一个矩阵存储下来, 节约计算时间。如图2 所示。

(3) 向量的点积。 形如的向量点积运行可以利用并行来实现, 由于最终是个累加操作, 可以使用Open MP中的re duction函数实现。 如图3 所示。

3.4 构建稀疏矩阵

稀疏矩阵的Open MP核心实现代码如下

3.5 结果与分析

(1) 并行程序的正确性

利用多批次小规模的数据测试后, 并行程序运结果保持二进制一致, 并行化并没有影响结果的正确。

(2) 并行程序的加速性和可扩展性

由于数据规模比较大, 迭代次数比较多, 因此对100 次迭代循环总时间进行计时, 再得到每次循环的平均运行时间。计算性能如下:

串行程序的每次循环平均运行时间为12.5 秒。 并行程序在1、 2、 4、 8 个CPU核的每次循环平均运行时间如表1 所示。

4 结语

大规模计算的性能优化是天气动力、 物理海洋等数值计算中的主要问题, 随着业务化需求的增大, 计算规模越来越大, 性能优化成为瓶颈问题。 利用Open MP技术对共轭梯度法中最多的向量加、 向量乘和向量点积进行分析, 并进行了测试实验, 达到了预期效果, 确认Open MP并行优化是共轭梯度法广泛应用的一种较好的计算解决方案。

参考文献

[1]陈红霞, 袁业立, 刘娜, 等.非线性共轭梯度法在东海黑潮流计算中的应用[J].海洋学报, 2003, 25 (6) :31-38.

[2]张少波, 胡明宝, 张鹏, 等.预处理共轭梯度法在VVP三维风场反演中的应用[J].气象学报, 2004, 24 (8) :303-308.

LP鞍点共轭梯度法的研究与实现 篇7

1 鞍点算法

定义:若满足如下条件

Z (X*, λ*) ≥Z (X, λ*) X≥0

Z (X*, λ*) ≤Z (X*, λ) λ≥0

点 (X*, λ*) , X*≥0, λ*≥0则被称为鞍点。

研究如下线性规划问题

(P) max f (x) = cTx

s.t. Ax+b=0 X≥0

其中c, x∈En;b∈Em;A为m×n阶矩阵;m≤n。

(P) 问题的对偶问题是

(D) min F (λ) = bTλ

s.t. ATλ+c≥0

其中λ∈Em。

问题 (P) 所对应的拉格朗日方程是:

Z (x, λ) = λTAx+cTx+λTb

这是一个超鞍面, 如果 (x*, λ*) 是鞍点, 那么下式肯定成立,

Z (x*, λ*) =max z (x, λ*) =min z (x*, λ)

亦即 (x*, λ*) 是满足方程组

undefined

的某一点故x*为 (P) 问题的最优解, λ*为 (D) 问题的最优解。

根据鞍面方程的几何解释和上述公式我们可得到如下的公式:

undefined

由上述公式可得公式 (2) ::

undefined

设

undefined

根据以上公式进行迭代可推出:

undefined

假设g是矩阵A AT的特征根, 0≤g1≤g2…≤gm, 只要选择适当的步长ρ1, ρ2, 例如:undefined, 就可使矩阵M的特征根TM<1, 从而保证鞍点问题的收敛性[1]。

2 共轭梯度法

定义:设A为n×n阶对称正定阵, 若非零向量组P (1) , P (2) , …, P (n) ∈满足条件:P (i) TAP (j) =0 (i≠j;i, j=1, 2, …, n) 则称该向量组为A共轭。

定义:无约束极值问题的一个特殊情形是undefined, 式中A为n×n阶对称正定阵;x, B∈En.称为正定二次函数极小问题。

定理:设向量P (i) , i=0, 1, 2, …, n-1, 为A共轭, 则从任一点x (0) 出发, 相继以P (0) , P (1) , …, P (n-1) 搜索方向的下述算法:

undefined

经n次一维搜索收敛于正定二次函数的极小点x*。

共轭梯度法的计算过程如下:

①选择初始近似点x (0) , 取初始方向为负梯度方向, 即p (0) =-∇f (x (0) )

②一般地, 假定已得出x (t) 和P (t) , 则可计算出第t+1次近似点

x (t+1) :x (t+1) =x (t) +λtP (t) )

λt:minf (x (t) +λP (t) ) )

③根据t+1点处的梯度∇f (x (t+1) ) 和A共轭向量p (t) 合成共轭梯度方向P (t+1) , 并转向下一次迭代。

3 鞍点共轭梯度法

当迭代点逼近到鞍点附近时, 由于梯度变小, 收敛速度逐渐变慢, 这时需要采用共轭梯度方向逼近鞍点。

设:

undefined

当t=0时, 设

undefined

任取初始近似点 (x (0) , λ (0) ) , 并取初始搜素方向为W (0) ;即:P (0) =W (0) ;由 (3) , (4) 式可得:R (1) =R (0) +ρ (0) UP (0) , 其中;

‖R (1) ‖2=‖R (0) ‖2+2ρ (0) RT (0) UP (0) +ρ2 (0) ‖UP (0) ‖2

选择ρ (0) , 使‖R (1) ‖2最小。

则,

undefined, 则

undefined

当t=1时,

undefined

P (1) 为共轭梯度方向, 它为当前点的中间点梯度向量W (1) 和前点的迭代方向P (0) 的合成:

P (1) =W (1) +β (0) P (0) (6)

β (0) 为待定系数, 由它保证P (1) 与P (0) 为UUT共轭, 即PT (1) P (0) =0再由 (5) 式得: (WT (1) +β (0) PT (0) ) UTUP (0) =0;所以undefined, 再由 (3) 和 (5) 得:则:R (2) =R (1) +ρ (1) UP (1) ;

‖R (2) ‖2=‖R (1) ‖2+2ρ (1) UP (1) +2ρ (1) ‖UP (1) ‖2=0;

可得:undefined;

以此类推下去可得:

undefined

完整的鞍点共轭梯度法公式如下:

undefined

ρ1为中间点迭代步长, 可取任意整数, 一般取较大值时精度较高。

4 实验结果

鞍点算法和鞍点共轭梯度法运行情况如下表, 以下数据是从美国贝尔实验室数据库中抽取。运行环境为Pentium (R ) 4 CPU2.40GHz, 内存512MB, 硬盘80G。

摘要：在线性规划问题中, 为了提高算法的求解速度, 快速得到最优解。对鞍点算法, 共轭梯度法进行了深入研究与分析。针对鞍点算法在逼近鞍点时收敛速度变慢的缺陷, 将计算比较简单且有限步迭代即可收敛的共轭梯度法成功的应用于鞍点算法中形成了一种新的算法—鞍点共轭梯度算法。以c++为开发工具, 在计算机上实现了该算法, 并编成一个解题系统能够快速求解线性规划问题。实验结果表明相对于鞍点算法, 用鞍点共轭梯度算法计算, 解题时间效率明显提高。

关键词：鞍点算法,梯度方向,共轭梯度法,鞍点共轭梯度法

参考文献

[1]尚毅.一种新的线性规划迭代算法—鞍点逼近算法[J], 计算机研究与发展, 1989 (8) .

[2]尚毅, 张国光, 邵和平.鞍点梯度法、鞍点共轭梯度法[J], 计算机研究与发展, 1990 (5) .

[3]邵和平, 成孟金, 张国光, 等.CNJK线性规划鞍点算法原理及理论分析[J], 沈阳化工学院学报, 1994, 8 (4) .

[4]邵和平, 成孟金, 张国光, 尚毅.CNJK鞍点共轭梯度法[J], 沈阳化工学院学报, 1995, 9 (2) .

[5]尚毅, 张国光, 成孟金.一种新的解决大规模线性规划问题的实用算法[J], 沈阳化工学院学报, 1996, 10 (3) :209-222.

[6]SHANG Yi, CHENG Meng-jin, ZHANG Guo-guan等, Principle and Computational Experience of a Saddle PointAlgorithm for Linear Programming[J], 沈阳化工学院学报, 2004, 18 (2) :138-143.

[7]尚毅, 成孟金, 张国光.LP鞍点算法收敛性分析[J], 沈阳化工学院学报, 2000, 14 (4) .

[8]张国光, 富晓雷.新型线性规划解题器[J], 系统工程, 2005, 23 (10) :117-121.

[9]Luenberger D G.夏尊铨等译, 线性与非线性规划引论[M], 北京:科学出版社, 1982.

共轭梯度法在膜结构分析中的应用 篇8

力密度法应用于膜结构分析时建立的方程组如下:

其中,C为结构的拓扑矩阵;Q为力密度矩阵;Px,Py和Pz均为节点荷载,具体推导详见文献[1][2]。随着结构网格划分的增加,总结点数变大,力密度法方程组阶数升高,膜结构分析的最终问题就归结为大型线性方程组的求解上。C矩阵本身是含有大量零元素的稀疏矩阵,并且本文通过推导证明,该方程组具有对称正定的特点,所以,本文提出可利用其方程组的结构特性进行算法优化,以提高计算程序的效率。

一般来说,解线性方程组Ax=b有两种数值分析方法:1)直接法。但直接法涉及到系数矩阵的分解,当A为大型稀疏矩阵时,因为所要求的分解因子是稠密的,直接法的效率不高甚至难以实现。2)迭代法。这类方法是生成近似解序列{x(k)},矩阵A只在矩阵向量乘法时才用到,而稀疏矩阵的乘法已相当成熟。数值方法的一个基本原则是:求解任一问题都应利用其方程组的结构特性,下面将介绍一种迭代解法——共轭梯度法,其优点正好体现于求解稀疏、对称及正定的方程组的效率上。

2 共轭梯度法在力密度方程组求解中的应用

2.1 力密度方程组的对称正定性

根据式(1),设任意n为向量p,且力密度矩阵Q为对角矩阵,其中对角元素q(i,i)>0,(i=1,n),则:

所以方程组系数矩阵(CTQC)为对称正定矩阵。

2.2 共轭梯度法

设A为对称正定,定义函数$\phi (x)=\frac{1}{2}(Ax,x)-(b,x)$,并求x∈Rn,使φ(x)最小,按文献[4],这是等价于求解方程组Ax=b的变分问题,求解的方法是构造一个向量序列{x(k)},使φ(x(k))→minφ(x)。

minφ(x)最简单的方法是最速下降法。对当前点xc,φ(x)在负梯度方向-∇φ(x)=b-Ax上下降最快。我们称rc=b-Axc为残量。如果残量非零,则存在一正数α=(rTcrc)/(rTcArc),使得$\phi (x{}_c+\alpha r{}_c)=\phi (x{}_c)-\alpha r{}_c^{\text{Τ}}r{}_c+\frac{1}{2}\alpha {}^{2}r{}_c^{\text{Τ}}Ar{}_c$达到最小。最速下降法是可以保证收敛,但却不能保证收敛速度。文献[4]中提出,如果搜索方向{p1,…,pk}是A共轭的(即是对所有的i≠j,有pTiApj=0),则搜索方向是线性无关的,且xk为以下公式的解minφ(x)(x∈x0+span{p1,…,pk}),就能保证最多n步就收敛到真解。而这种结合了最速下降法和A共轭搜索方向法优点的迭代方法就是共轭梯度法。

3 算例分析

根据以上算法,本文编制了相应的程序,并进行了算例分析。

本算例为马鞍形膜结构,采用矩形网格划分,划分间距为0.5 m,膜面预应力为1.0 kN/m,膜网内部力密度值为1.0 kN/m,边索力密度值为14.0 kN/m。结点总数为552,其中4个为固定结点,坐标分别为99 000 001(12,16,4),99 000 002(3,10,0),99 000 003(12,1,4),99 000 004(20,9,0)。单元总数1 000,其中“T”单元总数为128。

本文编制的程序计算迭代166次,满足终止准则‖r‖2<1×e-6。图1,图2分别给出结构网格划分、几何零状态时与找形后的平衡形状的对比,表1,表2分别给出了共轭梯度法和Gauss消去直接法的结点坐标计算结果及其计算耗时的比较。算例分析表明,本文算法精度高、收敛快,是求解力密度方程组的可靠、高效的数值分析方法,为力密度法应用于大型膜结构分析奠定了坚实的基础。

摘要：基于力密度法应用于膜结构分析时需求解大型线性方程组,并结合该方程组具有稀疏、对称及正定的特点,提出采用共轭梯度法对其进行求解,通过算例分析证明,该算法收敛快、精度高,是求解力密度方程组高效、可靠的数值分析方法。

关键词：共轭梯度法,膜结构,力密度法

参考文献

[1]H.J.Schek.The force density method for form finding and compu-tation of general network[J].Computer Methods in Applied Me-chanics and Engineer,1974(3):115-134.

[2]王勇,魏德敏,高振宇.张拉膜结构力密度法混合找形分析[J].计算力学学报,2005(10):629-632.

[3]郑超,张建海.预处理共轭梯度法在岩土工程有限元中的应用[J].岩石力学与工程学报,2007(7):2820-2825.

[4]G.H.戈卢布,C.F.范洛恩.矩阵计算[M].袁亚湘,译.北京:科学出版社,2001.

共轭梯度算法 篇9

在1998年Barzilai与Borwein[2]提出谱梯 度法. 在2001年Birgin与Martinez[3]把谱梯度法与共轭梯度法结合提出一类新的谱共轭梯度法. 谱共轭梯度法数值试验结果与收敛情况表明,与相应的共轭梯度法相比,谱共轭梯度法更有效[4].

对于无约束优化问题

其中f: Rn→R是连续可微的.

本文构造了一种新的谱共轭梯度法:

在线搜索条件的选择上,在本文中将选择由Grippo等人提出的一种Armijo型的非单调线搜索技术[1]: 令β > 0,γ∈( 0,1) ,取一正的整数M,并且取步长为αk= βγmk,我们要求mk是满足下面不等式的最小的非整数

其中要求0 < σ < 1,并且

m( 0) = 0,0≤m( k) ≤min{ m( k - 1) + 1,M} .

利用Armijo型的非单调线搜索技术构造的谱共轭梯度法的优点在于,数值试验表明该算法具有良好计算效能,也能用于维数较高的无约束优化问题[5 - 6]. 本文证明了新算法不仅具有充分下降性,并在Armijo线搜索下具有全局收敛性.

1. 充分下降性及新的谱共轭梯度算法

为了证明充分下降性,我们首先假设:

( a) 目标函数f( x) 在如下水平集中有界,

L = { x∈Rn| f( x) ≤f( x0) } .

其中x0为初始点.

( b) f在水平集L的开凸集U连续可微,并且它的梯度向量g满足Lipschitz条件,即存在一个常数τ,使得:

‖g( x) - g( y) ‖≤τ‖x - y‖,x,y∈U

根据假设( a) 和( b) ,我们容易知道存在一个常数ν,满足: ‖g( x) ‖≤ν,x∈L. .

定理1. 1考虑迭代方法( 1) - ( 4) ,步长因子ak满足了非单调步长规则( 5) ,

那么存在正常数N,对k≥l,有gTkdk≤ - N‖gk‖.

证明

我们对k分情况考虑如下:

结论成立,

若 gTkdk - 1≠0,则

又由于假设( a) 跟( b) ,我们有存在一个常数v,使得

‖g( x) ‖≤ν,x∈L.

故存在rn > 0,使得有

则由( 6) 和( 7) 有

取μk充分小,存在正常数N0满足k≥1有

假设0 < δk< T,则有

所以

综上,结论成立,

2. 算法算法

算法2. 1

·Step1,给定x1∈Rn,ε > 0,d1= - g1,k: = 1;

·Step2. 如果‖gk‖ < ε,则停止,否则找至αk满足非单调线搜索条件( 5) ;

·Step3. 令xk + 1= xk+ αkdk,若‖gk + 1‖≤ε,则停止,否则转Step4;

·Step4. 由 ( 3) 与 ( 4) 计算βk+ 1和δk,进而计算

·Step5. 令 k: = k + 1,转 Step2.

3. 新算法的全局收敛性

引理3. 1算法产生序列{ xk} ,若对{ δk} 满足0 < ρmin<δk< ρmax,则对k∈N,存在常数H,有

‖dk‖≤H‖gk‖.

证明( ⅰ) 当k = l时,由于d1= - g1,所以我们有‖d1‖ = ‖g1‖,结论显然成立,

( ⅱ) 当k≥2时,由βk的定义和( 7) 我们有

引理3. 2 [7]假设( a) 和( b) 成立,考虑迭代( 1) ( 4) ,为本文算法产生的序列,则有,

定理3. 3假设( a) 和( b) 成立,考虑方法( 1) - ( 2) ,由式( 3) 与( 4) 定义,由单调线搜索条件( 5) 决定,则有

证明假设结论不成立,那么存在着一个常数c > 0,使得

如若,由引理3. 2证明的最后,我们知道,并且由定理1. 1可知,产生矛盾,

如若,那么一定存在着无穷子列I满足条件:

由αk的定义以及γ∈( 0,1) ,我们有αkγ不满足非单调线搜索( 5) ,也就是:

由微分中值定理,Lipchitz条件以及引理3. 1可知,存在一个常数θ,满足

由式( 9) 、( 10) ,我们知道可以得到对任意的k∈I有

又由假设( a) 与( b) ,我们容易知道存在一个常数ν,满足:

‖g( x) ‖≤ν,x∈L

整理式( 11) 我们有

由定理1. 1,我们知道gTkdk< - N‖gk‖2,由上式我们有

由引理3. 2与( 13) ,我们可以得到. 与假设产生矛盾.

综上,结论成立.

4. 结 论

本文结合Grippo等人提出的非单调线搜索技术,给出了一种新的非单调谱共轭梯度法,证明了这种方法在不依赖于线搜索条件的情况下,具有着充分的下降性,并且证明新算法具有全局收敛性.