Semi-Proximal Alternating Direction Method Of Multipliers For Sparse Inverse Covariance Matrices Estimation

Covariance matrix estimation is a classical problem in the field of statistics, and it is widely used in the high-dimensional data analysis, such as economy, finance, social networks and gene sequencing. Because of its simple iteration and low storage capacity,alternating direction method of multipliers is efficient for separable convex optimization problems. The semi-proximal alternating direction method of multipliers with symmetric Gauss-Seidel technique is more effective for multi-block separable optimization problem-s under the background of big data, which can effectively decompose an optimization problem into several relatively simple sub-problems. In this thesis, we will focus on the applications of the semi-proximal alternating direction method of multipliers with sym-metric Gauss-Seidel technique in the sparse inverse covariance estimation problems, and analyze the convergence of the algorithm. Finally the effectiveness of the proposed algo-rithms are tested by using synthetic and real data.In Chapter one, we simply introduce covariance matrix estimation problems and the related models, then review some well-known algorithms for solving corresponding models. We introduce the basic knowledges of optimization, review the alternating di-rection method of multipliers and its development process, and give the corresponding convergence theorem. We also introduce the symmetric Gauss-Seidel technique and the semi-proximal alternating direction method of multipliers for multi-block convex opti-mization problem, state the main motivation and contributions of this thesis, and list some symbols and concepts which will be used in the sequent chapters.In Chapter two, we derive the dual problem of the sparse inverse covariance ma-trix estimation model, and solve subsequently by the semi-proximal alternating direction method of multipliers with symmetric Gauss-Seidel technique. We analyze the equiva-lence between the proposed algorithm and the two-block semi-proximal alternating direc-tion method of multipliers theoretically, then the convergence of the algorithm is followed directly. Finally, the pra.ctical performance of the proposed algorithm is tested by using synthetic data and gene network data.In Chapter three, we improve the original model which is proposed in the second chapter, and present a more general inverse covariance matrix estimation model. We derive the dual problem of the proposed model. Furthermore, combing with parallel computing, we solve the dual problem by the semi-proximal alternating direction method of multipliers with symmetric Gauss-Seidel technique. We show theoretically that the proposed algorithm is equivalent to the two-block semi-proximal alternating direction method of multipliers, which means that the convergence of the algorithm is guaranteed.Finally, the effectiveness of the proposed algorithm and the advantage of the new model are tested by using synthetic data and gene network data.In Chapter four, we conclude the thesis and propose some further research topics.