Please use this identifier to cite or link to this item:
Title: Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
Authors: Tseng, P.
Yun, S. 
Keywords: ℓ1-regularization
Bilevel optimization
Complexity bound
Coordinate gradient descent
Global convergence
Linear constraints
Linear convergence rate
Nonsmooth optimization
Support vector machines
Issue Date: Mar-2009
Citation: Tseng, P., Yun, S. (2009-03). Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization. Journal of Optimization Theory and Applications 140 (3) : 513-535. ScholarBank@NUS Repository.
Abstract: We consider the problem of minimizing the weighted sum of a smooth function f and a convex function P of n real variables subject to m linear equality constraints. We propose a block-coordinate gradient descent method for solving this problem, with the coordinate block chosen by a Gauss-Southwell-q rule based on sufficient predicted descent. We establish global convergence to first-order stationarity for this method and, under a local error bound assumption, linear rate of convergence. If f is convex with Lipschitz continuous gradient, then the method terminates in O(n 2/ε) iterations with an ε-optimal solution. If P is separable, then the Gauss-Southwell-q rule is implementable in O(n) operations when m=1 and in O(n 2) operations when m>1. In the special case of support vector machines training, for which f is convex quadratic, P is separable, and m=1, this complexity bound is comparable to the best known bound for decomposition methods. If f is convex, then, by gradually reducing the weight on P to zero, the method can be adapted to solve the bilevel problem of minimizing P over the set of minima of f+δ X , where X denotes the closure of the feasible set. This has application in the least 1-norm solution of maximum-likelihood estimation. © 2008 Springer Science+Business Media, LLC.
Source Title: Journal of Optimization Theory and Applications
ISSN: 00223239
DOI: 10.1007/s10957-008-9458-3
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Nov 23, 2022


checked on Nov 23, 2022

Page view(s)

checked on Nov 24, 2022

Google ScholarTM



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