A study on augmented Lagrangian-based splitting methods for separable convex programming

• Main Author: Wang, Kai
• Other Authors: Jitamitra Desai
• Format: Theses and Dissertations
• Language: English
• Published: 2017
• Subjects: DRNTU::Engineering::Industrial engineering::Operations research
• Online Access: http://hdl.handle.net/10356/73066
• Institution: Nanyang Technological University

Convex programming has played an important role in studying a wide class of applications arising from computer science, statistics, industrial engineering, and management. Moreover, the advent of big-data analytics has resulted in very large-scale structural convex programming problems, thereby necessitating the research towards devising fast numerical algorithms for solving such problems. The goal of this thesis is to propose some efficient augmented Lagrangian-based splitting methods for solving the convex programming problem, provide an in-depth study of the convergence and convergence rate properties of these algorithms, and discuss computational results that establish the efficiency of these methods. Towards this end, we first consider the linearly constrained separable convex minimization problem, whose objective function consists of the sum of m individual convex functions in the absence of any coupling variables. This work shows that a straightforward Jacobian decomposition of the augmented Lagrangian method is globally convergent if the involved functions are further assumed to be strongly convex. Furthermore, we also analyze the sublinear and linear convergence rate under some corresponding assumptions. Then, we propose a proximal partially parallel splitting method for solving separable convex optimization problems. The proposed method is a hybrid mechanism that combines the nice features of Gauss-Seidel and Jacobian decomposition methods, while simultaneously adopting the predictor-corrector strategy to ensure convergence. Furthermore, the worst-case convergence rate O(1/t) of the proposed method is obtained under both ergodic and non-ergodic conditions. The efficiency of the proposed algorithm is also demonstrated by solving several instances of the Robust PCA problem. Next, continuing in the same vein, we present a portfolio of linearized versions of this method, which can be gainfully employed when the underlying subproblems possess some structural properties, and showcase the computational effectiveness of this method on standard test instances taken from the literature.