CENTER FOR COMPUTATION & TECHNOLOGY

Optimization has been applied in many areas including engineering, statistics, finance, and data sciences. Modern applications
often have rich structure information. Traditional methods like projected subgradient and the augmented Lagrangian can be used, but they do not utilize structures of the problems and thus are not so efficient. This talk will focus on convex optimization problems with affine constraints. The first part assumes two-block structure on the problem and presents the alternating direction method of multipliers (ADMM) and its accelerated variant. With strong convexity on one block variable, the ADMM can be accelerated from O(1/k) rate to O(1/k^2). Numerical results will be given to demonstrate the improved speed. In the second part, I will present a novel primal-dual block update method for a multi-block (at least three blocks) problem. Existing works have shown that directly extending two-block ADMM to multi-block problems may diverge. To guarantee convergence, either strong assumptions are made or updating order of the blocks has to be changed. Our method uses a simple randomization technique on choosing block variables, and it enjoys O(1/k) ergodic convergence rate and also global convergence in probability. In addition, by choosing a few blocks every time and using Jacobi-type update, the method enables parallel computing with guaranteed convergence. Numerical experiments will be shown to demonstrate its efficiency compared to other methods.