一类凸优化问题的随机下降算法及其应用

发布时间：2020-04-04 19:44

【摘要】：近年来,最优化问题的研究和发展得到了广泛的关注.随着大数据时代的到来,源于工程、信息、生物等很多应用问题中,所求模型可以被归纳为等式约束优化问题.由于目标函数可能非光滑、问题规模又特别巨大,传统的内点算法等往往不适合,这些问题可以使用增广拉格朗日算法或者ADMM算法等一阶算法求解更为适合.其中,ADMM算法利用目标函数关于两块变量的可分性,把一个规模较大的子问题转化为两个规模较小的子问题求解,大大简化了子问题的计算量.由于这些问题的重要应用价值,近十几年,学者们提出了一系列ADMM的改进算法.其中,ADMM下降算法(DADMM)可以在保持每步计算量基本不变的前提下,通过对部分变量进行延拓,提高了ADMM的收敛速度.另一方面,有学者提出利用随机步长加快投影收缩算法的收敛速度.本文在ADMM下降算法的基础之上,结合了随机步长的思想,提出了随机步长ADMM下降算法(RDADMM),进一步提高了收敛速度.同时,针对目标函数具有特殊结构的情形,有学者提出了线性化ADMM算法,利用目标函数的结构,通过对ADMM子问题进行线性化等改造使其有显式解,简化了子问题求解.基于此算法,又有学者将线性化ADMM算法和ADMM下降算法相结合,提出了线性化ADMM下降算法,在保持子问题有显式解的前提之下提升了线性化ADMM算法的收敛速度.本文结合随机步长思想,提出了随机步长的线性化ADMM下降算法(RDLADMM).通过求解带等式约束的二次规划数值实验,新算法的计算效率得到了验证.本文具体研究内容安排如下:第一章,主要介绍了选题背景和研究意义,以及ADMM算法的国内外研究现状,并阐述了本文的主要工作.第二章,介绍本文的研究成果.针对求解带有两块变量的结构型凸优化问题,我们提出了两种新算法,即RDADMM算法和RDLADMM算法.第三章,给出了本文新算法的收敛性分析和证明.第四章,证明了本文新算法收敛速率为O(1/t).第五章,数值实验.将RDADMM算法应用于求解带有两块变量结构型凸优化问题,验证其计算效率.第六章,对本文的研究进行总结和展望.
【学位授予单位】：南京财经大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O224

【参考文献】