A Perturbed DCA for Computing d-Stationary Points of Nonsmooth DC Programs

Abstract

This paper introduces an efficient perturbed difference-of-convex algorithm (perturbed DCA) for computing d-stationary points of an important class of structured nonsmooth difference-of-convex problems. Compared to the principal algorithms introduced in [J.-S. Pang, M. Razaviyayn, and A. Alvarado, Math. Oper. Res. 42(1):95--118 (2017)], which may require solving several subproblems for a one-step update, perturbed DCA only requires solving a single subproblem. Therefore, the per-iteration computational cost of perturbed DCA is comparable to the widely used difference-of-convex algorithm (DCA) introduced in [D. T. Pham and H. A. Le Thi, Acta Math. Vietnam. 22(1):289--355 (1997)] for computing a critical point. We establish the subsequential and almost sure convergence of the perturbed DCA to d-stationary points under certain conditions. To decouple the perturbation radii from the local convergence rate of the iterates, we further propose a hybrid variant of the perturbed DCA that independently samples the perturbation radius and direction with a safeguard using a proximal DCA step. Importantly, under more relaxed and practical assumptions, we prove that every accumulation point of the sequence generated by the hybrid perturbed DCA is a d-stationary point almost surely. Numerical results on several important examples demonstrate the efficiency of the proposed methods for computing d-stationary points.