Linearly Constrained Non-Lipschitz Optimization for Image Restoration

Nonsmooth nonconvex optimization models have been widely used in the restoration and reconstruction of real images. In this paper, we consider a linearly constrained optimization problem with a non-Lipschitz regularization term in the objective function which includes the lₚ norm ($0<p<1$) of the gradient of the underlying image in the l₂-lₚ problem as a special case. We prove that any cluster point of ε scaled first order stationary points satisfies a first order necessary condition for a local minimizer of the optimization problem as ε goes to $0$. We propose a smoothing quadratic regularization (SQR) method for solving the problem. At each iteration of the SQR algorithm, a new iterate is generated by solving a strongly convex quadratic problem with linear constraints. Moreover, we show that the SQR algorithm can find an ε scaled first order stationary point in at most O(ε⁻²) iterations from any starting point. Numerical examples are given to show good performance of the SQR algorithm for image restoration.