Algorithms for the solution of quadratic knapsack problems (Q806968): Difference between revisions

Let Q be an \(n\times n\) real matrix and let e denote the n-vector of ones. The authors present and analyze three algorithms for minimizing the quadratic form (x,Qx) subject to \((e,x)=1\), \(x\geq 0.\) The first algorithm is an extension of the potential reduction algorithm for linear complementarity problems developed recently by \textit{M. Kojima}, \textit{S. Mizuno}, and \textit{A. Yoshise} [An O(\(\sqrt{n}L)\) iteration potential reduction algorithm for linear complementary problems. Math. Program., Ser. A, No.3, 331-342 (1991)] to the problems with arbitrary positive semidefinite matrices Q. The second algorithm deals with the problem of computing a stationary point for the indefinite case and the knapsack constraint of the form \((e,x)=n\), \(x\geq 0\). The algorithm is a variation of the affine scaling method and interior trust region method. The third algorithm is based on simplicial partitioning and convex underestimating functions. It is guaranteed to converge to the global minimum of indefinite problems. For the first two algorithms, computational results on a variety of test problems are presented.