A semidefinite programming method for integer convex quadratic minimization
From MaRDI portal
Publication:1749779
Abstract: We consider the NP-hard problem of minimizing a convex quadratic function over the integer lattice . We present a simple semidefinite programming (SDP) relaxation for obtaining a nontrivial lower bound on the optimal value of the problem. By interpreting the solution to the SDP relaxation probabilistically, we obtain a randomized algorithm for finding good suboptimal solutions, and thus an upper bound on the optimal value. The effectiveness of the method is shown for numerical problem instances of various sizes.
Recommendations
- Semidefinite programming relaxation for nonconvex quadratic programs
- Semidefinite relaxations for non-convex quadratic mixed-integer programming
- Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation
- Semidefinite approximation for mixed binary quadratically constrained quadratic programs
- Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds
Cites work
- An effective branch-and-bound algorithm for convex quadratic integer programming
- Approximating CVP to within almost-polynomial factors is NP-hard
- Closest point search in lattices
- Eigenvalue techniques for convex objective, nonconvex optimization problems
- Ellipsoid bounds for convex quadratic integer programming
- Factoring polynomials with rational coefficients
- Geometric algorithms and combinatorial optimization
- Graph implementations for nonsmooth convex programs
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 1852142 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Linear Matrix Inequalities in System and Control Theory
- MLAMBDA: a modified LAMBDA method for integer least-squares estimation
- On the complexity of sphere decoding in digital communications
- Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations
- Semidefinite Programming
- Semidefinite relaxations for non-convex quadratic mixed-integer programming
- Supersparse linear integer models for optimized medical scoring systems
- The hardness of approximate optima in lattices, codes, and systems of linear equations
Cited in
(12)- On the Burer-Monteiro method for general semidefinite programs
- SDP-based branch-and-bound for non-convex quadratic integer optimization
- On the gap between the quadratic integer programming problem and its semidefinite relaxation
- Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs
- A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs
- A roof linearization algorithm to obtain a tight upper bound for integer nonseparable quadratic programming
- Approximation Bounds for Sparse Programs
- Learning optimized risk scores
- Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach
- Integrability and complexity in quantum spin chains
- Fix and bound: an efficient approach for solving large-scale quadratic programming problems with box constraints
- Efficient local and tabu search strategies for large-scale general quadratic integer programming
This page was built for publication: A semidefinite programming method for integer convex quadratic minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1749779)
