A logarithmic descent direction algorithm for the quadratic knapsack problem
| Autor: | Hamid Reza Karimi, Baoping Jiang, Zhengtian Wu |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
NP-hard optimization problem Optimization problem Logarithm Applied Mathematics Quadratic knapsack problem MathematicsofComputing_NUMERICALANALYSIS 020206 networking & telecommunications 02 engineering and technology Karush–Kuhn–Tucker condition Computational Mathematics symbols.namesake 020901 industrial engineering & automation Damped newton method Convergence (routing) 0202 electrical engineering electronic engineering information engineering symbols Management engineering Descent direction Algorithm Newton's method Mathematics |
| Zdroj: | Applied Mathematics and Computation. 369:124854 |
| ISSN: | 0096-3003 |
| DOI: | 10.1016/j.amc.2019.124854 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect