求解结构型优化问题的随机步长ADMM下降算法

本文考虑求解带有两块变量的结构型凸优化问题.ADMM算法是求解该问题的一种经典算法,主要思想是在増广拉格朗日乘子算法的基础上,利用目标函数关于两块变量的可分性,降低了子问题的计算难度.ADMM下降算法是ADMM算法的一种改进,对部分变量利用最优步长外加一个固定的延长因子进行延长,以加快ADMM算法的收敛速度.数值实验结果表明,ADMM下降算法比ADMM算法收敛速度更快.根据徐海文提出的随机步长收缩算法的思想,我们在ADMM下降算法的基础上,将延长因子改为利用随机数生成,提出了带随机步长的ADMM下降算法,并证明了新算法的收敛性.初步数值实验结果,表明新算法的计算效率优于经典ADMM算法和ADMM下降算法,且新算法的计算效率对问题规模的增长有更好的尺度适应性.