数学物理学报 ›› 2024, Vol. 44 ›› Issue (1): 195-208.

• • 上一篇    下一篇

非凸多分块优化的 Bregman ADMM 的收敛率研究

陈建华(),彭建文*()   

  1. 重庆师范大学数学科学学院 重庆 401331
  • 收稿日期:2022-06-09 修回日期:2023-08-16 出版日期:2024-02-26 发布日期:2024-01-10
  • 通讯作者: 彭建文, E-mail:jwpeng168@hotmail.com
  • 作者简介:陈建华, E-mail:1224888402@qq.com
  • 基金资助:
    国家自然科学基金(12271071);国家自然科学基金(11991024);重庆英才·创新创业领军人才·创新创业示范团队项目(CQYC20210309536);重庆英才计划"包干制"项目(cstc2022ycjh-bgzxm0147);重庆市高校创新研究群体项目(CXQT20-014);重庆市自然科学基金项目(cstc2021jcyj-msxmX0300)

Research on the Convergence Rate of Bregman ADMM for Nonconvex Multiblock Optimization

Chen Jianhua(),Peng Jianwen()   

  1. College of Mathematical Sciences; Chongqing Normal University, Chongqing 401331
  • Received:2022-06-09 Revised:2023-08-16 Online:2024-02-26 Published:2024-01-10
  • Supported by:
    National Natural Science Foundation of China(12271071);National Natural Science Foundation of China(11991024);Team Project of Innovation Leading Talent in Chongqing(CQYC20210309536);Chongqing Talent Plan contract system project(cstc2022ycjh-bgzxm0147);Chongqing University Innovation Research Group Project(CXQT20-014);Basic and Advanced Research Project of Chongqing(cstc2021jcyj-msxmX0300)

摘要:

Wang 等提出了求解带线性约束的多块可分非凸优化问题的带 Bregman 距离的交替方向乘子法 (Bregman ADMM), 并证明了其收敛性. 该文将进一步研究求解带线性约束的多块可分非凸优化问题的 Bregman ADMM 的收敛率, 以及算法产生的迭代点列有界的充分条件. 在效益函数的 Kurdyka-Łojasiewicz (KŁ) 性质下, 该文建立了值和迭代的收敛速率, 证明了与目标函数相关的各种 KŁ 指数值可获得 Bregman ADMM 的三种不同收敛速度. 更确切地说, 该文证明了如下结果:如果效益函数的 KŁ 指数$\theta=0$, 那么由 Bregman ADMM 生成的序列经过有限次迭代后收敛; 如果$\theta \in \left (0, \frac{1}{2}\right ]$, 那么Bregman ADMM是线性收敛的;如果$\theta \in \left ( \frac{1}{2}, 1\right )$, 那么 Bregman ADMM 是次线性收敛的.

关键词: 非凸优化问题, 交替方向乘子法, Kurdyka-Łojasiewicz 性质, Bregman 距离, 收敛率, 有界性

Abstract:

Wang et al proposed the alternating direction method of multipliers with Bregman distance (Bregman ADMM) for solving multi-block separable nonconvex optimization problems with linear constraints, and proved its convergence.In this paper, we will further study the convergence rate of Bregman ADMM for solving multi-block separable nonconvex optimization problems with linear constraints, and the sufficient conditions for the boundedness of the iterative point sequence generated by the algorithm.Under the Kurdyka-Łojasiewicz property of benefit function, this paper establish the convergence rates for the values and iterates, and we show that various values of KŁ-exponent associated with the objective function can obtain Bregman ADMM with three different convergence rates. More precisely, this paper proves the following results:if the(KŁ) exponent of the benefit function$\theta=0$, then the sequence generated by Bregman ADMM converges in a finite numbers of iterations; if$\theta \in \left (0, \frac{1}{2}\right ]$, then Bregman ADMM is linearly convergent; if$\theta \in \left ( \frac{1}{2}, 1\right )$, then Bregman ADMM is sublinear convergent.

Key words: Nonconvex optimization problem, The alternating direction method of multipliers, Kurdyka-Łojasiewicz property, Bregman distance, Convergence rates, Boundedness

中图分类号: 

  • O221