Semidefinite relaxation bounds for bi‐quadratic optimization problems with quadratic constraints

Semidefinite relaxation bounds for bi‐quadratic optimization problems with quadratic constraints

0.00 Avg rating0 Votes
Article ID: iaor20111380
Volume: 49
Issue: 2
Start Page Number: 293
End Page Number: 311
Publication Date: Feb 2011
Journal: Journal of Global Optimization
Authors: , ,
Keywords: programming (semidefinite)
Abstract:

This paper studies the relationship between the so‐called bi‐quadratic optimization problem and its semidefinite programming (SDP) relaxation. It is shown that each r‐bound approximation solution of the relaxed bi‐linear SDP can be used to generate in randomized polynomial time an 𝒪(r) ‐approximation solution of the original bi‐quadratic optimization problem, where the constant in 𝒪(r) does not involve the dimension of variables and the data of problems. For special cases of maximization model, we provide an approximation algorithm for the considered problems.

Reviews

Required fields are marked *. Your email address will not be published.