English

运筹学学报 ›› 2019, Vol. 23 ›› Issue (3): 135-140.doi: 10.15960/j.cnki.issn.1007-6093.2019.03.010

• • 上一篇    

多块交替方向乘子法不收敛反例的几点注记

陈彩华*   

  1. 南京大学工程管理学院, 南京 210093
  • 收稿日期:2019-05-13 发布日期:2019-09-09
  • 通讯作者: 陈彩华 E-mail:chchen@nju.edu.cn
  • 基金资助:
    江苏省自然科学基金（No.BK20181259），国家自然科学基金（Nos.11871269，71673130）

Some notes on the divergence example for multi-block alternating direction method of multipliers

CHEN Caihua*   

  1. School ofManagement and Engineering, Nanjing University, Nanjing 210093, China
  • Received:2019-05-13 Published:2019-09-09

PDF

356

摘要： 近年来，多块交替方向乘子法被广泛地应用在信号处理、图像处理、机器学习、工程计算等各个领域中，然而它的收敛性一直是一个悬而未决的公开问题；直至2016年，陈彩华等人给出了一个三维线性方程组构成的反例说明多块交替方向乘子法是可能发散的.结合陈等人的结果，现讨论了与此相关的三个问题：1）反例之所以发散是否由于初始点选择不够好?2）反例的发散是否因为它的可行域是单点集?3）是否能够在对偶变量更新中引入某一与问题无关的步长γ∈（0，1]使得小步长的交替方向乘子法变形收敛?从理论上对前两个问题给出了否定的回答，证明当初始点随机选取时，存在可行域不是单点集的例子，使得多块交替方向乘子法求解该问题时以概率1发散；从数值上否定了第三个问题，说明即使步长γ=10-8，多块交替方向乘子法也可能发散.

关键词: 多块交替方向乘子法, 发散反例, 初始点, 可行域, 对偶更新步长

Abstract: Recently, multi-block alternating direction method of multipliers (ADMM) has been widely used in signal processing, image processing, machine learning, engineering calculation and so on. However its convergence had been ambiguous for a long time. In 2016, Chen Caihua, et al. gave a counter-example constructed by a threedimensional linear equations to illustrate the possible convergence of multi-block ADMM. In this paper we discuss three related issues in the light of the results Chen's:1) is the divergence of the counter-example due to the initial point selection? 2) is the divergence of the counter-example due to its singleton feasible region? 3) Whether it is possible to introduce a problem-independent step-length in the dual update γ ∈ (0, 1] such that the small step-size ADMM variant converges? In theory, the paper gives negative answers to the first two questions, and we prove that when the initial point is randomly selected, there is an example where the feasible region is not a singleton such that the multi-block ADMM is divergent with probability of 1. The third problem is negated numerically and we show that even if the step-size is γ=10-8, the multi-block ADMM can still diverge.

Key words: multi-block ADMM, divergence example, initial point, feasible region, stepsize in the dual update

中图分类号: