A Geometrical Analysis on Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems

DOI10.1137/19M1237715zbMath1491.90112arXiv1901.02179OpenAlexW3021709123MaRDI QIDQ5110556

Kojima, Masakazu, Sunyoung Kim, Kim-Chuan Toh

Publication date: 20 May 2020

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

quadratic programspolynomial optimization problemscompletely positive programming reformulationconic optimization problemsfaces of the completely positive cone

Mathematics Subject Classification ID

Convex programming (90C25) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Polynomial optimization (90C23)

Related Items

Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures, Optimization under uncertainty and risk: quadratic and copositive approaches, Approximation hierarchies for copositive cone over symmetric cone and their comparison, Sparse conic reformulation of structured QCQPs based on copositive optimization with applications in stochastic optimization, An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs

Uses Software

• QAPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
• Extension of completely positive cone relaxation to moment cone relaxation for polynomial optimization
• Erratum to: ``On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets
• A robust Lagrangian-DNN method for a class of quadratic optimization problems
• Copositive and semidefinite relaxations of the quadratic assignment problem
• A fresh CP look at mixed-binary QPs: new formulations and relaxations
• Sparsity in sums of squares of polynomials
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints
• Completely positive reformulations for polynomial optimization
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
• Approximation of the Stability Number of a Graph via Copositive Programming
• Improved Conic Reformulations for $K$-means Clustering
• Algorithm 996
• A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming
• A Copositive Programming Approach to Graph Partitioning
• LMI Approximations for Cones of Positive Semidefinite Forms
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Convex Analysis
• On copositive programming and standard quadratic optimization problems