A coordinate gradient descent method for structured nonsmooth optimization.

摘要

We consider the problem of minimizing the sum of a smooth function and a (block separable) convex function with or without linear constraints. This problem includes as special cases bound-constrained optimization, smooth optimization with ℓ1-regularization, and linearly constrained smooth optimization such as a large-scale quadratic programming problem arising 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, highly parallelizable, and suited for large-scale applications in signal/image denoising, regression, and data mining/classification. We establish global convergence and, under a local Lipschitzian error bound assumption, local linear rate of convergence for this method. The local Lipschitzian error bound holds under assumptions analogous to those for constrained smooth optimization, e.g., the convex function is polyhedral and the smooth function is (nonconvex) quadratic or is the composition of a strongly convex function with a linear mapping. We report our numerical experience with solving the ℓ 1-regularization of unconstrained optimization problems from More et al. [73] and from the CUTEr set [38] and some large-scale quadratic program of support vector machines arising from two-class data classification. Comparison with L-BFGS-B and MINOS, applied to a reformulation of the ℓ1-regularized problem as a bound-constrained smooth optimization problem, is reported. Comparison with LIBSVM on large-scale quadratic programming problems of support vector machines is also reported.; In addition, we consider the bi-level problem which minimizes a nonsmooth convex function over the set of stationary points of a certain smooth function. If the smooth function is convex, the convex function is proper, level-bounded, lower semi-continuous, and the set of stationary points of the smooth function over the domain of the convex function is nonempty, a regularization strategy for solving this bi-level problem is proposed for a (block) coordinate gradient descent method. We prove that any cluster point of the generated iterates is a solution of the bi-level problem.