A LINEAR TIME ALGORITHM FOR THE CONTINUOUS QUADRATIC KNAPSACK PROBLEM WITH Ei REGULARIZATION

作者：Liu, Yong-Jin^*; Wen, Yanan

来源：Pacific Journal of Optimization, 2017, 13(2): 301-313.

• continuous quadratic knapsack problem
• l(1) regularization
• linear time complexity
• median search method

Recent interests in sparse optimization arising from kernel density learning, sparse portfolio selection, and index tracking motivate us to consider the continuous quadratic knapsack problem with 21 regularization (CQKPL1) which favors sparsity. In this paper, we aim to develop an efficient algorithm based on median search strategy to solve CQKPL1. A remarkable feature of the algorithm is that the closed-form solution of CQKPL1 would be achieved with order n operations. Numerical results validate the linear time complexity of our algorithm and the sparsity of optimal solution, as well as demonstrate that our algorithm is able to efficiently solve CQKPL1 with the problem sizes up to ten million within about two minutes.

• 出版日期2017-4
• 单位沈阳航空航天大学