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

报  告  人: Sun Defeng (The Hong Kong Polytechnic University)

报告时间：2018年8月11日，9:00-11:30

报告地点：数计学院2号楼229报告厅

报告摘要: The Gauss-Seidel method is a classical iterative method of solving the linear system Ax =b. It has long been known to be convergent when A 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 Ax = 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.

报告人简介: Professor Sun Defeng is currently Chair Professor of Applied Optimization and Operations Research at the Hong Kong Polytechnic University.   Before moving to Hong Kong in August 2017, Professor Sun served as Professor at Department of Mathematics, National University of Singapore, Deputy Director (Research) at the NUS Risk Management Institute and Program Director for its Master of Financial Engineering program. He mainly publishes in continuous optimization. He has written a number of software for solving large-scale complex optimization problems, including SDPNAL/SDPNAL+ for general purpose large scale semidefinite programming,   codes for correlation matrix calibrations and most recently the packages including LassoNAL for various statistical regression models. Currently Professor Sun focuses on establishing the foundation for the next generation methodologies for big data optimization and applications. Professor Sun has actively involved in many professional activities. He served as editor-in-chief of Asia-Pacific Journal of Operational Research from 2011 to 2013 and he now serves as associate editor of Mathematical Programming, SIAM Journal on Optimization, Journal of the Operations Research Society of China, Journal of Computational Mathematics, and Science China: Mathematics.    Together with Professor Kim-Chuan Toh and Dr Liuqin Yang, he is awarded the triennial Beale--Orchard-Hays Prize for Excellence in Computational Mathematical Programming 2018 by the Mathematical Optimization Society.