Algorithms Research For Sloving Box-Constrained L₂-L_p Minimization Problems

In recent years,the L2-Lp(0<p<1)box-constrained minimization problem has been widely applied in signal reconstruction and variable selection.However,it is a class of nonsmooth,nonconvex and non-Lipschitz continuous constrained optimiza-tion problem,which is very difficult to solve.In general,this type of problem is NP hard.This thesis is devoted to the research of numerical algorithms for solving such problems.The main tasks of this paper are as follows:First of all,we transform the original problem to a box-constrained minimization problem whose objective function is continuously differentiable on the constraint do-main and its gradient function is Lipschitz continuous by variable substitution.We prove that the original problem is equivalent to the transformation problem and show the KKT condition for the equivalent problem.In addition,we also use the projection operator to obtain the necessary and sufficient conditions that the feasible solution is a KKT point.Secondly,based on the equivalent problem,we have designed the first-order in-terior point method,active set method and gradient projection method to solve the problem of L2-Lp box-constrained minimization problem.For first-order interior point method,we first give the definition of ?-KKT point and prove that after iterating O(?-2)times,we can get a ?-KKT point by the algorithm.For active set method,we present the classification rules of the working set and we solve iterative subproblems for obtaining the search direction by the conjugate gradient method.we also show that the iteration point sequence generated by the active set algorithm converges to a KKT point of the equivalent problem.For the gradient projection method,we prove that the iteration point sequence generated by the gradient projection algorithm converges to a KKT point of the equivalent problem.Last but not least,By using these three algorithms to solve the compression sens-ing problem,we verify the validity of these algorithms and the numerical results show that the gradient projection algorithm is superior.