Biquadratic optimization over unit spheres and semidefinite programming relaxations

Chen Ling, Jiawang Nie, Liqun Qi, Yinyu Ye

Research output: Journal article publicationJournal articleAcademic researchpeer-review

80 Citations (Scopus)

Abstract

This paper studies the so-called biquadratic optimization over unit spheres minx∈ℝny∈ℝmΣ1≤i k≤n 1≤j, ι≤mbijklxiyjxkyl, subject to ∥x∥ = 1, ∥y∥ = 1. We show that this problem is NP-hard, and there is no polynomial time algorithm returning a positive relative approximation bound. Then, we present various approximation methods based on semidefinite programming (SDP) relaxations. Our theoretical results are as follows: For general biquadratic forms, we develop a -1/2max{m,n}2-approximation algorithm under a slightly weaker approximation notion; for biquadratic forms that are square-free, we give a relative approximation bound 1/nm; when min{n, m} is a con-stant, we present two polynomial time approximation schemes (PTASs) which are based on sum of squares (SOS) relaxation hierarchy and grid sampling of the standard simplex. For practical computational purposes, we propose the first order SOS relaxation, a convex quadratic SDP relaxation, and a simple minimum eigenvalue method and show their error bounds. Some illustrative numerical examples are also included.
Original languageEnglish
Pages (from-to)1286-1310
Number of pages25
JournalSIAM Journal on Optimization
Volume20
Issue number3
DOIs
Publication statusPublished - 1 Dec 2009

Keywords

  • Approximate solution
  • Biquadratic optimization
  • Polynomial time approximation scheme
  • Semidefinite programming
  • Sum of squares

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this