Semidefinite relaxation approximation for multivariate bi-quadratic optimization with quadratic constraints

Chen Ling, Xinzhen Zhang, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

In this paper, we consider the NP-hard problem of finding global minimum of quadratically constrained multivariate bi-quadratic optimization. We present some bounds of the considered problem via approximately solving the related bi-linear semidefinite programming (SDP) relaxation. Based on the bi-linear SDP relaxation, we also establish some approximation solution methods, which generalize the methods for the quadratic polynomial optimization in (SIAM J. Optim. 2003; 14:268-283). Finally, we present a special form, whose bi-linear SDP relaxation can be approximately solved in polynomial time.
Original languageEnglish
Pages (from-to)113-131
Number of pages19
JournalNumerical Linear Algebra with Applications
Volume19
Issue number1
DOIs
Publication statusPublished - 1 Jan 2012

Keywords

  • Approximation solution
  • Bi-quadratic optimization
  • NP-hard
  • Semidefinite programming relaxation

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics

Cite this