A semidefinite programming method for integer convex quadratic minimization

DOI10.1007/S11590-017-1132-YzbMath1401.90131arXiv1504.07672OpenAlexW3102922146MaRDI QIDQ1749779

Stephen P. Boyd, Jae Hyun Park

Publication date: 28 May 2018

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.07672

zbMATH Keywords

convex optimizationbranch-and-boundmixed integer programmingsemidefinite relaxationinteger quadratic programming

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Quadratic programming (90C20)

Related Items (4)

Learning Optimized Risk Scores ⋮ Approximation Bounds for Sparse Programs ⋮ SDP-based branch-and-bound for non-convex quadratic integer optimization ⋮ On the Burer-Monteiro method for general semidefinite programs

Uses Software

• CVX
• Mosek
• MILES
• MLAMBDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Semidefinite relaxations for non-convex quadratic mixed-integer programming
• Supersparse linear integer models for optimized medical scoring systems
• An effective branch-and-bound algorithm for convex quadratic integer programming
• Factoring polynomials with rational coefficients
• Geometric algorithms and combinatorial optimization
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Approximating CVP to within almost-polynomial factors is NP-hard
• MLAMBDA: a modified LAMBDA method for integer least-squares estimation
• Relaxing Nonconvex Quadratic Functions by Multiple Adaptive Diagonal Perturbations
• Ellipsoid Bounds for Convex Quadratic Integer Programming
• Graph Implementations for Nonsmooth Convex Programs
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Eigenvalue Techniques for Convex Objective, Nonconvex Optimization Problems
• Linear Matrix Inequalities in System and Control Theory
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Closest point search in lattices
• Semidefinite Programming
• On the complexity of sphere decoding in digital communications

This page was built for publication: A semidefinite programming method for integer convex quadratic minimization