Semidefinite approximation for mixed binary quadratically constrained quadratic programs

DOI10.1137/130909597MaRDI QIDQ2934478zbMATH OpenOpenAlexFDO

Authors Zi Xu, Mingyi Hong, Zhi-Quan Luo

Publication date 12 December 2014

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

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

zbMATH Keywords

NP-hardsemidefinite programming relaxationapproximation boundnonconvex quadratic constrained quadratic programming

Mathematics Subject Classification ID

Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59) Semidefinite programming (90C22)

Abstract: Motivated by applications in wireless communications, this paper develops semidefinite programming (SDP) relaxation techniques for some mixed binary quadratically constrained quadratic programs (MBQCQP) and analyzes their approximation performance. We consider both a minimization and a maximization model of this problem. For the minimization model, the objective is to find a minimum norm vector in $N$-dimensional real or complex Euclidean space, such that $M$ concave quadratic constraints and a cardinality constraint are satisfied with both binary and continuous variables. {color{blue}By employing a special randomized rounding procedure, we show that the ratio between the norm of the optimal solution of the minimization model and its SDP relaxation is upper bounded by $cO(Q^2(M-Q+1)+M^2)$ in the real case and by $cO(M(M-Q+1))$ in the complex case.} For the maximization model, the goal is to find a maximum norm vector subject to a set of quadratic constraints and a cardinality constraint with both binary and continuous variables. We show that in this case the approximation ratio is bounded from below by $cO(epsilon/ln(M))$ for both the real and the complex cases. Moreover, this ratio is tight up to a constant factor.

Recommendations

• Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds
• Approximation algorithm for a mixed binary quadratically constrained quadratic programming problem
• Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints
• SDP relaxation of homogeneous quadratic optimization: approximation bounds and applications
• scientific article; zbMATH DE number 6612550

Cited in

(14)

• SDP relaxation of homogeneous quadratic optimization: approximation bounds and applications
• A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs
• Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods
• Approximation algorithm for a mixed binary quadratically constrained quadratic programming problem
• Mixed linear and semidefinite programming for combinatorial and quadratic optimization
• A semidefinite programming method for integer convex quadratic minimization
• A quadratic semidefinite relaxation approach for resource allocation in orthogonal frequency division multiple access
• scientific article; zbMATH DE number 6612550 (Why is no real title available?)
• Robust semidefinite relaxations for a quadratic OFDMA resource allocation scheme
• Semidefinite relaxations for mixed 0-1 second-order cone program
• Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem
• Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds
• A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
• Probabilistic Analysis of Semidefinite Relaxation for Binary Quadratic Minimization

This page was built for publication: Semidefinite approximation for mixed binary quadratically constrained quadratic programs

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