A Newton's method for the continuous quadratic knapsack problem

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

doi:10.1007/s12532-014-0066-y

A Newton's method for the continuous quadratic knapsack problem

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

Faculty of Engineering and Science

Research output: Contribution to journal › Article › peer-review

31 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 language	English
Pages (from-to)	151-169
Number of pages	19
Journal	Mathematical Programming Computation
Volume	6
Issue number	2
DOIs	https://doi.org/10.1007/s12532-014-0066-y
State	Published - Jun 2014

Keywords

Continuous quadratic knapsack
Duality
Semismooth Newton
Simplex projections

Access to Document

10.1007/s12532-014-0066-y

Cite this

@article{38ff458fcee7430ba338a53b656804c0,

title = "A Newton's method for the continuous quadratic knapsack problem",

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.",

keywords = "Continuous quadratic knapsack, Duality, Semismooth Newton, Simplex projections",

author = "Roberto Cominetti and Mascarenhas, \{Walter F.\} and Silva, \{Paulo J.S.\}",

note = "Funding Information: This work was supported by Fondecyt 1100046 and Nucleo Milenio Informaci{\'o}n y Coordinaci{\'o}n en Redes ICM/FIC P10-024F, PRONEX-Optimization (PRONEX-CNPq/FAPERJ E-26/171.510/2006-APQ1), CNPq (Grant 305740/2010-5), and FAPESP (Grant 2012/20339-0).",

year = "2014",

month = jun,

doi = "10.1007/s12532-014-0066-y",

language = "English",

volume = "6",

pages = "151--169",

journal = "Mathematical Programming Computation",

issn = "1867-2949",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

T1 - A Newton's method for the continuous quadratic knapsack problem

AU - Cominetti, Roberto

AU - Mascarenhas, Walter F.

AU - Silva, Paulo J.S.

N1 - Funding Information: This work was supported by Fondecyt 1100046 and Nucleo Milenio Información y Coordinación en Redes ICM/FIC P10-024F, PRONEX-Optimization (PRONEX-CNPq/FAPERJ E-26/171.510/2006-APQ1), CNPq (Grant 305740/2010-5), and FAPESP (Grant 2012/20339-0).

PY - 2014/6

Y1 - 2014/6

N2 - 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.

AB - 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.

KW - Continuous quadratic knapsack

KW - Duality

KW - Semismooth Newton

KW - Simplex projections

UR - https://www.scopus.com/pages/publications/84904995697

U2 - 10.1007/s12532-014-0066-y

DO - 10.1007/s12532-014-0066-y

M3 - Article

AN - SCOPUS:84904995697

SN - 1867-2949

VL - 6

SP - 151

EP - 169

JO - Mathematical Programming Computation

JF - Mathematical Programming Computation

IS - 2

ER -

A Newton's method for the continuous quadratic knapsack problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this