Study For Multi-stage Convex Relaxation Approach To Group Zero-norm Regularized Problems

Group zero-norm optimization problems have a very wide range of applications in a diverse set of fields such as statistics,signal and image processing,machine learning,bioinformation,quantum computing,financial engineering,and so on.In this thesis,with the help of the variational characterization of the group zero-norm,we reformulate the group zero-norm regularized minimization problem into an equivalent globally Lipschitz continuous optimization model with the desirable bilinear structure,and then design and investigate the multi-stage convex relaxation approach to this class of problems with a ceratin combinatorial property.This thesis,starting from the variational characterization of the group zero-norm,reformulates the group zero-norm regularized problem as a mathematical program with a complementarity constraint(MPCC)and shows that its penalty version,yielded by moving the complementarity constraint into the objective,is a global exact penalty of the MPCC problem itself.The objective function of the exact penalty problem is not only globally Lipschitz continuous in the feasible set but also has the bilinear structure,thereby providing a desirable equivalent Lipschitz optimization model for designing sequential convex relaxation algorithms for the group zero-norm regularized problem.Then,by solving the equivalent global Lipschitz continuous optimization model in an alternating way,the thesis designs a multi-stage convex relaxation approach to the group zero-norm regularized minimization problem.This approach is solving at each step a con-vex minimization problem with simple constraints.In particular,for the group zero-norm regularized least squares problem,under a restricted strong convexity condition weaker than the group restricted isometry property(RIP),the thesis quantitatively character-izes the Euclidean norm error bound for the optimal solution of each stage,and verifies that the group zero-norm of the optimal solution in each stage is decreasing and keeps invariant after some stages and exactly identifies the support set of the true solution.Lastly,the thesis applies the proposed multi-stage convex relaxation approach to some group zero-norm vector recovery problems generated randomly to confirm the cor-rectness of the obtained theoretical results;and verifies its efficiency for the group zero-norm vector recovery problems by making numerical comparisons with the accelerated gradient method(SLEP)and separable approximation method(SpaRSA),which are the classical methods to solve the group zero-norm regularized least squares problem.