English

运筹学学报

• 运筹学 •    下一篇

我和乘子交替方向法20年

何炳生1,2,*   

  1. 1. 南方科技大学数学系, 广东深圳 518055;   2. 南京大学数学系, 南京 210023
  • 收稿日期:2017-09-15 出版日期:2018-03-15 发布日期:2018-03-15
  • 通讯作者: 何炳生 hebma@nju.edu.cn
  • 基金资助:

    国家自然科学基金(No.11471156)

My 20 years research on alternating directions method of multipliers

HE Bingsheng1,2,*   

  1. 1. Department of Mathematics, Southern University Science and Technology, Shenzhen 518055, Guangdong, China; 2. Department of Mathematics, Nanjing University, Nanjing 210023, China
  • Received:2017-09-15 Online:2018-03-15 Published:2018-03-15

PDF

1334

被引次数

2

摘要：

1997 年, 交通网络分析方面的问题把我引进乘子交替方向法(ADMM)的研究领域. 近10 年来, 原本用来求解变分不等式的ADMM在优化计算中被广泛采用,   影响越来越大. 这里总结了20 年来我们在ADMM 方面的工作,  特别是近10 年 ADMM 在凸优化分裂收缩算法方面的进展. 梳理主要结果, 说清来龙去脉. 文章利用变分不等式的形式研究凸优化的ADMM 类算法,  论及的所有方法都能纳入一个简单的预测-校正统一框架. 在统一框架下证明算法的收缩性质特别简单.   通读,  有利于了解ADMM类算法的概貌.  仔细阅读, 也许就掌握了根据实际问题需要构造分裂算法的基本技巧. 也要清醒地看到, ADMM类算法源自增广拉格朗日乘子法 (ALM) 和邻近点 (PPA)算法, 它只是便于利用问题的可分离结构, 并没有消除 ALM和PPA等一阶算法固有的缺点.

关键词: 凸优化, 单调变分不等式, 乘子交替方向法, 收缩性质, O(1/t) 收敛速率, 预测-校正, 统一框架

Abstract:

My research on ADMM dates back to 1997 when I considered the problems from traffic network analysis. Over the last 10 years, the ADMM based on variational inequalities is widely used in optimization. This paper summarizes our research on ADMM over the last 20 years, particularly, the developments in splitting and contraction methods based on ADMM for convex optimization over the last 10 years. We list the main results as well as the motivations. Our analysis is based on the variational inequalities. All methods mentioned fall in a simple unified prediction-correction framework, in which the convergence analysis is quite simple. A through reading will acquaint you with the ADMM, while a more carefully reading may make you familiar with the tricks on constructing splitting methods according to the problem you met. We should notice that the ADMM originates from ALM and PPA, which are good at utilizing the splitting structure. However, it also inherits the intrinsic shortcomings of these first order methods.

Key words: convex optimization, monotone variational inequality, alternating directions method of multipliers, contractive properties, O(1/t) convergence rate, prediction-correction, unified framework