在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2019, Vol. 36 ›› Issue (2): 123-137.doi: 10.3969/j.issn.1005-3085.2019.02.001

• •    下一篇

求解结构型优化问题的随机步长ADMM下降算法

张艳娜1,   申  远1,   孙黎明2   

  1. 1- 南京财经大学应用数学学院，南京  210023
    2- 南京审计大学统计与数学学院，南京  211815
  • 收稿日期:2017-03-31 接受日期:2018-05-04 出版日期:2019-04-15 发布日期:2019-06-15
  • 通讯作者: 孙黎明 E-mail: lmsun@nau.edu.cn
  • 基金资助:
    国家自然科学基金(11401295; 11726618)；国家社科基金(15BGL158; 17BTQ063)；江苏省“青蓝工程”项目；江苏省社科基金(18GLA002)；江苏省高等学校自然科学研究项目(18KJB110016).

A Descent Alternating Direction Method of Multipliers with Random Step Size for Structured Optimization Problem

ZHANG Yan-na1,    SHEN Yuan1,   SUN Li-ming2   

  1. 1- School of Applied Mathematics, Nanjing University of Finance & Economics, Nanjing 210023
    2- School of Statistics and Mathematics Science, Nanjing Audit University, Nanjing 211815
  • Received:2017-03-31 Accepted:2018-05-04 Online:2019-04-15 Published:2019-06-15
  • Contact: L. Sun. E-mail address: lmsun@nau.edu.cn
  • Supported by:
    The National Natural Science Foundation of China (11401295; 11726618); the National Social Science Foundation of China (15BGL158; 17BTQ063); the Qinglan Project of Jiangsu Province; the Social Science Foundation of Jiangsu Province (18GLA002); the Natural Science Foundation of University and Colleges in Jiangsu Province (18KJB110016).

PDF (PC)

364

摘要： 本文考虑求解带有两块变量的结构型凸优化问题．ADMM算法是求解该问题的一种经典算法，主要思想是在増广拉格朗日乘子算法的基础上，利用目标函数关于两块变量的可分性，降低了子问题的计算难度．ADMM下降算法是ADMM算法的一种改进，对部分变量利用最优步长外加一个固定的延长因子进行延长，以加快ADMM算法的收敛速度．数值实验结果表明，ADMM下降算法比ADMM算法收敛速度更快．根据徐海文提出的随机步长收缩算法的思想，我们在ADMM下降算法的基础上，将延长因子改为利用随机数生成，提出了带随机步长的ADMM下降算法，并证明了新算法的收敛性．初步数值实验结果，表明新算法的计算效率优于经典ADMM算法和ADMM下降算法，且新算法的计算效率对问题规模的增长有更好的尺度适应性．

关键词: 变分不等式, 交替方向乘子法, 邻近点算法, 随机步长, 结构型凸优化问题

Abstract: In this paper, we consider the structured convex optimization problem with two blocks of variables. The alternating direction method of multipliers (ADMM) is a classical method for solving this problem, which is based on the augmented Lagrange algorithm and it utilizes the separability of two blocks of variables in the objective function to simplify the computation of subproblems. The descent alternating direction method of multipliers (DADMM) is an improved version of ADMM, which applies an optimal step as well as a fixed factor to do extension on  part of the variables. The DADMM is reported to be faster than the classical ADMM in numerical simulations. According to the idea of SC-Method proposed by Xu which allows the extension factor to be randomly generated, we propose a new DADMM with random step size. The convergence of the new algorithm can be derived under mild assumptions. Preliminary experiments demonstrate the promising performance and dimensional scalability of the new method.

Key words: variational inequalities, alternating direction method of multipliers, proximal point algorithm, random step size, structured optimization

中图分类号: