Random Coordinate Descent Methods for Sparse Optimization: Application to Sparse Control

In this paper we analyze a family of general random block coordinate descent methods for the minimization of ℓ₀ regularized optimization problems, i.e. The objective function is composed of a smooth convex function and the ℓ₀ regularization. Our family of methods covers particular cases such as random block coordinate gradient descent and random proximal coordinate descent methods. We analyze necessary optimality conditions for this nonconvex ℓ₀ regularized problem and devise a separation of the set of local minima into restricted classes based on approximation versions of the objective function. We provide a unified analysis of the almost sure convergence for this family of block coordinate descent algorithms and prove that, for each approximation version, the limit points are local minima from the corresponding restricted class of local minimizers.