We design inexact proximal augmented Lagrangian based decomposition methods for convex composite programming problems with dual block-angular structures. Our methods are particularly well suited for convex quadratic p...
详细信息
We design inexact proximal augmented Lagrangian based decomposition methods for convex composite programming problems with dual block-angular structures. Our methods are particularly well suited for convex quadratic programming problems arising from stochastic programming models. The algorithmic framework is based on the application of the abstract inexact proximal ADMM framework developed in [Chen, Sun, Toh, Math. Prog. 161:237-270] to the dual of the target problem, as well as the application of the recently developed symmetric Gauss-Seidel decomposition theorem for solving a proximal multi-block convexcomposite quadratic programming problem. The key issues in our algorithmic design are firstly in designing appropriate proximal terms to decompose the computation of the dual variable blocks of the target problem to make the subproblems in each iteration easier to solve, and secondly to develop novel numerical schemes to solve the decomposed subproblems efficiently. Our inexact augmented Lagrangian based decomposition methods have guaranteed convergence. We present an application of the proposed algorithms to the doubly nonnegative relaxations of uncapacitated facility location problems, as well as to two-stage stochastic optimization problems. We conduct numerous numerical experiments to evaluate the performance of our method against state-of-the-art solvers such as Gurobi and MOSEK. Moreover, our proposed algorithms also compare favourably to the well-known progressive hedging algorithm of Rockafellar and Wets.
In applying the level-set method developed in [E. Van den Berg and M. P. Friedlander, SIAM J. Sci. Comput., 31 (2008), pp. 890-912] and [E. Van den Berg and M. P. Friedlander, SIAM J. Optim., 21 (2011), pp. 1201-1229]...
详细信息
In applying the level-set method developed in [E. Van den Berg and M. P. Friedlander, SIAM J. Sci. Comput., 31 (2008), pp. 890-912] and [E. Van den Berg and M. P. Friedlander, SIAM J. Optim., 21 (2011), pp. 1201-1229] to solve the fused lasso problems, one needs to solve a sequence of regularized least squares subproblems. In order to make the level-set method practical, we develop a highly efficient inexact semismooth Newton based augmented Lagrangian method for solving these subproblems. The efficiency of our approach is based on several ingredients that constitute the main contributions of this paper. First, an explicit formula for constructing the generalized Jacobian of the proximal mapping of the fused lasso regularizer is derived. Second, the special structure of the generalized Jacobian is carefully extracted and analyzed for the efficient implementation of the semismooth Newton method. Finally, numerical results, including the comparison between our approach and several state-of-the-art solvers, on real data sets are presented to demonstrate the high efficiency and robustness of our proposed algorithm in solving challenging large-scale fused lasso problems.
暂无评论