A memory gradient method for non-smooth convex optimization

Abstract

Based on the Moreau–Yosida regularization and a modified line search technique, this paper presents an implementable memory gradient method for solving a possibly non-differentiable convex minimization problem by converting the original objective function to a once continuously differentiable function. A main feature of this proposed method is that at each iteration, it sufficiently uses the previous multi-step iterative information and avoids the storage and computation of some matrices. Moreover, the proposed method makes use of approximate function and gradient values of the Moreau–Yosida regularization instead of the corresponding exact values. Under reasonable conditions, the convergence properties of the proposed algorithm are analysed. Preliminary numerical results show that the proposed method is efficient and can be applied to solve large-scale non-smooth optimization problems.

Keywords:

• non-smooth convex optimization
• memory gradient method
• non-monotone line search
• convergence analysis

2000 AMS Subject Classifications:

• 90C30
• 65K05
• 49M37

Acknowledgements

The authors would like to thank the anonymous referees and the editor for their patience and valuable comments and suggestions that greatly improved this paper. Supported by NNSF of China (No.11261015) and NSF of Hainan Province (No. 111001)