The spherical constraint in Boolean quadratic programs

DOI10.1007/s10898-007-9161-1zbMath1146.90043OpenAlexW2014548643MaRDI QIDQ925238

Jérôme Malick

Publication date: 3 June 2008

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00070518/file/07-malick.pdf

zbMATH Keywords

SDP relaxationCombinatorial optimizationConvex analysisLagrangian duality

Mathematics Subject Classification ID

Quadratic programming (90C20) Optimality conditions and duality in mathematical programming (90C46) Boolean programming (90C09)

Related Items

On the spherical quasi-convexity of quadratic functions, A variational approach of the rank function, On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods, Solving \(k\)-cluster problems to optimality with semidefinite programming, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, A low complexity semidefinite relaxation for large-scale MIMO detection, Improved semidefinite bounding procedure for solving max-cut problems to optimality, Efficient semidefinite branch-and-cut for MAP-MRF inference, Improved row-by-row method for binary quadratic optimization problems, Constrained Best Euclidean Distance Embedding on a Sphere: A Matrix Optimization Approach

Uses Software

• Scilab
• QSDP
• SDPLR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the nearest correlation matrix--a problem from finance
• Semi-Lagrangian relaxation applied to the uncapacitated facility location problem
• Solving the \(p\)-median problem with a semi-Lagrangian relaxation
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Convex analysis and nonlinear optimization. Theory and examples
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Seizure warning algorithm based on optimization and nonlinear dynamics
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Lower bound improvement and forcing rule for quadratic binary programming
• Lectures on Modern Convex Optimization
• A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix
• A nonlinear equation for linear programming
• An Implicit Enumeration Algorithm for Quadratic Integer Programming
• Iterative Solution of Linear Programs
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Bundle Method for Semidefinite Programming
• A Dual Approach to Semidefinite Least-Squares Problems
• Semidefinite Programming vs. LP Relaxations for Polynomial Programming
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Introduction to global optimization.