张　乾，何　岸，何洪津

(杭州电子科技大学理学院，浙江 杭州 310018)



一种解Dantzig-Selector模型的快速分解算法

张乾，何岸，何洪津

(杭州电子科技大学理学院，浙江 杭州 310018)

基于增广拉格朗日法提出了一种快速分解算法求解Dantzig-Selector模型.与经典的乘子交替方向法相比，新算法的每个子问题都具有更简单易行的迭代格式.通过测试两种不同类型的随机数据，相应的数值计算结果表明，算法在CPU运行时间方面有较明显的优势.

Dantzig-Selector模型；增广拉格朗日方法；乘子交替方向法；分解算法

0　引　言

线性回归是一类非常经典的数学模型，它在信号处理、机器学习以及统计学习中有着极其广泛的应用.由于压缩感知理论[1]的提出，寻找欠定线性回归模型的稀疏解成为近年来最热门的研究课题之一.然而，直接寻找满足线性方程组的稀疏解是一个NP-难问题.为此，研究者提出了一系列凸松弛优化模型，例如基追踪模型[2]和LASSO模型[3].2007年，Candes和Tao针对超欠定线性方程组问题进一步提出了更稳健的Dantzig-Selector模型[4].与LASSO模型相比，Dantzig-Selector模型结构更为复杂，从而给模型的求解增加了很大的困难.如何设计简单高效的算法求解该模型是极具挑战性的研究课题之一.本文首先通过引入两个新的辅助变量，将Dantzig-Selector模型等价转化为弱分离的优化问题.然后，基于增广拉格朗日方法，充分利用新模型的结构特点设计出一种快速、可行的分解算法，使得算法的子问题都具有显式表达式.相比已有的分裂算法，本文算法在CPU运行时……