A Coordinate Gradient Descent Method for Nonsmooth Nonseparable Minimization
Zheng-Jian Bai 1, Michael K. Ng 2*, Liqun Qi 31 School of Mathematical Sciences, Xiamen University, Xiamen 361005, China.
2 Centre for Mathematical Imaging and Vision and Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong.
3 Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Hong Kong.
Received 18 February 2009; Accepted (in revised version) 9 June 2009
This paper presents a coordinate gradient descent approach for minimizing the sum of a smooth function and a nonseparable convex function. We find a search direction by solving a subproblem obtained by a second-order approximation of the smooth function and adding a separable convex function. Under a local Lipschitzian error bound assumption, we show that the algorithm possesses global and local linear convergence properties. We also give some numerical tests (including image recovery examples) to illustrate the efficiency of the proposed method.
AMS subject classifications: 65F22, 65K05
Key words: Coordinate descent, global convergence, linear convergence rate.
Email: email@example.com (Z.-J. Bai), firstname.lastname@example.org (M. K. Ng), email@example.com (L. Qi)