Journal of Industrial and Management Optimization (JIMO)

Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints

Pages: 743 - 759, Volume 10, Issue 3, July 2014      doi:10.3934/jimo.2014.10.743

       Abstract        References        Full Text (799.9K)       Related Articles       

Yuan Shen - School of Applied Mathematics, Nanjing University of Finance & Economics, Nanjing, 210023, China (email)
Wenxing Zhang - School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu, 611731, China (email)
Bingsheng He - Department of Mathematics, Nanjing University, Nanjing, 210093, China (email)

Abstract: The classical augmented Lagrangian method (ALM) is an efficient method for solving convex optimization with linear constraints. However, the efficiency of ALM, to some extent, is hinged by the computational efforts on solving the resulting subproblems. For the convex optimization with some favorable structures, e.g., either the objective function is separable or the matrices in linear constraints are well-posed, a relaxation to the subproblems of ALM can substantially result in solutions with closed-form. Unfortunately, the relaxation skill can not be extended directly to the generic convex optimization without special structures, particularly for the case of objective function with coupled variables. In this paper, by further relaxing the resulting subproblems of ALM, we propose several novel augmented Lagrangian-based proximal point algorithms. Algorithmically, the next iterate is produced by integrating the predictor, which is obtained in either primal-dual or dual-primal order, with the current iterate. Numerical results demonstrate the promising performances of the proposed algorithms.

Keywords:  Convex optimization, proximal point algorithm, augmented Lagrangian method, relaxation.
Mathematics Subject Classification:  Primary: 65K05, 90C25; Secondary: 49M29, 90C30.

Received: February 2012;      Revised: December 2012;      Available Online: November 2013.