A Newton’s method for the continuous quadratic knapsack problem
- We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in dif- ferent contexts. The method converges after O(n) iterations with overall arithmetic complexity O(n2). Numerical experiments show that in practice the method con- verges in a small number of iterations with overall linear complexity, and is faster than the state-of-the-art algorithms based on median finding, variable fixing, and secant techniques.
| Author: | Roberto Cominetti, Walter F. Mascarenhas, Paulo J. S. Silva |
|---|---|
| DOI: | https://doi.org/10.1007/s12532-014-0066-y |
| ISSN: | 1867-2949 |
| Parent Title (English): | Mathematical Programming Computation |
| Publisher: | Springer Science and Business Media LLC |
| Document Type: | Article |
| Language: | English |
| Year of Completion: | 2014 |
| Tag: | Software; Theoretical Computer Science |
| Volume: | 6 |
| Issue: | 2 |
| Page Number: | 19 |
| First Page: | 151 |
| Last Page: | 169 |
| Mathematical Programming Computation : | MPC 2014 - Issue 2 |

