Optimality Theory And Algorithms For Sparsity Constrained Optimization

The sparsity constrained optimization is to minimize a general nonlinear function subject to a set constrained by sparsity.It has wide applications in regression analysis,signal and image processing,machine learning,pattern recognition.Recent years,it has attracted much attention and is a hot research topic.The sparsity constrained optimization is a mixed combinatorial optimization and is NP-hard.Speaking in general terms,continuous optimization theory is usually un?able to be applicable to a combinatorial optimization problem.However,the special structure of sparsity constrained set provides Lus with an interesting and challenging research topic.In this thesis,we mainly aim to study the optimality theory of the s-parsity constrained optimization.Relying on the tangent cones and normal cones to the feasible set,from specific to general,we study the optimality theory and constraint qualification from the only sparsity constrained optimization to the sparsity constrained cone optimization.These proposed optimality condition,s,to some extent,enrich the optimization theory for noncontinuous and non-convex programming problems.For the only sparsity constrained optimization,we characterize the expressions of Bouligand and Clarke tangent cones and Frechet and Clarke normal cones of sparsi-ty constraint.Base on these expressions,we present and characterize two first-order necessary optimality conditions for sparsity constrained optimization:N-stationarity and T-stationarity.Then we give the second-order necessary and sufficient optimality conditions for sparsity constrained optimization.We extend our results to the nonneg-ativity and sparsity constrained optimization,and consider the N-stationarity and the T-stationarity and second-order optimality conditions.For the sparsity constrained nonlinear programming,we first define two restricted constraint qualifications and show how these constraint qualifications can be applied to obtain the decomposition properties of the Frechct,Mordukhovich and Clarke normal cones to the sparsity constrained feasible set.Based on the decomposition properties of the normal cones,we then present and analyze three classes of Karush-Kuhn-Tucker(KKT)conditions for the problem.At last,we establish the second-order necessary optimality condition and sufficient optimality condition for the nonlinearity and sparsity constrained optimization.For the sparsity constrained cone programming,we introduce a restricted form of strict Robinson constraint qualification.Then we establish the first-order optimali-ty conditions for the sparsity constrained cone optimization based upon the properties of the normal cone.After further characterizing the second-order tangent set to the cardinality-constrained system,we also present the second-order optimality condition under some mild conditions.For the sparsity fand nonnegativity constrained optimization,we introduce the re-stricted strong convexity\smoothness and analyze the relationships between ?-stationary point,B-stationary point,C-stationary point,local minirmizer and global minimizer in detail,we give an improved iterative hard thresholding(IIHT)algorithm for solving the nonnegative sparsity optimization by employing the Armijo-type stepsize rule,which automatically adjusts the stepsize.The IIHT algorithm enjoys good convergence prop-erties under standard assumptions.Those include the convergence to the local mini-mizer,the finite identification of the true support,set,the linear convergence of rate of both the iteration points and its function values.Extensive numerical experiments are included to demonstrate the good performance of the proposed algorithm.