在线阅读 --自然科学版 2017年5期《求解绝对值方程组稀疏解的非精确交替方向法》
求解绝对值方程组稀疏解的非精确交替方向法--[在线阅读]
任天, 刘晓红, 牟洋
天津大学 数学学院, 天津 300000
起止页码: 386--391页
DOI: 10.13763/j.cnki.jhebnu.nse.2017.05.004
摘要
寻求绝对值方程组Ax-|x|=b的最稀疏解,该问题被松弛为l1范数最小化问题,进一步松弛为一个约束优化问题.利用非精确交替方向法求解上述约束优化问题,推导出了相关子优化问题的最优解公式,从而大大提高了计算速度.数值实验结果表明该方法是求解绝对值方程组稀疏解非常有效的算法.

Inexact Alternating Direction Method for the Sparest Solution of Absolute Value Equations
REN Tian, LIU Xiaohong, MU Yang
School of Mathematical Science, Tianjin University, Tianjin 300000, China
Abstract:
To find the sparest solution to the absolute value equations Ax-|x|=b,this question is relaxed to a l1-norm minimization problem,and it is further relaxed to a constrained optimization problem.In this paper,the inexact alternating direction algorithm (inexact ADM) is used to solve the above constrained optimization problem,and the optimal solution formulas of the relevant sub optimization problems are derived,this approach imrpoves the calculation speed and numerical experiments show that this approach is very efficient in finding the sparest solution of absolute value equations above.

收稿日期: 2017-03-15
基金项目: 国家自然科学基金(11431002)

参考文献:
[1]CANDÉS E,ROMBERG J,TAO T.Robust Uncertainty Principles:Exact Signal Reconstruction from Highly Incomplete Frequency Information[J].IEEE Trans Inform Theory,2006,52(2):489-509.doi:10.1109/TIT.2005.862083
[2]DONOHO D L.Compressed Sensing[J].IEEE Trans Inform Theory,2006,52(4):1289-1306.doi:10.1109/TIT.2006.871582
[3]ZHOU S L,KONG L C,XIU N H.New Bounds for RIC in Compressing Sensing[J].Journal of the Operations Research Society of China Oper,2013,1(2):227-237.doi:10.1007/S40305-013-0013-Z
[4]ZHANG M,HUANG Z H,LI Y F.The Sparsest Solution to the System of Absolute Value Equations[J].J Oper Res Soc China,2015,3(1):31-35.doi:10.1007/S40305-014-0067-6[LM]
[5]LIU X H,FAN J,LI W J.Concave Minimization for Sparse Solution of Absolute Value Equations[J].Transactions of Tianjin University,2016,22(1):89-94.doi:10.1007/S12209-016-2640-Z
[6]MANGASARIAN O L.Absolute Value Programming[J].Comput Optim Appl,2007,36(1):43-53.doi:10.1007/S10589-006-0395-5
[7]CACCETTA L,QU B,ZHOU G L.A Globally and Quadratically Convergent Method for Absolute Value Equations[J].Comput Optim Appl,2011,48(1):45-58.doi:10.1007/S10589-009-9242-9
[8]MANGASARIAN O L.Absolute Value Equation Solution via Dual Complementarity[J].Optim Lett,2013,7(4):625-630.doi:10.1007/S11590-012-0469-5
[9]MANGASARIAN O L.Absolute Value Equation Solution via Linear Programming[J].Optim Theory Appl,2014,161(3):870-876.doi:10.1007/S10957-013-0461-Y
[10]ECKSTEIN J,BERTSEKAS D.On the Douglas-Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators[J].Math Program,1992,55(1/2/3):293-318.doi:10.1007/BF01581204
[11]HE B,LIAO L,HAN D,et al.A New Inexact Alternating Directions Method for Monotone Variational Inequalities[J].Math Progam,2002,92(1):103-118.doi:10.1007/S101070100280
[12]ZHANG Y,YANG J F,YIN W.A Fast Alternating Direction Method for TVL1-L2 Signal Reconstruction from Partial Fourier Data[J].IEEE J Sel Top Signa,2010,4(2):288-297.doi:10.1109/JSTSP.2010.2042333
[13]GOLDSTEIN T,OSER S.The Split Bregman Method for l1 Regularized Problems[J].SIAM J Imag Sci,2009,2(2):323-343.doi:10.1137/080725891
[14]YANG J F,ZHANG Y.Alternating Direction Algorithms for l1-problems in Compressive Sensing[J]. SIAM J Sci Comput,2011,33(1):250-278.doi:10.1137/090777761
[15]DONOHO D L.For Most Large Underdetermined Systems of Linear Equations,the Minimal l1-norm Solution is Also the Sparsest Solution[J].Commun Pure Appl Math,2006,59(7):907-934.doi:10.1002/Cpa.20132
[16]CHEN S S,DONOHO D L,SAUUDERS M A.Atomic Decomposition by Basis Pursuit[J].SIAM J Sci Comput,1998,20(1):36-61.doi:10.1.1.135.1907
[17]HALE E,YIN W,ZHANG Y.Fixed-point Continuation for l1-minimization Methodology and Convergence[J].SIAM J Optim,2008,19(3):1107-1130.doi:10.1137/070698920