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

Xinzhen Zhang, Chen Ling, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

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 O(r) -approximation solution of the original bi-quadratic optimization problem, where the constant in O(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.
Original languageEnglish
Pages (from-to)293-311
Number of pages19
JournalJournal of Global Optimization
Volume49
Issue number2
DOIs
Publication statusPublished - 1 Feb 2011

Keywords

  • Approximation solution
  • Bi-quadratic optimization
  • Probabilistic solution
  • Semidefinite programming relaxation

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Cite this