基于线性化逐块交替方向乘子法的改进

基于线性化逐块交替方向乘子法的改进

乘子迭代方向法（admm）是解决线性约束凸优化问题的高效算法，由格林威治等人开发。考虑以下多块变量线性约束凸优化问题：其中，θ假设式（1）的解是非空的，它的拉格朗日函数为它的增广拉格朗日函数为其中，λ∈RADMM的一个优势是利用目标函数关于多块变量的可分性，把一个高维的子问题分解成多个维数较低的子问题，大大简化了子问题求解的过程．特别的，当θ由于广泛的应用性，国内外学者从理论、改进、应用等多个角度对ADMM进行了深入研究．当只有2块变量时（m=2),ADMM有全局收敛性，早期关于ADMM的研究工作集中于2块变量的情形：如Eckstein等当有更多块变量时（m≥3),ADMM一般不收敛，可参考文献本文基于文献式中，m利用以上记号，式（5）可以改写为以下形式：利用BADMM求解式（5）的迭代格式如下：其中η的二次项在x利用LBADMM求解式（5）的迭代格式如下：其中，η1预备知识1.1变分序列的性质若（x引入以下新记号：式（12）简写成下面的形式：1.2引用理论矩阵A和B在式（7）中被定义，有以下结论．引理1定义那么，有m引理2令k2a步骤2预测步骤2校正基于LBADMM，提出以下新算法：算法1新算法与线性化逐块ADMM算法的区别在于改进了算法中的邻近项因子，使算法的收敛速度更快．原算法对于每组变量使用相同的邻近项因子，而新算法对于组内的每一块使用不同的邻近项因子，参数条件大大放松，因此收敛速度更快．这种优势在组内不同块之间‖A步骤1（预测）步骤2（校正）其中，我们可以证明以下2个有用的结果．引理3给定其中，证明：忽略一些常数项，式（18）中的x根据一阶最优条件，有同样的，式（18）中y子问题的最优性条件可以写成再利用它可以重新写成结合式（26）、（27）、（28），使用式（20）、（21）、（22），引理得证．引理4定义则H、M正定．证明：根据式（20）中M的定义，有则根据引理2知道H是正定的．而且根据矩阵G的定义，可得：由引理2可知G正定，引理得证．基于引理3和4，有如下的定理．定理1序列{w证明：通过式（19）、（29）和（21）可以写成利用以下恒等式将通过式（19）和（29）处理式（36）的右端第2个括号里的项，得结合式（34）、（36）和（37），得式（33），定理得证．定理2序列{w证明：在式（33）中设w=w因为w以上2个不等式结合，得证．现在，给出算法1的收敛结论．定理3由算法1生成的序列{w证明：从式（38）可知{w3新算法与lbadagmm算法的比较我们将新算法与LBADMM算法通过数值实验进行比较，以研究新算法的实际计算效率．实验平台为一台配置为奔腾1.33GHzCPU、2GB内存、Windows10操作系统的笔记本电脑，所有算法在MATLABR2016a上编程实现．下面从迭代步数、计算时间及精度3个方面对算法的数值表现进行考察．将新算法应用于求解在统计学、信息科学中常用的LASSO模型，其问题如下：其中‖·‖按照2%的非零元比例随机生成稀疏向量（x无论是用新算法还是用LBADMM算法求解式（41），子问题的求解都是使用软阈值收缩（softshrinkage）得到，计算量完全相同．2种算法的关键参数β的取值需要人工调整至最优，每组问题β的设置都可能不同．邻近因子的选取按照尽可能靠近其上下界的规则选取，如k为公平起见，2种算法的初始点均随机产生，终止条件均为所有变量（x,y和λ）相邻2步的相对变化小于10我们在几组不同（m,n，ρ）设置下测试了算法．在每组（m,n，ρ）设置下，我们随机生成10个问题，并比较算法的计算时间和迭代步数的平均值．具体的数值结果见表1:从表1的结果看出：新算法的迭代次数和计算时间总比LBADMM算法少，可见新算法比LBADMM算法更为高效．并且在为了更细致地观察和比较LBADMM与新算法的收敛速度，在2种算法的求解过程中记录下每个迭代步当前点到解点的欧式距离，并将在2种不同问题设置下该距离的变化曲线展示在图1中．从图1可看出：在迭代初期（约200步以内），2种算法收敛几乎一样；在迭代中后期，LBADMM收敛变慢，而新算法的收敛速度基本保持不变．不同的问题设置基本不影响这一观察结果，因此新算法的收敛不仅稳定快速，而且在高精度下优势更为明显．比较2个子图还可发现，2种算法在迭代中后期的收敛速度的差距在ρ较大时更为明显，这和我们的预期完全一致．4算法有效性分析本文研究了在信息科学、统计学和工程等领域有广泛应用价值的线性约束多块凸优化问题及用于求解该问题的多块ADMM算法．ADMM通常只能求解2块变量的模型，在多块的情况下一般不收敛，需要增加假设条件或者对多块ADMM适当改造以保证算法收敛性．本文基于线性化逐块ADMM算法，放松了算法中邻近因子的取值范围，在保持子问题容易求解的前提下，使算法收敛速度加快．初步数值实验