A semidefinite programming method for integer convex quadratic minimization
From MaRDI portal
Publication:1749779
DOI10.1007/S11590-017-1132-YzbMATH Open1401.90131arXiv1504.07672OpenAlexW3102922146MaRDI QIDQ1749779FDOQ1749779
Authors: Stephen Boyd, Jaehyun Park 
Publication date: 28 May 2018
Published in: Optimization Letters (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1504.07672
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
convex optimizationmixed integer programmingbranch-and-boundsemidefinite relaxationinteger quadratic programming
Cites Work
- MLAMBDA: a modified LAMBDA method for integer least-squares estimation
- Title not available (Why is that?)
- Linear Matrix Inequalities in System and Control Theory
- Semidefinite Programming
- Supersparse linear integer models for optimized medical scoring systems
- Title not available (Why is that?)
- Geometric algorithms and combinatorial optimization
- Graph implementations for nonsmooth convex programs
- Factoring polynomials with rational coefficients
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Semidefinite relaxations for non-convex quadratic mixed-integer programming
- 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
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Approximating CVP to within almost-polynomial factors is NP-hard
- An effective branch-and-bound algorithm for convex quadratic integer programming
- Closest point search in lattices
- Title not available (Why is that?)
- Eigenvalue techniques for convex objective, nonconvex optimization problems
- Ellipsoid bounds for convex quadratic integer programming
- Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations
- On the complexity of sphere decoding in digital communications
Cited In (10)
- A roof linearization algorithm to obtain a tight upper bound for integer nonseparable quadratic programming
- A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs
- Integrability and complexity in quantum spin chains
- Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach
- On the gap between the quadratic integer programming problem and its semidefinite relaxation
- Approximation Bounds for Sparse Programs
- On the Burer-Monteiro method for general semidefinite programs
- Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs
- Learning optimized risk scores
- SDP-based branch-and-bound for non-convex quadratic integer optimization
Uses Software
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)
