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

摘要

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

目录

声明

摘要

第一章绪论

§1．1问题描述

§1．2基本知识

§1．3本文结构

第二章可分优化问题

§2．1引言

§2．2多块可分凸优化问题

§2．3多块可分非凸优化问题

第三章算法与主要结果

§3．1引言

§3．2算法

§3．3收敛性分析

第四章结论与展望

参考文献

致谢