A Coordinate Gradient Descent Method for Structured Nonsmooth Optimization

Nonsmooth optimization problems are generally considered to be moredifficult than smooth problems. Yet, there is an important class ofnonsmooth problems that lie in between. In this book, we consider the problem of minimizing the sum of a smoothfunction and a (block separable) convex function with or without linear constraints. This problem includes as special casesbound-constrained optimization, smooth optimization withL_1-regularization, and linearly constrained smoothoptimization such as a large-scale quadratic programming problemarising in the training of support vector machines. We propose a block coordinate gradient descent method for solving this class of structured nonsmooth problems. The method is simple, highlyparallelizable, and suited for large-scale applications insignal/image denoising, regression, and data mining/classification. We establish global convergence and, under a local Lipschitzianerror bound assumption,local linear rate of convergence for this method. Ournumerical experiences suggest that our method is effective in practice. This book is helpful to the people who are interested in solving large-scale optimization problems.