  The auxiliary problem principle of augmented Lagrangian (APP-AL), proposed by
Cohen and Zhu (1984), aims to find the solution of a constrained optimization
problem through a sequence of auxiliary problems involving augmented
Lagrangian. The merits of this approach are two folds. First, the core function
is usually separable, which makes the subproblems at each step decomposable and
particularly attractive for parallel computing. Second, the choice of the core
function is quite flexible. Consequently, by carefully specifying this
function, APP-AL may reduce to some standard optimization algorithms. In this
paper, we pursue enhancing such flexibility by allowing the core function to be
non-identical at each step of the algorithm, and name it varying auxiliary
problem principle (VAPP-AL). Depending on the problem structure, the varying
core functions in VAPP-AL can be adapted to design new flexible and suitable
algorithm for parallel and distributed computing. The convergence and O(1/t)
convergence rate of VAPP-AL for convex problem with coupling objective and
constraints is proved. Moreover, if this function is specialized to be
quadratic, an o(1/t) convergence rate can be established. Interestingly, the
new VAPP framework can cover several variants of Jacobian type augmented
Lagrangian decomposition methods as special cases. Furthermore, our technique
works for the convex problem with nonseparable objective and multi-blocks
coupled linear constraints, which usually can not be handled by ADMM.
