Optimality Theory And Algorithm For Sparse Nonlinear Programming

Sparse optimization has wide applications in signal reconstruction,image restoration,model identification,variable selection and other fields.For example,in real life,the signal is often sparse or under some transform domains--such as Fourier transform,wavelet transform and curvelet transform,etc.--the representation of a signal which is not sparse also shows characteristics of the most sparse approximation is zero.In this case,we only need store and transfer the signal with large coefficient and it is enough to reconstruct the original signal.In this paper,we study the theory and algorithm for sparse nonlinear programming.The details are given as follows:(1)We define the restricted Slater constraint qualification.Based on the constraint qualification,we establish the relationship between local solution and Karush-Kuhn-Tucker(KKT)conditions of sparse nonlinear programming.In addition,we provide the specific expression of the first order necessary optimality condition of sparse constraint nonlinear programming with box constraint.(2)We consider three types of sparse nonlinear programming problems: 1)Nonlinear programming with sparse constraints;2)Nonlinear programming with sparse regular item;3)Nonlinear programming with sparse regular item and penalty item.We introduce their optimality conditions,which include first order and second order optimality conditions.Using restricted Mangasarian Fromovitz constraint qualification and the decomposition properties of normal cones to the sparse constrained feasible set,we analyze the relationship of stable points among these problems.Base on properties of continuous differentiable functions,sparse regular item and local optimal solutions,we get the relationship of local optimal solutions among these problems.Finally,we analyze the relationship of global optimal solutions by limiting iterative method.(3)For sparse constraint optimization problem with box constraint,we design two effective algorithms.Under the condition with a general box constraint,we design the coordinate gradient algorithm and analyze its convergence property.For the problem with a nonnegative box constraint,we analyze the project process of a point to feasible set and usethe improved iterative hard thresholding algorithm to solve this problem.(4)Finally,by our algorithm,we introduce three kinds of numerical experiments:Stochastic problem simulation,Sparse signal recovery and Image restoration and corresponding results.