Cubic Regularization Algorithm For The Second Order Minimizer Of Sparse Optimization

In this paper,a class of sparse optimization models with nonconvex continuous penalty function is considered.This kind of model has a wide range of applications in signal processing,regression analysis,compressed sensing and image processing.It is one of the most popular research topics in optimization field in recent years.Specifically,the model with Capped-₁l penalty function is our research object in this paper.First of all,we consider the algorithm searching for the first-order minimizer of the sparse optimization model,and we select the lifted-stable point as the first-order minimum point.We construct an algorithm searching for the lifted stable point of the sparse optimization model via the special properties of the Capped-₁l function and the idea of cubic regularization.Since a constrained convex optimization subproblem is involved in the algorithm,we analyze the convergence behavior of the iterative sequence generated by the algorithm by means of the first-order optimality necessary and sufficient condition of convex optimization.Under some suitable assumptions,the properties of a class of special points in the iterative sequence of the algorithm are studied.Finally,it is proved that any accumulation point of the iterative sequence has a common lower bound property.Following the idea of searching for the first-order minimum point,the algorithm for the second-order minimum point of the original model is further discussed.According to an approximate high-order optimality condition of unconstrained optimi-zation problem,the definition of the approximate second-order minimum point of the sparse optimization model is then put forward and the algorithm that can solve the approximate second-order minimizer is constructed by means of designing the conditions for the solution of the subproblem.We discuss the existence of the solution of the subproblem and the rationality of the output point of the algorithm.Under certain conditions,the worst-case iteration complexity of the algorithm is obtained:the algorithm is terminated in a finite step,which indicates that the algorithm is globally convergent.