Linearized Alternating Direction Method For Solving Separable Convex Optimization Problems

Convex programming and variational inequality problem arise frequently from many fields. They not only have become important tools for studying a wide class problems arising from mathematics, engineering science and management science, but also have wide applications in mathematical programming, traffic equilibrium, network economics, game theory and image processing. Consequently, designing effective algorithm for solving these problems is always a hot research topic.Recently, there are many feasible algorithms to solve multi-block separable con-vex minimization problems, and the alternating direction method of multipliers (ADMM) is one of the most effective algorithm. Moreover, linearization technique is a useful tool to make the subproblems in the ADMM easy to solve, which is essential for the success of ADMM in some applications. Due to the absence of con-vergence guarantee of the direct extension of the classic ADMM to the multi-block case, He and Yuan [26] recently proposed a block-wise ADMM, which grouped the multi-block variables into two groups and then adopted the classic ADMM to the resulting model.Based on the block-wise ADMM in [26], in chapter 2, we adopt the linearization technique in the block-wise alternating direction method of multipliers and propose three linearized block-wise ADMM algorithms, which linearize the objective func-tions, or the quadratic terms, or both of them, respectively. And under some mild conditions, we prove the global convergence of the proposed algorithm.In chapter 3, we apply our algorithms to solve the convex quadratic program-ming problem with separable structure and image decomposition, and compare with some other algorithms. We also report some preliminary numerical results, indicat-ing the feasibility and effectiveness of the linearization strategy.