Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems

DOI10.1007/S10898-018-0676-4MaRDI QIDQ1756793zbMATH OpenOpenAlexFDO

Authors N. Ito, Sunyoung Kim, Akiko Takeda, Kim-Chuan Toh, Masakazu Kojima

Publication date 27 December 2018

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

Full work available at URL https://doi.org/10.1007/s10898-018-0676-4

zbMATH Keywords

semidefinite relaxationsnondegeneracycompletely positive relaxationsbinary and complementarity conditioncombinatorial quadratic optimization problemsdoubly nonnegative relaxationsequivalence of feasible regions

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)

Recommendations

• Copositive and semidefinite relaxations of the quadratic assignment problem
• Binary quadratic optimization problems that are difficult to solve by conic relaxations
• Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs
• Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
• Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions

Cites work

• scientific article; zbMATH DE number 4070633 (Why is no real title available?)
• scientific article; zbMATH DE number 3176168 (Why is no real title available?)
• A Copositive Programming Approach to Graph Partitioning
• A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
• A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming
• A fresh CP look at mixed-binary QPs: new formulations and relaxations
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• A robust Lagrangian-DNN method for a class of quadratic optimization problems
• Approximation of the stability number of a graph via copositive programming
• Binary quadratic optimization problems that are difficult to solve by conic relaxations
• Bounds for the quadratic assignment problem using the bundle method
• Complementarity and nondegeneracy in semidefinite programming
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Lagrangian-conic relaxations. I: A unified framework and its applications to quadratic optimization problems
• Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs
• Local structure of feasible sets in nonlinear programming, part II: Nondegeneracy
• On Lagrangian relaxation of quadratic matrix constraints
• On copositive programming and standard quadratic optimization problems
• On the copositive representation of binary and continuous nonconvex quadratic programs
• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• Semidefinite programming relaxations for the quadratic assignment problem
• Simplified copositive and Lagrangian relaxations for linearly constrained quadratic optimization problems in continuous and binary variables
• Solving semidefinite-quadratic-linear programs using SDPT3
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Some NP-complete problems in quadratic and nonlinear programming

Cited in

(4)

• Binary quadratic optimization problems that are difficult to solve by conic relaxations
• Comparing QUBO models for quantum annealing: integer encodings for permutation problems
• Algorithm 996
• A Newton-bracketing method for a simple conic optimization problem

Describes a project that uses

Uses Software

• SDPNAL+
• SDPT3
• QAPLIB

This page was built for publication: Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756793)