Numerical Method For Sparse Discrete Optimization Problems

Sparse optimization problems are optimization problems which obtain sparse solutions by using optimization models and corresponding algorithms.In recent years,the sparse optimiza-tion has been heavily used in signal and image processing,compression sensing,engineering,finance,machine learning,data mining,high-dimensional statistics and other fields and became a new branch of the field of optimization.In this thesis,we mainly discuss the optimality con-ditions and the numerical algorithms for the sparse discrete optimization problems with the l0-norm.For sparse portfolio selection problems with the l0-norm this thesis proposes a new more efficient numerical algorithm and for index tracking problems this thesis proposes two new types of sparse support vector regression models and corresponding algorithms.The main results of this thesis are summarized as follows:In Chapter I and 2.we introduce the development and application of the sparse optimization problems,sparse discrete optimization problems,sparse portfolio selection problems and index tracking problems.And we also introduce some basic concepts and conclusions of the theory which will be used in this thesis.In Chapter 3,we study the optimality conditions of the sparse discrete optimization prob-lems under different constraint qualifications and propose an augmented Lagrangian proximal alternating(ALPA)method.Under some suitable assumptions,we establish that any accumu-lation point of the sequence generated by the ALPA method satisfies the first-order necessary optimality conditions of the sparse discrete optimization problems.Furthermore,under another assumption we show that any accumulation point of the sequence is also a local minimizer of these problems.The computational results demonstrate that our method can find the subopti-mal solutions of the problems efficiently and is more simple and efficient than some other local solution methods and the integer programming method.In Chapter 4,the optimality conditions of the sparse portfolio selection problems with the l0-norm are studied.For this type of problems we propose a more efficient penalty proximal alternating linearized minimization(penalty PALM)method and generalize this method to a method for solving general l0 minimization problems.Under the characteristic of the problems,we show that any accumulation point of the sequence generated by the penalty PALM method satisfies the first-order necessary optimality conditions of the problems.Furthermore,under a suitable assumption we show that such an accumulation point is also a local minimizer of the problems.The computational results with practical problems demonstrate that our method can find the suboptimal solutions of the problems efficiently and is more competitive with some other local solution methods.In Chapter 5,we propose two new types of sparse support vector regression(sparse SVR)models and the penalty PALM method for these models by combining l0-norm and support vector regression models and apply these two types of models to the index tracking problem.Under the characteristic of the problems,we also show that any accumulation point of the sequence gen-erated by the penalty PALM method satisfies the first-order necessary optimality conditions of the problems.Under a suitable assumption such an accumulation point is also a local minimizer of the problems.The numerical results with practical data sets demonstrate that for the fewer sample data the sparse SVR models have better generalization ability and stability especially for the large-scale problems.