|本期目录/Table of Contents|

[1]王西平,刘红卫,刘泽显*.全变分模型的修正交替方向算法[J].南京大学学报(自然科学),2017,53(4):693.[doi:10.13232/j.cnki.jnju.2017.04.011]
 Wang Xiping,Liu Hongwei,Liu Zexian *.Modified alternating direction method for solving total variation problem[J].Journal of Nanjing University(Natural Sciences),2017,53(4):693.[doi:10.13232/j.cnki.jnju.2017.04.011]
点击复制

全变分模型的修正交替方向算法()
     

《南京大学学报(自然科学)》[ISSN:0469-5097/CN:32-1169/N]

卷:
53
期数:
2017年第4期
页码:
693
栏目:
出版日期:
2017-08-03

文章信息/Info

Title:
Modified alternating direction method for solving total variation problem
作者:
王西平1刘红卫1刘泽显12*
1.西安电子科技大学数学与统计学院,西安,710126;2.贺州学院数学与计算机学院,贺州,542899
Author(s):
Wang Xiping 1Liu Hongwei 1Liu Zexian 12*
1.School of Mathematics and Statistics,Xidian University,Xi’an,710126,China; 2.School of Mathematics and Computer Science,Hezhou University,Hezhou,542899,China
关键词:
全变分模型交替方向算法非单调线搜索图像重构
Keywords:
total variationalternating direction methodnon-monotone line searchimage recovering
分类号:
TP181
DOI:
10.13232/j.cnki.jnju.2017.04.011
文献标志码:
A
摘要:
基于传统交替方向算法的框架,提出了一种求解全变分问题的修正交替方向算法(modified alternating direction method,MADM).该算法利用当前点的信息和前两个迭代点的信息得到修正的初始BB步长,再结合非单调线搜索技术得到子问题的近似解,在理论上验证了该算法的全局收敛性.最后,将该算法分别在小规模、无噪声和大规模、有噪声的情况下应用于全变分图像重构问题.对重构后的结果,从运行时间、迭代次数、相对误差以及图像的重构效果四个角度进行评价,并与求解全变分问题的交替方向算法(TV minimization by alternating direction algorithms,TVAL3)进行对比,其数值结果表明了该算法具有更好的收敛速度和重构效果.
Abstract:
Alternating direction methods(ADM)are a class of the effective approaches for solving the convex optimization problems with linear constraint structure.Due to these algorithms can be used to solve the complex large-scale problem into several subproblems,it has attracted the attention of many optimization scholars at home and abroad,and has become particularly important in the field of image processing,compress sensing,physics and economics et al.However,without further special structures,it is excessively expensive to solve those realistic problems accurately.To address this issue,this paper considered a modified alternating direction method(MADM)to solve total variation problem,which could be viewed as an extension of the particular alternating direction method for minimizing total variation problem,called TVAL3.In the proposed method,a novel strategy for choice of the initial BB(Barzilai-Borwein)stepsize was introduced to improve the convergence speed and guarantee the stability of the algorithm.The modified initial BB stepsize effectively employed the information of the current point and the first two iteration points,which combineed the two gradient directions that was used in the steepest descent method(SD)and BB method.With the uses of the modified initial BB stepsize in the non-monotone line search technique,the approximate solution of subproblems was obtained,and the global convergence of the modified algorithm was also proved by extending existing theoretical results.Finally,in order to test the performance of the proposed algorithm,we applied it to solving problems in image reconstruction problem with total variation regularization under small scale,noiseless and large-scale,noisy.And by comparing MADM with TVAL3 in terms of running time,the number of iterations,the relative error and the effect of reconstruction,the numerical results demonstrate that the proposed method have much better performance in convergence speed and reconstruction effect.

参考文献/References:

[1] Rudin L I,Osher S,Fatemi E.Nonlinear total variation based noise removal algorithms.Physica D Nonlinear Phenomena,1992,60(1-4):259-268. [2] Chan R H,Tao M,Yuan X M.Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers.SIAM Journal on Imaging Sciences,2013,6(1):680-697. [3] Goldfarb D,Ma S Q,Scheinberg K.Fast alternating linearization methods for minimizing the sum of two convex functions.Mathematical Programming,2013,141(1-2):349-382. [4] Yang J F,Zhang Y.Alternating direction algorithms for l1-problems in compressive sensing.SIAM Journal on Scientific Computing,2011,33(1):250-278. [5] Ng M K,Weiss P,Yuan X M.Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods.SIAM Journal on Scientific Computing,2010,32(5):2710-2736. [6] Ng M K,Wang F,Yuan X M.Inexact alternating direction methods for image recovery.SIAM Journal on Scientific Computing,2011,33(4):1643-1668. [7] Ling Q,Shi W,Wu G,et al.DLM:Decentralized linearized alternating direction method of multipliers.IEEE Transactions on Signal Processing,2015,63(15):4051-4064 [8] Nesterov Y E.A method for unconstrained convex minimization problem with the rate of convergence O(1/k2).Soviet Mathematics Doklady,1983,269(3):372-376. [9] Beck A,Teboulle M.A fast iterative shrinkage-thresholding algorithm for linear inverse problems.SIAM Journal on Imaging Sciences,2009,2(1):183-202. [10] Goldstein T,O’Donoghue B,Setzer S,et al.Fast alternating direction optimization methods.SIAM Journal on Imaging Sciences,2014,7(3):1588-1623. [11] Kang M,Kang M,Jung M.Inexact accelerated augmented lagrangian methods.Computational Optimization and Applications,2015,62(2):373-404. [12] Grippo L,Lampariello F,Lucidi S.A nonmonotone line search technique for Newton’s method.SIAM Journal on Numerical Analysis,1986,23(4):707-716. [13] Li C B,Yin W T,Jiang H,et al.An efficient augmented Lagrangian method with applications to total variation minimization.Computational Optimization and Applications,2013,56(3):507-530. [14] Barzilai J,Borwein J M.Two-point step size gradient methods.IMA Journal of Numerical Analysis,1988,8(1):141-148. [15] Raydan M.The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem.SIAM Journal on Optimization,1997,7(1):26-33. [16] Dai Y H,Fletcher R.Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming.Numerische Mathematik,2005,100(1):21-47. [17] Zheng Y T,Zheng B.A new modified barzilai-borwein gradient method for the quadratic minimization problem.Journal of Optimization Theory and Applications,2017,172(1):179-186. [18] Liu H,Liu Z,Dong X.A new adaptive Barzilai and Borwein method for unconstrained optimization.Optimization Letters,2017,DOI:10.1007/s11590-017-1150-9. [19] Liu Z,Liu H.An efficient gradient method with approximate optimal stepsize for large-scale unconstrained optimization.Numerical Algorithms,2017,DOI 10.1007/s11075-017-0365-2.

相似文献/References:

备注/Memo

备注/Memo:
基金项目:国家自然科学基金(11461021),贺州学院科研课题(2014YBZK06),贺州学院硕士点支撑项目(2016HZXYSX03),广西壮族自治区教育厅(2013YB236) 收稿日期:2017-03-02 *通讯联系人,E-mail:liuzexian2008@163.com
更新日期/Last Update: 2017-08-02