On cones of nonnegative quartic forms

convexity nonlinear optimization NP-hard problems positive quartic forms positive semidefinite positivity of polynomials primal-dual pair sum of powers of linear forms sum of squares of quadratic forms super-symmetric tensors

Mathematics Subject Classification ID

Quadratic and bilinear forms, inner products (15A63) Multilinear algebra, tensor calculus (15A69) Duality theory (optimization) (49N15) Convex programming (90C25)

Review text

Historically most work on nonlinear optimization has concentrated on optimization of quadratic functions. For these problems checking convexity of a quadratic function is a basic operation which is easily carried out. However, if we consider the next most complex case, optimization of quartic functions, computations turn out to much more difficult. For example, \textit{A. A. Ahmadi} et al. [Math. Program. 137, No. 1--2 (A), 453--476 (2013; Zbl 1274.90516)] showed that the problem of deciding whether a quartic is convex is strongly NP-hard. The current paper is a well-written survey of positivity questions which arise in optimization with quartic forms, including some new results, and will be useful to anyone wanting to know the present state of knowledge in this field. A real fourth-order tensor \(\mathcal{F=[F}_{ijk\ell}]\) with indices \(i,j,k,\ell\in\left\{ 1,\dots,n\right\} \) is called super-symmetric when each component \(\mathcal{F}_{ijk\ell}\) equals \(\mathcal{F}_{i^{\prime}j^{\prime }k^{\prime}\ell^{\prime}}\) for all permutations \(i^{\prime}j^{\prime} k^{\prime}\ell^{\prime}\) of \(ijk\ell\). The set of such tensors is denoted by \(S^{n^{4}}\). A (real) quartic form in \(n\) variables is a function \(\mathcal{F(}x,x,x,x):=\sum_{1\leq i,j,k,\ell\leq n}\mathcal{F}_{ijk\ell} x_{i}x_{j}x_{k}x_{\ell}\) where \(\mathcal{F}\in S^{n^{4}}\) and \(x=(x_{1} ,\dots,x_{n})^{T}\in\mathbb{R}^{n}\). The following subclasses of \(S^{n^{4}}\) are considered: (1) \(\mathcal{F}\) is positive semidefinite (PSD), namely, \(\mathcal{F(}x,x,x,x)\geq0\) for all \(x\in\mathbb{R}^{n}\); (2) \(\mathcal{F(} x,x,x,x)\) is a sum of squares of quadratic forms (SOS); (3) \(\mathcal{F}\) is matrix positive semidefinite, namely \(\mathcal{F(}X,X):=\sum_{i,j,k,\ell }\mathcal{F}_{ijk\ell}X_{ij}X_{k\ell}\geq0\) for all real \(n\times n\) matrices \(X=[X_{ij}]\); and (4) \(\mathcal{F(}x,x,x,x)\) is a sum of powers of linear forms (SOP), namely, \(\mathcal{F(}x,x,x,x)=\sum_{i=1}^{m}(x^{T}a^{i})^{4}\) for some choice of vectors \(a^{1},\dots,a^{m}\in\mathbb{R}^{n}\). The four classes of tensors defined in this way are denoted by \(S_{+}^{n^{4}},\Sigma_{n,4} ^{2},S_{+}^{n^{2}\times n^{2}}\) and \(\Sigma_{n,4}^{4}\), respectively. It is proved that for \(n\geq4\) each of these classes is a closed convex cone in \(S^{n^{4}}\) and each class strictly contains the class which follows it. Moreover, the first and fourth class are a primal-dual pair, and the same is true for the second and third class. It is also shown that \(\mathcal{F(}x,x,x,x)\) is convex \(\iff\) \(\mathcal{F(}x,x,y,y)\geq0\) for all \(x,y\in\mathbb{R}^{n}\) \(\iff\) \(\mathcal{F(}X,Y)\geq0\) for all positive semidefinite matrices \(X,Y\). Two other classes are also introduced, but their definitions are more complicated and we omit them. Section 5 studies the complexity of deciding when a given \(\mathcal{F\in S}^{n^{2}}\) lies in one of the four classes; the problem is NP-hard for all classes except \(S_{+}^{n^{2}\times n^{2}}\). Section 6 discusses the problem of optimizing a linear function over the intersection of an affine subspace with one of these cones of quartic forms, and the paper concludes by remarking that quartic conic problems have many potential applications as well as interesting theoretical properties. The authors suggest that the hierachical relation between the classes described above may be useful for designing relaxation methods of approximating such problems.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: On cones of nonnegative quartic forms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q525602)