A Newton's method for the continuous quadratic knapsack problem

Autor(es)

Cominetti, Roberto ; Mascarenhas, Walter F. ; Silva, Paulo J. S.

• Tipo de documento: Artigo Científico
• Fonte: MATHEMATICAL PROGRAMMING COMPUTATION; v. 6, n. 2, p. 19-pg., 2014-06-01.

Resumo

We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in different contexts. The method converges after O(n) iterations with overall arithmetic complexity O(n(2)). Numerical experiments show that in practice the method converges 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. (AU)

• Processo FAPESP: 12/20339-0 - Métodos de penalidade, condições de otimalidade e aplicações
• Beneficiário: Paulo José da Silva e Silva
• Modalidade de apoio: Auxílio à Pesquisa - Regular