可分非凸优化的分解算法及其在图像分割中的应用研究

The separable convex optimization gets rapid progress in recent years, both in theoretical and numerical aspects, as well as its applications. However, separable nonconvex optimization problems arise frequently from applications fields, while numerical methods and convergence analysis are still at its infancy. In this project, based on the well-known Kurdyka-Lojasiewicz (KL) inequality, we design new decomposition methods for solving separable nonconvex optimization problems, analyze their convergence, and apply them in image segmentation problems, which is a class of basic and difficult problems in image processing. Concretely, we first consider the case that the objective functions has two or more blocks of separable structure, and prove the convergence of the new decomposition methods under the assumption that the objective function satisfies KL property and some other suitable conditions. Then, under some further conditions about the KL exponents, we analyze the convergence rate of the new algorithms. Finally, we customize the new algorithms for Mumford-Shah(MS) model, a well-known model for image segmentation, also establish their global convergence and convergence rate. Unlike the other methods which solve the convex relaxation of the MS model, we apply our new algorithms for solving the original MS model, which is the exact description of the real application. We use lots of numerical results to demonstrate the efficiency of the new algorithms. Our work can give some solid basis for further study on a class of nonconvex optimization problems, and provide new tools and theoretical guarantee for solving application problems.

可分凸优化问题理论和算法在过去几年得到了飞速发展，并在众多领域有着广泛应用，其算法和理论分析已经比较完善。然而实际应用中，可分非凸优化问题广泛地存在，对其算法设计和收敛性分析尚处于初级阶段。本项目中，基于著名的Kurdyka-Lojasiewicz(KL)不等式，我们着重研究可分非凸优化问题中分解算法的收敛性及其在图像分割中的应用：首先，针对目标函数为两模块及多模块的情况，假设目标函数满足KL性质，证明迭代序列的聚点即为问题的解；进一步，分析KL性质中的凹函数结构，讨论不同指数参数情况下算法的收敛率；最后，我们为图像分割中非凸Mumford-Shah(MS)模型“量身定制”新的分解算法，利用所得理论结果，对新算法进行收敛性和收敛率分析，并通过大量数值模拟验证我们所提出算法的高效性。本项目的研究工作将为深入探讨一系列非凸优化问题奠定坚实的理论基础，为解决实际应用问题提供新的工具和理论保证。

围绕着项目申请书内容，本课题组对非凸优化问题的分解算法及其在图像处理中的应用、智能优化算法设计等关键问题开展研究工作，取得了一系列研究成果，保质保量完成了项目预期的计划，项目组发表学术论文 12 篇，其中 SCI 收录 7篇，核心期刊收录 4篇，SCD收录1篇，接受待刊论文 3 篇，投稿以及修改论文若干。主要研究成果有以下几点:.1).结合重要的KL不等式性质来分析非凸优化问题中ADMM算法的收敛性，若目标函数的增广拉格朗日函数为KL函数，我们的假设只需满足增广拉格朗日函数中的罚参数 大于 时， 即可证明由经典ADMM算法产生的迭代序列收敛到拉格朗日函数的聚点。由于结合了目标函数的KL性质，极大弱化了对于目标函数的假设条件，使得我们的理论分析更具有一般性与代表性。同时，将两模块问题中得到的结论推广至多模块非凸优化问题中，进一步讨论了三个模块下非凸ADMM算法的收敛性。.2). 研究了图像重建问题、图像混合去噪和泊松去噪，图像着色，图像放大等问题。针对实际问题，设计了ADMM及其修正算法：Peaceman-Rachford分裂算法、带Gauss回带的多块ADMM算法等。结合图像问题中的具体模型，对经典算法进行改进，加快算法的收敛速度。.3). 考虑基于动态罚函数和Lévy flight的人工蜂群算法来求解约束优化问题, 提出四种改进策略：用动态罚来处理约束；利用logistic映照的Lévy flight处理雇佣蜂项；根据选择概率，改进搜索机制；改进边界处理机制。另一方面，提出一种改进的二进制人工蜂群算法用于图像的动态聚类。该算法用了变化更多的候选解产生方式，以提高算法的全局搜索能力；增加了一个局部搜索阶段，以提高算法的局部寻优能力。. 总之，我们对项目申请书的部分研究内容进行了深入的探讨和研究，并进行了其它方面的研究工作，为今后的研究开展打下了坚实的基础。