Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization

DOI10.1137/070679041MaRDI QIDQ3629504zbMATH OpenOpenAlexFDO

Authors Simai He, Zhi-Quan Luo, Jiawang Nie, Shuzhong Zhang

Publication date 27 May 2009

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

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

zbMATH Keywords

approximation ratioprobabilistic solutionquadratic optimizationSDP relaxation

Mathematics Subject Classification ID

Randomized algorithms (68W20) Quadratic programming (90C20) Semidefinite programming (90C22)

Abstract: In this paper we study the relationship between the optimal value of a homogeneous quadratic optimization problem and that of its Semidefinite Programming (SDP) relaxation. We consider two quadratic optimization models: (1) $min{x}^{\ast }Cxmid{x}^{\ast }{A}_{k}xge1,xinmathbb{F}^n,k=0,1,\mathrm{...},m$; and (2) $max{x}^{\ast }Cxmid{x}^{\ast }{A}_{k}xle1,xinmathbb{F}^n,k=0,1,\mathrm{...},m$. If emph{one} of $A_k$'s is indefinite while others and $C$ are positive semidefinite, we prove that the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by $O(m^2)$ when $mathbbF$ is the real line $mathbbR$, and by $O(m)$ when $mathbbF$ is the complex plane $mathbbC$. This result is an extension of the recent work of Luo {em et al.} cite{LSTZ}. For (2), we show that the same ratio is bounded from below by $O(1/logm)$ for both the real and complex case, whenever all but one of $A_k$'s are positive semidefinite while $C$ can be indefinite. This result improves the so-called approximate S-Lemma of Ben-Tal {em et al.} cite{BNR02}. We also consider (2) with multiple indefinite quadratic constraints and derive a general bound in terms of the problem data and the SDP solution. Throughout the paper, we present examples showing that all of our results are essentially tight.

Recommendations

• Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints
• Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints
• Semidefinite relaxation and nonconvex quadratic optimization
• Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation
• On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations

Cited in

(32)

• Improved semidefinite approximation bounds for nonconvex nonhomogeneous quadratic optimization with ellipsoid constraints
• An exact Jacobian SDP relaxation for polynomial optimization
• Small deviations of sums of independent random variables
• Penalized semidefinite programming for quadratically-constrained quadratic optimization
• A note on random signs
• Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem
• Tight relaxations for polynomial optimization and Lagrange multiplier expressions
• A subgradient-based convex approximations method for DC programming and its applications
• An improved probability bound for the approximate S-lemma
• Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds
• A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming
• Convex hulls of quadratically parameterized sets with quadratic constraints
• Exactness conditions for an SDP relaxation of the extended trust region problem
• A note on semidefinite programming relaxations for polynomial optimization over a single sphere
• A new series of conjectures and open questions in optimization and matrix analysis
• A counter-example to a conjecture of Ben-Tal, Nemirovski and Roos
• Approximation bounds for trilinear and biquadratic optimization problems over nonconvex constraints
• Semidefinite relaxation approximation for multivariate bi-quadratic optimization with quadratic constraints.
• Rademacher-Gaussian tail comparison for complex coefficients and related problems
• scientific article; zbMATH DE number 7626745 (Why is no real title available?)
• An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints
• Probability bounds for polynomial functions in random variables
• Inhomogeneous polynomial optimization over a convex set: an approximation approach
• Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained quadratic optimization problems
• An approach for minimizing a quadratically constrained fractional quadratic problem with application to the communications over wireless channels
• scientific article; zbMATH DE number 7662450 (Why is no real title available?)
• Approximation algorithms for homogeneous polynomial optimization with quadratic constraints
• A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints
• Projectively and Weakly Simultaneously Diagonalizable Matrices and their Applications
• Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints
• Reducing the large set threshold for Oertel's conjecture on the mixed-integer volume
• Approximation algorithms for nonnegative polynomial optimization problems over unit spheres

Describes a project that uses

Uses Software

• QPBOX

This page was built for publication: Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization

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