  Nonconvex optimization problems arise in many areas of computational science
and engineering and are (approximately) solved by a variety of algorithms.
Existing algorithms usually only have local convergence or subsequence
convergence of their iterates. We propose an algorithm for a generic nonconvex
optimization formulation, establish the convergence of its whole iterate
sequence to a critical point along with a rate of convergence, and numerically
demonstrate its efficiency.
  Specially, we consider the problem of minimizing a nonconvex objective
function. Its variables can be treated as one block or be partitioned into
multiple disjoint blocks. It is assumed that each non-differentiable component
of the objective function or each constraint applies to one block of variables.
The differentiable components of the objective function, however, can apply to
one or multiple blocks of variables together.
  Our algorithm updates one block of variables at time by minimizing a certain
prox-linear surrogate. The order of update can be either deterministic or
randomly shuffled in each round. We obtain the convergence of the whole iterate
sequence under fairly loose conditions including, in particular, the
Kurdyka-{\L}ojasiewicz (KL) condition, which is satisfied by a broad class of
nonconvex/nonsmooth applications.
  We apply our convergence result to the coordinate descent method for
non-convex regularized linear regression and also a modified rank-one residue
iteration method for nonnegative matrix factorization. We show that both the
methods have global convergence. Numerically, we test our algorithm on
nonnegative matrix and tensor factorization problems, with random shuffling
enable to avoid local solutions.

Optimization and Control