北京科学与工程计算研究院学术报告之六十六

报告人/Speaker: Sun Defeng, Department of Applied Mathematics, The Hong Kong Polytechnic University


报告题目/Title: A block symmetric Gauss-Seidel decomposition theorem and its applications in big data nonsmooth optimization


时间/Date & Time: June 24, 2018, 14:00—15:00


地点/Venue:北京科学与工程计算研究院M843会议室


报告摘要/Abstract

The Gauss-Seidel method is a classical iterative method of solving the linear system Qx =b. It has long been known to be convergent when Q is symmetric positive definite. In this talk, we shall focus on introducing a symmetric version of the Gauss-Seidel method and its elegant extensions in solving big data nonsmooth optimization problems. For a symmetric positive semidefinite linear system Qx = b with x = (x_1,…,x_s) being partitioned into s blocks, we show that each cycle of the block symmetric Gauss-Seidel (block sGS) method exactly solves the associated quadratic programming (QP) problem but  added with an extra proximal term. By leveraging on such a connection to optimization, one can extend the classical convergent result, named as the block sGS decomposition theorem, to solve a convex composite QP (CCQP) with an additional nonsmooth term in x_1. Consequently, one is able to use the sGS method to solve a CCQP. In addition, the extended block sGS method has the flexibility of allowing for inexact computation in each step of the block sGS cycle. At the same time, one can also accelerate the inexact block sGS method to achieve an iteration complexity of O(1/k^2) after performing k block sGS cycles. As a fundamental building block, the block sGS decomposition theorem has played a key role in various recently developed algorithms such as the proximal ALM/ADMM for linearly constrained multi-block convex composite conic programming (CCCP) and the accelerated block coordinate descent method for multi-block CCCP.


报告人简介/About the speaker:

Prof. Sun Defeng is Chair Professor of Applied Optimization and Operations Research at Department of Applied Mathematics in The Hong Kong Polytechnic University. His research interests include Matrix Optimization, High-Dimensional Statistical Optimization, Second Order Variational Analysis and Risk Management and Computational Finance. He is the associate editor of SIAM Journal on Optimization, Journal of the Operations Research Society of China,  Science China Mathematics, and etc.