On standard quadratic programs with exact and inexact doubly nonnegative relaxations
From MaRDI portal
Publication:2133420
DOI10.1007/s10107-020-01611-0zbMath1491.90111arXiv2002.12659OpenAlexW3124804635MaRDI QIDQ2133420
E. Alper Yıldırım, Y. Görkem Gökmen
Publication date: 29 April 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2002.12659
Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)
Related Items
Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph, An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs, A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- SPN completable graphs
- SPN graphs: when copositive = SPN
- The extreme rays of the \(5 \times 5\) copositive cone
- On the computational complexity of membership problems for the completely positive cone and its dual
- Analysis of copositive optimization based linear programming bounds on standard quadratic optimization
- The strong perfect graph theorem
- The ellipsoid method and its consequences in combinatorial optimization
- On standard quadratic optimization problems
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- The extreme rays of the \(6\times 6\) copositive cone
- Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures
- Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
- New approximations for the cone of copositive matrices and its dual
- Recognizing Berge graphs
- Extreme copositive quadratic forms
- Irreducible elements of the copositive cone
- Approximation of the Stability Number of a Graph via Copositive Programming
- On the accuracy of uniform polyhedral approximations of the copositive cone
- Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects
- Some NP-complete problems in quadratic and nonlinear programming
- A comparison of the Delsarte and Lovász bounds
- On the Shannon capacity of a graph
- Continuous Characterizations of the Maximum Clique Problem
- An Adaptive Linear Approximation Algorithm for Copositive Programs
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- Optimality conditions for quadratic programming
- On cliques in graphs
- On copositive programming and standard quadratic optimization problems
