求解三块可分非凸优化问题的交替方向法

发布时间：2020-07-30 18:22

【摘要】：交替方向法(ADMM)起源于20世纪70年代微分方程数值解领域,可追溯到20世纪50年代著名的算子分裂算法,如Dougals-Rachford分裂算法、Peaceman-Rachford算子分裂算法等,在上世纪80年代初被引入优化领域,逐渐成为凸优化算法中一类非常有效的算法.近年来,随着大数据和人工智能的兴起,交替方向法在机器学习、交通问题、图像处理、经济平衡问题、资源配置问题等领域发挥着越来越重要的应用,受到越来越多的学者的关注.交替方向法过去的发展主要集中在凸优化问题,其算法设计、理论分析已经很成熟.然而实际应用中产生的问题往往是非凸的.对于目标函数是非凸或者部分非凸的情况,目前一般采取凸松弛方式进行处理,直接从非凸问题角度进行研究还处于初期阶段,只有非常少的研究成果.从本质上讲,非凸模型往往比凸模型更好地近似实际问题本身.因此,越来越多的学者开始关注非凸问题的交替方向法的收敛性及收敛速率.对于凸优化问题中的ADMM算法,当目标函数为两块时,交替方向法是收敛的.然而,对于目标函数为多块可分凸优化问题,有反例可说明直接推广到交替方向法是发散的,学者从两个不同的侧面对多块问题进行了研究:一是给出多块凸优化问题直接推广的ADMM算法收敛的充分条件,二是对算法进行”简单”修正,在经典算法的条件下保证其收敛性.最近,Sun,Toh,Yang在[36]中提出了一种变形的交替方向法去求解一类特殊的三块可分凸优化问题,证明该算法的收敛性.对非凸问题,Guo,Han,Wang,Wu在[17]中研究了多块可分非凸优化问题,在假设目标函数满足Kurdyka-Lojasiewicz不等式的条件下,证明交替方向法的收敛性并分析了收敛速率。结合[36]及[17]的结果,本文针对含有二次项的三块可分非凸优化问题,进行算法设计和收敛性分析的研究.首先,提出类似[36]的半定临近交替方向法.在假设目标函数满足Kurdyka-Lojasiewicz不等式的条件下,证明该变形的交替方向法产生的迭代序列收敛到原问题的稳定点.进一步地,证明在Kurdyka-Lojasiewicz不等式参数满足一定条件下,分析了算法的线性收敛速率.
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O224

【相似文献】

相关期刊论文 前10条

1 胡伯霞;非对称变分不等式的另一类非精确交替方向法[J];衡阳师范学院学报;2005年03期

2 何炳生;;乘子交替方向法的一些收敛性质[J];高等学校计算数学学报;2017年01期

3 周叔子;胡伯霞;;一类非对称变分不等式的非精确交替方向法[J];湖南大学学报(自然科学版);2007年04期

4 刘晓遇;解对流扩散方程的显式交替方向法[J];清华大学学报(自然科学版);1999年12期

5 刘田园;;凸两分块问题邻近乘子交替方向法的O(1/n)收敛率[J];玉林师范学院学报;2017年02期

6 李慧;;解凸优化问题的一类修正线性近似交替方向法[J];重庆工商大学学报(自然科学版);2015年04期

7 吕晓帆;李姣芬;周学林;;非精确交替方向法求解秩最小化问题[J];桂林电子科技大学学报;2016年02期

8 孙聿童;赵金玲;;求解结构型分裂可行问题的一种交替方向法[J];数值计算与计算机应用;2018年01期

9 康金章;交替方向法迭代参数的确定[J];福州大学学报;1962年02期

10 何炳生;;我和乘子交替方向法20年[J];运筹学学报;2018年01期

相关会议论文 前1条

1 李敏;何炳生;;求解带约束的min-max问题的预测校正交替方向法[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

相关博士学位论文 前10条

1 王金江;乘子交替方向法与函数二阶增长条件[D];哈尔滨工业大学;2016年

2 晁绵涛;带回代乘子交替方向法与误差界研究[D];北京工业大学;2015年

3 郭科;非凸优化问题Douglas-Rachford分裂方法的收敛性分析[D];南京师范大学;2017年

4 贾泽慧;优化问题分裂算法及早高峰拥堵问题研究[D];南京师范大学;2017年

5 张文星;增广拉格朗日型算法及其在图像处理中的应用[D];南京大学;2012年

6 王学永;变分不等式与线性约束分离优化问题的若干算法研究[D];重庆大学;2015年

7 罗曼;偏积分微分方程拟小波及紧致差分方法[D];湖南师范大学;2016年

8 胡亚萍;非线性单调方程组和非光滑优化问题的算法研究[D];华东理工大学;2015年

9 申远;一些求解结构型优化的一阶算法[D];南京大学;2012年

10 刘晓光;非光滑图像恢复算法的研究[D];陕西师范大学;2014年

相关硕士学位论文 前10条

1 黎财胜;求解三块可分非凸优化问题的交替方向法[D];南京师范大学;2018年

2 黎超琼;求解一类可分离结构型变分不等式问题的部分并行分裂LQP交替方向法[D];云南师范大学;2018年

3 戴艺清;几类可分离凸优化问题的同伦算法[D];福州大学;2016年

4 孙康康;小批量数据的随机交替方向法研究[D];南京大学;2018年

5 郭绮;混合矩阵回归模型的线性化乘子交替方向法[D];北京交通大学;2018年

6 王慧芳;线性化乘子交替方向法求解稀疏组最小一乘模型[D];北京交通大学;2017年

7 金天;具有大步长邻近点的对称交替方向法的收敛性研究[D];南京大学;2017年

8 曹冰;解可分离变分不等式的一种自适应交替方向法[D];河北工业大学;2015年

9 龙林鹤;解可分离结构型变分不等式的LQP交替方向法[D];重庆大学;2016年

10 邓钊;非凸非光滑分块优化问题Bregman乘子交替方向法收敛性分析[D];广西大学;2017年

本文编号：2775907