A Newton's method for the continuous quadratic knapsack problem

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

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

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(n2). 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.

Original languageEnglish
Pages (from-to)151-169
Number of pages19
JournalMathematical Programming Computation
Volume6
Issue number2
DOIs
StatePublished - Jun 2014

Keywords

  • Continuous quadratic knapsack
  • Duality
  • Semismooth Newton
  • Simplex projections

Fingerprint

Dive into the research topics of 'A Newton's method for the continuous quadratic knapsack problem'. Together they form a unique fingerprint.

Cite this