Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2018-001 (July 11, 2018)

An Alternating Direction Method of Multiplier with the BFGS update for Structured Convex Quadratic Optimization
by Yan Gu and Nobuo Yamashita

pdf File


The alternating direction method of multipliers (ADMM) is an effective method for solving wide fields of convex problems. At each iteration, the classical ADMM solves two subproblems exactly. However, in many applications, it is expensive or impossible to obtain the exact solutions of the subproblem. To overcome the difficulty, some proximal terms are added to the subproblems. This class of methods normally solves the original subproblem approximately, and thus takes more iterations. This fact urges us to consider that a special proximal term can lead to a better result as the classical ADMM. In this paper, we propose a proximal ADMM whose regularized matrix in the proximal term is generated by the BFGS update (or Limited memory BFGS) at every iteration. These types of matrices use the second-order information of the objective function. The convergence of the proposed method is proved under certain assumptions. Numerical results are given to show the effectiveness of the proposed proximal ADMM.