The Study Of Alternative Direction Method Of Multipliers With Substitution And Error Bounds

This thesis mainly studies the alternating direction method of multipliers with a substitution of multi-block optimization problems and error bounds theo-ry. Multi-block optimization problem has a wide range of applications in many practical problems including signal processing, wireless networking and smart grid provisioning. Since the alternating direction method of multipliers (ADMM) takes advantage of the separable structure of 2-block optimization problems, it is very efficient for solving 2-block optimization problems. However, the direct extension of ADMM to the multi-block case is not necessarily convergent. So the research on the convergence condition of the ADMM and more faster and efficient optimization algorithms for solving muti-block optimization problems are urgently demanded. Alternating direction method of multipliers with a substitution is among the most efficient algorithms for solving multi-block optimization problems. Error bounds theory is an important research content of optimization theory. Error bounds have important applications in sensitivity analysis of mathematical programming and convergence analysis of the algorithms. It is mainly to provide characterizations and criteria for the error bound property in terms of various derivative-like objects which live either in the primal space or in the dual space (directional derivatives, slopes, subdifferentials, normal cones, etc).Firstly, this thesis studies the alternating direction method of multipliers (with a substitution) of multi-block optimization problems, the main research works are as follows:Chapter 2 shows the global convergence of linearized al-ternating direction method of multipliers for multi-block optimization problems when the involved functions are strongly convex. By using the linear technology and the idea of alternating direction method of multipliers, Chapter 3 propos-es a linearized alternating direction method of multipliers with substitution for the multi-block optimization problems. Due to the linearization technique, the proposed algorithm simplifies the structure of the subproblem at each iteration so that, the subproblems are easier to be solved than the traditional alternating direction method of multipliers. The preliminary numerical results show that the proposed algorithm is stable and efficient. Chapter 4 considers the optimization problem with minimizing the sum of a smooth convex function and a separable convex function subject to linear coupling constraints. Because of containing the inseparable part, such optimization problem can not be solved by the existing alternating direction method of multipliers (with a substitution). With the help of the smoothness of the inseparable part and combined with the block coordi-nate descent algorithm and the alternating direction method of multipliers with a substitution, we propose a new algorithm to solve this family of problems. The proposed algorithm is called the proximal block minimization method of multi-pliers with a substitution. Numerical results show that the proposed algorithm is stable and efficient. Chapter 5 considers the multi-block optimization problem whose functions consist of two terms:one is smooth and the other is a general convex function, which is solved by a gradient-based alternating direction method of multipliers with a substitution. Numerical results show that the proposed algo-rithm is efficient. Furthermore, if each function is strongly convex, we prove that the substitution could be removed.Secondly, considering the error bounds theory of functions. Chapter 6 consid- ers the error bounds of lower semicontinuous functions. We show some characteri-zations of linear and nonlinear error bounds for lower semicontinuous functions by a new notion, called subslope. In particular, we introduce a sufficient and neces-sary condition for global linear error bound. Chapter 7 examines the error bounds of proper functions. We define two new concepts which are called closed strong slope and closed global slope respectively. According to two new concepts, some characterizations of the existence of the global and local error bounds are given for proper functions. Meanwhile, we give a necessary and sufficient condition of global error bound for proper functions. Particularly, we show several necessary and sufficient conditions of global error bound for proper convex functions defined on Euclidean space. As the applications of error bounds theory, we characterize linear and nonlinear metric regularity and subregularity.