Algorithms for the solution of quadratic knapsack problems
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.
- A Centered Projective Algorithm for Linear Programming
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
- An O(n^ 3L) primal interior point algorithm for convex quadratic programming
- An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds
- An algorithm for nonconvex programming problems
- An extension of Karmarkar's projective algorithm for convex quadratic programming
- An O(n) algorithm for quadratic knapsack problems
- Checking local optimality in constrained quadratic programming is NP- hard
- Computing a Trust Region Step
- Constrained global optimization: algorithms and applications
- Convex quadratic programming with one constraint and bounded variables
- Duality in quadratic programming
- scientific article; zbMATH DE number 4213315 (Why is no real title available?)
- scientific article; zbMATH DE number 3677572 (Why is no real title available?)
- scientific article; zbMATH DE number 3561096 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 4193461 (Why is no real title available?)
- Interior path following primal-dual algorithms. I: Linear programming
- Local minima for indefinite quadratic knapsack problems
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Methods for Global Concave Minimization: A Bibliographic Survey
- Newton’s Method with a Model Trust Region Modification
- Optimal scaling of balls and polyhedra
- Quadratic problems defined on a convex hull of points
- Quasi-Newton Updates with Bounds
- Inverse optimization for linearly constrained convex separable programming problems
- Local minima for indefinite quadratic knapsack problems
- Quadratic resource allocation with generalized upper bounds
- The nonlinear knapsack problem - algorithms and applications
- Computation of sparse and dense equilibrium strategies of evolutionary games
- New infeasible interior-point algorithm based on monomial method
- Variable fixing method by weighted average for the continuous quadratic knapsack problem
- Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem
- A wide neighborhood arc-search interior-point algorithm for convex quadratic programming with box constraints and linear constraints
- A logarithmic descent direction algorithm for the quadratic knapsack problem
- Optimality and stability of symmetric evolutionary games with applications in genetic selection
- Quadratic bottleneck knapsack problems
- Minimum variance allocation among constrained intervals
- A survey on the continuous nonlinear resource allocation problem
- On a nonseparable convex maximization problem with continuous Knapsack constraints
- A branch and bound algorithm for constrained least squares
- On the solution of multidimensional convex separable continuous knapsack problem with bounded variables
- Equilibrium distributions of populations of biological species on networks of social sites
- Minimization of a strictly convex separable function subject to convex separable inequality constraint and box constraints
- scientific article; zbMATH DE number 617926 (Why is no real title available?)
- Comparative analysis of the cutting angle and simulated annealing methods in global optimization
- scientific article; zbMATH DE number 2124285 (Why is no real title available?)
- A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems
- A two-phase method for solving continuous rank-one quadratic knapsack problems
- Reformulation of the quadratic multidimensional knapsack problem as copositive/completely positive programs
- Minimum norm solution to the positive semidefinite linear complementarity problem
- A pegging algorithm for the nonlinear resource allocation problem
- Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem
- A note on optimal solutions to quadratic knapsack problems
- A class of nonlinear nonseparable continuous Knapsack and multiple-choice knapsack problems
- Global optimality conditions and optimization methods for quadratic knapsack problems
- Nonconvex homogeneous optimization: a general framework and optimality conditions of first and second-order
- Approximation algorithms for indefinite quadratic programming
- The complexity of computing KKT solutions of quadratic programs
- A combinatorial algorithm for inverse continuous quadratic knapsack problem
- An O(n) algorithm for quadratic knapsack problems
- The quadratic knapsack problem -- a survey
- Competitive facility location model with concave demand
- Variable fixing algorithms for the continuous quadratic Knapsack problem
This page was built for publication: Algorithms for the solution of quadratic knapsack problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q806968)
