Study On Algorithms For Continuous Quadratic Knapsack Problem With L1 Regularization

In life,optimization problems are very common,and optimization problems in mechanics can also be seen everywhere.The continuous quadratic knapsack problem with₁l regularization?CQKPL1?is an important kind of optimization problem and it has a wide range of applications in life such as data mining,image processing,compression sensing and so on.In particular,the good sparsity of regularization has long been applied in the field of computer.The research of this problem have long been concerned by scholars in the field of engineering mechanice at home and abroad and have become a hot issue during recent years.Under the background of above applications,this thesis focuses on fast algorithms of solving the continuous quadratic knapsack problem withl₁ regularization and compares with the proposed algorithms via data experiment.The main content of the thesis is summarized as follows:Chapter 1 introduces the evolution process and development history of the quadratic knap-sack problem,and introduces some commonly used algorithms to solve the knapsack separable quadratic problem.In Chapter 2,we propose the algorithms of CQKPL1 to study in the above background and transform it into the problem of solving root of equation by analyzing sub-problems and parametric problems of the model.Based on these results,we develop three algorithms to obtain close-form solution of CQKPL1.In Chapter 3,the modified binary search is proposed.The algorithm first classifies the breakpoints.Secondly,it mainly performs the binary search on the breakpoints contained in the function.At the same time,the steps of accelerating iteration are added to speed up the algo-rithm convergence and search for the solution until the optimal solution is found.In Chapter 4,we propose the modified secant method.The algorithm consists of two phases:Bracketing Phase.The purpose of the first phase is to lock the interval of the root of the equation;Secant Phase.It uses the secant procedure to find the root of the equation within the locked interval.In Chapter 5,we develop the modified Newton method for CQKPL1.First,the concept of Moreau-Yosida regularization is introduced to re-search the original problem and much better analytic properties of the obtained function.Then,iterative direction is obtained by using the modified derivative and the iterative step is made by Armijo line search.Finally,the global convergence theorem of modified Newton method is given and the feasibility of the algorithm is proved theoretically.Chapter 6 carries out numerical experiment of the three proposed modified algorithms respectively.The experimental results are compared with Gurobi and Mosek to verify the fea-sibility and efficiency of the proposed algorithms.