南京大学学报(自然科学版) ›› 2017, Vol. 53 ›› Issue (4): 693–.

• • 上一篇    下一篇

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

王西平1,刘红卫1,刘泽显1,2*   

  • 出版日期:2017-08-02 发布日期:2017-08-02
  • 作者简介:1.西安电子科技大学数学与统计学院,西安,710126;2.贺州学院数学与计算机学院,贺州,542899
  • 基金资助:
    基金项目:国家自然科学基金(11461021),贺州学院科研课题(2014YBZK06),贺州学院硕士点支撑项目(2016HZXYSX03),广西壮族自治区教育厅(2013YB236) 收稿日期:2017-03-02 *通讯联系人,E-mail:liuzexian2008@163.com

Modified alternating direction method for solving total variation problem

Wang Xiping 1,Liu Hongwei 1,Liu Zexian 1,2*   

  • Online:2017-08-02 Published:2017-08-02
  • About author:1.School of Mathematics and Statistics,Xidian University,Xi’an,710126,China; 2.School of Mathematics and Computer Science,Hezhou University,Hezhou,542899,China

摘要: 基于传统交替方向算法的框架,提出了一种求解全变分问题的修正交替方向算法(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.

[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.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!