Exact SDP relaxations for quadratic programs with bipartite graph structures

DOI10.1007/s10898-022-01268-3zbMath1522.90063arXiv2204.09509OpenAlexW4313323051MaRDI QIDQ6173960

Sunyoung Kim, Godai Azuma, Mituhiro Fukuda, Makoto Yamashita

Publication date: 13 July 2023

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

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

zbMATH Keywords

bipartite graphquadratically constrained quadratic programsexact semidefinite relaxationsrank of aggregated sparsity matrixsign-indefinite QCQPs

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Exactness conditions for an SDP relaxation of the extended trust region problem
• Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
• Strong duality for generalized trust region subproblem: S-lemma with interval bounds
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Theory of semidefinite programming for sensor network localization
• Semidefinite programming relaxations for the quadratic assignment problem
• Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
• Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods
• Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• Nonchordal positive semidefinite stochastic matrices^∗
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
• Exactness of Semidefinite Relaxations for Nonlinear Optimization Problems with Underlying Graph Structure
• JuMP: A Modeling Language for Mathematical Optimization
• A Survey of the S-Lemma

This page was built for publication: Exact SDP relaxations for quadratic programs with bipartite graph structures