求解正则化最小二乘问题的一个非精确交替方向乘子法
|
摘要
正则化最小二乘问题广泛出现在图像处理、统计学等领域中,交替方向乘子法(ADMM)是求解这个问题的一种有效方法.ADMM在每一步迭代过程中,都需要求解两个子问题,子问题能否有效地求解对整个算法的有效性有重要影响.在有些情形,精确求解子问题是不可能的,或者是需要花费很大代价的.由于这个原因,非精确地求解子问题的一类算法得到了发展.而已有的非精确类ADMM算法,在迭代过程中需要不断提高子问题解的精度,从而子问题迭代步数也越来越多,这就影响了整个算法的效率.这篇文章提出了一个不精确ADMM算法,该算法的特点是在迭代过程中,子问题的迭代步数是确定的,这克服了之前算法的不足.文章中的数值例子也说明了提出的算法是有效的.
The regularized least squares problems are widely used in image processing,statistics and other field.Alternating direction method of multipliers(ADMM) is an effective algorithm for the problem.The computation of ADMM is dominated by two subproblems at each step,and whether subproblems can be solved effectively have a major impact on the effectiveness of the algorithm.Since the subproblem could be too difficult to be solved exactly in many practical applications,the inexact versions of ADMM are developed.Most existing inexact ADMMs are based on solving subproblems approximately and gradually increasing their precision,which means the precision can become very high after several iterations.In this paper,an easily implementable inexact ADMM with certain iteration number of subproblems is developed.Numerical examples illustrate the proposed algorithm is effective.
The regularized least squares problems are widely used in image processing,statistics and other field.Alternating direction method of multipliers(ADMM) is an effective algorithm for the problem.The computation of ADMM is dominated by two subproblems at each step,and whether subproblems can be solved effectively have a major impact on the effectiveness of the algorithm.Since the subproblem could be too difficult to be solved exactly in many practical applications,the inexact versions of ADMM are developed.Most existing inexact ADMMs are based on solving subproblems approximately and gradually increasing their precision,which means the precision can become very high after several iterations.In this paper,an easily implementable inexact ADMM with certain iteration number of subproblems is developed.Numerical examples illustrate the proposed algorithm is effective.
引文
[1]Ng M K,Wang F,Yuan X.Inexact alternating direction methods for image recovery[J].SIAM Journal on Scientific Computing,2011,33(4):1643-1668.
[2]Eckstein J,Bertsekas D P.On the Douglas Rachford splitting method and the proximal point algorithm for maximal monotone operators[J].Mathematical Programming,1992,55(1-3):293-318.
[3]Boyd S,Paxikh N,Chu E,et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends?in Machine Learning,2011,3(1):1-122.
[4]Varga R S.Matrix iterative analysis[M].Springer Science&Business Media,2009.
[5]Ben-Tal A,Nemirovski A.Lectures on modern convex optimization:analysis,algorithms,and engineering applications[M].Siam,2001.
[6]Hansen P C,Nagy J G,O'leary D P.Deblurring images:matrices,spectra,and filtering[M].Siam,2006.
[7]Parikh N,Boyd S P.Proximal algorithms[J].Foundations and Trends in optimization,2014,1(3):127-239.
[8]Recht B,Fazel M,Parrilo P A.Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J].SIAM review,2010,52(3):471-501.
[9]Toh K C,Yun S.An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[J].SIAM review,2010,15(6):615-640.
[10]Trefethen L N,BauⅢD.Numerical linear algebra[M].Siam,1997.
[2]Eckstein J,Bertsekas D P.On the Douglas Rachford splitting method and the proximal point algorithm for maximal monotone operators[J].Mathematical Programming,1992,55(1-3):293-318.
[3]Boyd S,Paxikh N,Chu E,et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends?in Machine Learning,2011,3(1):1-122.
[4]Varga R S.Matrix iterative analysis[M].Springer Science&Business Media,2009.
[5]Ben-Tal A,Nemirovski A.Lectures on modern convex optimization:analysis,algorithms,and engineering applications[M].Siam,2001.
[6]Hansen P C,Nagy J G,O'leary D P.Deblurring images:matrices,spectra,and filtering[M].Siam,2006.
[7]Parikh N,Boyd S P.Proximal algorithms[J].Foundations and Trends in optimization,2014,1(3):127-239.
[8]Recht B,Fazel M,Parrilo P A.Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J].SIAM review,2010,52(3):471-501.
[9]Toh K C,Yun S.An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[J].SIAM review,2010,15(6):615-640.
[10]Trefethen L N,BauⅢD.Numerical linear algebra[M].Siam,1997.