A Block Symmetric Gauss-Seidel Decomposition Theorem for Convex Composite QP and its Applications to Multi-block ADMM

报告人：Toh Kim-Chuan（卓金全）教授

报告题目：A Block Symmetric Gauss-Seidel Decomposition Theorem for Convex Composite QP and its Applications to Multi-block ADMM

报告时间：2018年5月28日16:00-17:00

报告地点：工商管理楼200-9

摘要:

For a symmetric positive semidefinite linear system of equations ${cal Q} x = b$, where $x = (x_1,ldots,x_s)$ is partitioned into $s$ blocks of sub-vectors $x_1,ldots,x_s$, with $s geq 2$, we show that each cycle of the classical block symmetric Gauss-Seidel (block sGS) method exactly solves the associated quadratic programming (QP) problem but  added with an extra proximal term of the form $rac{1}{2}|x-x^k|_{cal T}^2$,  where ${cal T}$ is a symmetric positive semidefinite matrix related to the sGS decomposition of ${cal Q}$  and  $x^k$ is the previous iterate.

By leveraging on such a connection to optimization, we are able to extend the result (which we name as the  block sGS decomposition theorem) for solving convex composite QP (CCQP) with an additional possibly nonsmooth term in $x_1$, i.e., $min{ p(x_1) + rac{1}{2}langle x, {cal Q} xangle -langle b, x angle$, where $p(cdot)$ is a proper closed convex function.

Based on the block sGS decomposition theorem, we extend the classical block sGS method to solve   CCQP. In addition, our extended block sGS method has the flexibility of allowing for inexact computation in each step of the block sGS cycle. At the same time, we can also accelerate the inexact block sGS method to achieve an iteration complexity of $O(1/k^2)$ after performing $k$ cycles. As a fundamental building block, the block sGS decomposition theorem has played a key role in various recently developed algorithms such as the inexact semiproximal {ALM/ADMM} for linearly constrained multi-block convex composite conic programming (CCCP), and the accelerated block coordinate descent method for multi-block CCCP.

报告人简介：

Toh Kim-Chuan（卓金全），新加坡国立大学教授，新加坡国立大学数学系系副主任，Provost's Chair, Deputy Head for Research & Graduate Programmes。1990年以优异成绩本科毕业于新加坡国立大学数学系；1992年获新加坡国立大学数学系硕士学位，1994年获美国康奈尔大学应用数学硕士学位；1996年获美国康奈尔大学应用数学博士学位（师从国际数值计算专家Lloyd N. Trefethen教授），1996年至今执教新加坡国立大学数学系。Toh教授是国际知名数值优化专家，主要致力于矩阵优化、二阶锥规划、凸规划等方面的算法设计、分析与实现。Toh教授及其合作者研制的软件被学术界和工业界广泛使用，如用于计算半定规划、二阶规划、线性规划的免费软件SDPT3，SDPNAL被广泛使用。Toh教授在Mathematical Programming, SIAM Journal on Optimization, SIAM Journal on Matrix Analysis and Applications等国际知名期刊发表论文60余篇，Toh教授的研究结果被广泛引用，被引4836次。Toh教授于2007年获新加坡国立大学杰出科学家奖，2010年在SIAM年会上做大会报告，并多次担任国际重要学术会议的组织成员。Toh教授荣获了2017年Farkas奖，2018年当选SIAM Fellow，现任优化著名杂志SIAM Journal on Optimization副主编，Mathematical Programming Series B副主编，担任Mathematical Programming Computation杂志区域主编, 担任Optimization and Engineering, Numerical Algebra, Control and Optimization, Pacific Journal of Mathematics for Industry 等多个杂志的编委。

联系人：梁克维（matlkw@zju.edu.cn）