Abstract:

The linearly constrained convex optimization is a class of quintessential problem in optimization community. In this paper, we will devote to the algorithmic study of such problems on the perspective of duality. By introducing auxiliary variables, the dual of this problem can be reformulated into a separable structured optimization. By virtue of the recent advances in accelerated alternating direction method of multiplier, we analyze the convergence and establish the $O(1/k^2)$ convergence rate of Goldstein et al's accelerated algorithm under some mild conditions. Specifically, 1) the objective suffices to be convex instead of strongly convex; 2) the penalty parameter merely requires $\beta>0$ instead of a bounded interval involving Lipschitz constant and strongly convex modulus. Some numerical experiments on image reconstruction problem were conducted to demonstrate the performance of algorithm on solving linearly constrained convex optimization, which is computationally appealing.

Key words: linear-equality constraint, duality, separable structured convex optimization, alternating direction method of multipliers, Nesterov's acceleration technique