A random coordinate descent algorithm for large-scale sparse nonconvex optimization

In this paper we develop a random coordinate descent method suitable for solving large-scale sparse nonconvex optimization problems with composite objective function. Under the typical assumptions of nonconvexity of the smooth part of the objective function and separability and convexity of the nonsmooth part (e.g. ℓ₁ regularization, box indicator functions or others), we derive an algorithm with a very simple and cheap iteration. We prove sublinear convergence rate for our method to a stationary point. Numerical results show that our algorithm performs favourably in comparison to other algorithms on large-scale sparse nonconvex problems, e.g. the eigenvalue complementarity problem arising in different areas such as stability of dynamical systems, distributed control and resonance frequency of mechanical structures with friction.