Please use this identifier to cite or link to this item:
Title: A block symmetric Gauss–Seidel decomposition theorem for convex composite quadratic programming and its applications
Authors: Li, X
Sun, D 
Toh, KC
Keywords: Augmented Lagrangian method
Block symmetric Gauss–Seidel
Convex composite quadratic programming
Schur complement
Issue Date: 2019
Publisher: Springer
Source: Mathematical programming, 2019, v. 175, no. 1-2, p.395-418 How to cite?
Journal: Mathematical programming 
Abstract: For a symmetric positive semidefinite linear system of equations Qx= b, where x= (x 1 , … , x s ) is partitioned into s blocks, with s≥ 2 , we show that each cycle of the classical block symmetric Gauss–Seidel (sGS) method exactly solves the associated quadratic programming (QP) problem but added with an extra proximal term of the form 12‖x-xk‖T2, where T is a symmetric positive semidefinite matrix related to the sGS decomposition of 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(x1)+12⟨x,Qx⟩-⟨b,x⟩}, where p(·) 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.
[for formular please refer to the text]
ISSN: 0025-5610
DOI: 10.1007/s10107-018-1247-7
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Citations as of Oct 22, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.