An Inexact Nonsmooth Quadratic Regularization Algorithm

The quadratic regularization technique is widely used in the literature for constructing efficient algorithms, particularly for solving nonsmooth optimization problems. We propose an inexact nonsmooth quadratic regularization algorithm for solving large-scale optimization, which involves a large-scale smooth separable item and a nonsmooth one. The main difference between our algorithm and the (exact) quadratic regularization algorithm is that it employs inexact gradients instead of the full gradients of the smooth item. Also, a slightly different update rule for the regularization parameters is adopted for easier implementation. Under certain assumptions, it is proved that the algorithm achieves a first-order approximate critical point of the problem, and the iteration complexity of the algorithm is O(ε−2). In the end, we apply the algorithm to solve LASSO problems. The numerical results show that the inexact algorithm is more efficient than the corresponding exact one in large-scale cases.