Block-Coordinate Gradient Descent Method for?Linearly Constrained Nonsmooth Separable Optimization

详细信息    查看全文

• 作者：P. Tseng ; S. Yun
• 关键词：Nonsmooth optimization ; Linear constraints ; Support vector machines ; Bilevel optimization ; ℓ ; ₁ ; regularization ; Coordinate gradient descent ; Global convergence ; Linear convergence rate ; Complexity bound
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2009
• 出版时间：March, 2009
• 年：2009
• 卷：140
• 期：3
• 页码：513-535
• 全文大小：506.1 KB

文摘

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 ²/ε) 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 ²) 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.