非凸优化问题Douglas-Rachford分裂方法的收敛性分析

摘要

在本文中，我们研究了Douglas-Rachford算子分裂方法求解非凸优化问题的收敛性分析.论文由四部分构成，结构如下:
　　第一、二章，给出了本文的研究背景及所要用到的一些预备知识.
　　第三章，我们考虑乘子交替方向法求解线性约束非凸优化问题的收敛性分析.本质上，乘子交替方向法可以看作Douglas-Rachford分裂方法应用到两块线性约束可分凸优化问题的对偶问题.对于许多应用问题中的大规模可分优化问题，目标函数为凸函数或是非凸函数，利用经典的乘子交替方向法来求解是非常有效的.虽然对于凸目标函数的情形已经有了非常多的收敛性分析结果，目标函数为非凸的情形仍然是一个公开问题，这方面的研究仍在初期.我们考虑三种问题，即线性约束两块可分非凸优化问题，线性约束多块可分非凸优化问题，具有耦合目标函数的线性约束非凸优化问题.通过假定相应的增广拉格朗日函数满足Kurdyka-(L)ojasiewicz不等式，当增广拉格朗日函数中的罚参数充分大时，我们证明了用乘子交替方向法求解这些问题产生的迭代序列收敛到增广拉格朗日函数的稳定点.在一些更多的假设下，我们分析了该算法的收敛速率.
　　第四章，我们考虑利用Douglas-Rachford分裂方法求解极小化一个强凸函数与一个弱凸函数和的优化问题的收敛性分析.该模型有非常多的应用，特别是某些稀疏性驱动的问题，可以避免通常用凸的罚项产生的偏差估计.若目标函数中的两个函数都是凸函数，Douglas-Rachford分裂方法的收敛性已经有了非常多地研究.然而当目标函数中含有非凸函数时，包括“强凸+弱凸”的情形，该算法的收敛性研究仍在初期.与现有的文献相比，我们在相对较弱的假设下证明了Douglas-Rachford分裂方法求解“强凸+弱凸”问题的收敛性.更多地，我们证明了Douglas-Rachford算子的渐近正则速率，并且在度量次正则性假设下，我们证明了该算法的局部线性收敛速率.

目录

声明

Contents

摘要

Abstract

Chapter 1 Introduction

1．1 Motivation

1．2 Contributions

1．3 Organization

Chapter 2 Preliminaries

2．1 Nonexpansive operator

2．2 Convex and variational analysis

2．3 Kurdyka-Lojasiewicz inequality

2．4 Douglas-Rachford splitting method

Chapter 3 Alternating Direction Method of Multipliers

3．1 Two-block separable nonconvex optimization problem with linear constaints

3．1．1 Convergence analysis

3．1．2 Conclusions

3．2 Multi-block separable nonconvex optimization problem with linear constraints

3．2．1 Convergence analysis

3．2．2 Conclusions

3．3 Linearly constrained nonconvex optimization with coupled objective functions

3．3．1 Convergence analysis

3．3．2 Extensions

3．3．3 Conclusions

Chapter 4 Douglas-Rachford Splitting Method

4．1 Proximal parameter

4．2 Convergence analysis

4．2．1 Preparations

4．2．2 Convergence of the Douglas-Rachford splitting method(4．0．2)

4．2．3 Convergence of the Douglas-Rachford splitting method(4．0．3)

4．3 Rates of asymptotic regularity

4．3．1 Douglas-Rachford operator (~T)DR

4．3．2 Douglas-Rachford operator (∧T)DR

4．3．3 Related to the existing works

4．4 Local linear convergence rate

4．5 Conclusions

Bibliography

Papers completed in the period of Ph．D．education

Acknowledgements