×

zbMATH — the first resource for mathematics

Biquadratic optimization over unit spheres and semidefinite programming relaxations. (English) Zbl 1221.90074
This paper studies the so-called biquadratic optimization over unit spheres \[ \min_{x\in\mathbb{R}^n, y\in\mathbb{R}^m} b(x,y)= \sum_{1\leq i, k\leq n, 1\leq j,l\leq m} b_{ijkl} x_i y_j x_k y_l, \]
\[ \text{subject to }\| x\|= 1,\quad\| y\|= 1, \] where \(\|\cdot\|\) denotes the standard 2-norm in Euclidean spaces \(\mathbb{R}^n\) and \(\mathbb{R}^n\), where \(\mathbb{R}^n\) denotes the space of real \(n\)-dimensional column vectors. It is showed that this problem is NP-hard, and there is no polynomial time algorithm returning a positive relative approximation bound. Various approximation methods based on semidefinite programming (SDP) relaxations are also presented. The theoretical results are as follows. For general biquadratic forms, the authors develop a \({1\over 2\max\{m,n\}^2}\)-aproximation algorithm under a slightly weaker approximation notion; for biquadratic forms that are square-free, a relative approximation bound \({1\over nm}\) is given; when \(\min\{n, m\}\) is a constant, two polynomial time approximation schemes (PTASs) which are based on sum of squares (SOS) relaxation hierarchy and grid sampling of the standard simplex are presented. For practical computational purposes, the authors propose the first-order SOS relaxation, a conex quadratic SDP relaxation, and a simple minimum eigenvalue method and show their error bounds. Some illustrative numerical examples are also included.

MSC:
90C26 Nonconvex programming, global optimization
90C22 Semidefinite programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI