一种求解dacig-sshr模型的快速分解算法

一种求解dacig-sshr模型的快速分解算法

0总结线性回归是一种非常经典的数学模型，在数据处理、机器学习和统计学习中得到了广泛应用。这是因为压缩感知理论。1基于乘子交替方向法的求解经典的线性回归问题可刻画为:式中,β∈R式中,‖·‖上述模型是标准的带线性约束的凸优化模型,而增广拉格朗日函数是求解此类问题的经典方法之一.但是,直接使用增广拉格朗日方法会使得子问题变量耦合在一起,不利于算法的实现.因此,根据目标函数的可分离性,文献[6]利用乘子交替方向法进行求解,且取得了良好的数值效果.美中不足之处是,直接利用乘子交替方向法求解,其关于β部分的子问题没有显式表达式,这给算法的实现增加了一定难度.随后,文献[7]巧妙地将与β有关的子问题进行线性化,提高了乘子交替方向法的可操作性,也在一定程度上减少了算法的计算时间.但他们的方法要求估计一个矩阵的谱半径,这也并非一件易事.基于上述原因,本文寻求一种新的简单易行的算法.2变量分离算法针对模型(3),引入增广拉格朗日函数:式中,γ>0是罚参数,λ表示拉格朗日乘子.给定(β显然,乘子交替方向法主要的任务就是求解子问题(5)和问题(6).由于子问题(5)可以显式求解,子问题(6)的求解直接决定了算法的有效性.但由于X为了简化数学符号,记A∶=X式中,ρ>0是一个惩罚因子.针对模型(8),相应的增广拉格朗日函数为:式中,λ和γ分别代表拉格朗日乘子和罚参数.根据乘子交替方向法的Gauss-Seidel迭代思想,给定(x类似迭代格式(5)~(7),上述方法的主要工作量集中在子问题(10)~(12).下文中,本文主要讨论式(10)~(12)的具体表达式.首先,关于变量z的子问题(10)归结为:式中,diag(D)表示由D矩阵对角元素构成的列向量.最后,将(z由上述分析可见,本文新提出的算法其每个子问题都能显式求解,这相比文献[5]中的乘子交替方向法更容易实现.当矩阵A具有某些特殊结构时,可以借助一些快速矩阵求逆方法对式(18)进行求解(例如:快速傅立叶变换).当矩阵A规模较大且无特殊结构时,(γA当处理(18)的病态情形时,在共轭梯度法中引入预处理迭代技术增加算法的稳定性和可靠性,这也是新算法的一个潜在优势.综上分析,本文的分解算法过程可描述如下:1)输入初始迭代点(x2)通过式(15)更新z4)通过式(18)或(19)更新β3计算公式的数值测试本节对新提出的算法进行数值模拟来检验算法的优劣.考虑到β子问题的计算方式,新算法分为式(18)的精确计算(简记为“New-accurate”)和式(19)的一步迭代近似计算(简记为“New-one”).同时,将新算法与文献[5]中的乘子交替方向法(简记为“ADMM”)进行比较.所有算法都用MATLAB进行编程实现,其中文献[5]的ADMM算法程序由该文作者提供.类似文献[4]的测试情况,本节仍考虑两种类型的系数矩阵X:单位列向量系数矩阵和行正交系数矩阵.实验中设定初始值迭代点为(x3种算法的数值结果如表1和表2所示,其中包括计算迭代次数(Iter.)、以秒为单位的CPU运行时间(Time)和近似解的误差(ρ表1和表2的数值结果表明New-one算法和ADMM在得到质量相当的近似解时,New-one所需的CPU运行时间比后者要少,这进一步从数值上验证了本文新方法在求解子问题方面的优势.若直接使用式(18)更新β因表1、表2中的数据只是显示了计算结果的平均值,为了更加清晰展现每组随机数据的计算结果,当X分别为行正交矩阵和单位列向量矩阵时,3种算法求解第i个问题时最大、最小和平均的(内)迭代次数,如图1和图2所示;与之相对应的,误差量ρ图5和图6分别画出了当(n,p,s)=(72,256,8)时两种不同类型系数矩阵对应的数值解情况.两幅图可看出New-one恢复出来的数值解令人满意.4基于快速分解的质量评分解鉴于直接使用乘子交替方向法求解Dantzig-Selector模型时子问题不具有显式迭代格式的缺陷,本文引入一种新的模型刻画技巧,提出了一种子问题简单易行的分解算法.通过测试两种不同类型的随机数据,初步的数值结果表明新算法在CPU运行时间方面有较明显的优势.新的快速分解算法解Dantzig-Selector模型的算法步骤如下:3)通过式(16)更新x5)通过式(13)更新λ式中,其次,将z根据式(17)的一阶最优性条件立得式中,另外,根据文献[4]的测试方法,对两种不同类型的系数矩阵情况分别测试5组规模不同的随机数据,相关维数设定为(n,p,s)=(72i,256i,8i