A logarithmic descent direction algorithm for the quadratic knapsack problem

摘要

The quadratic knapsack problem is an NP-hard optimization problem with many diverse applications in industrial and management engineering. However, computational complexities still remain in the quadratic knapsack problem. In this study, a logarithmic descent direction algorithm is proposed to approximate a solution to the quadratic knapsack problem. The proposed algorithm is based on the Karush–Kuhn–Tucker necessary optimality condition and the damped Newton method. The convergence of the algorithm is proven, and the numerical results indicate its effectiveness.