Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs

In 1965, Motzkin and Straus provided a connection between the order of a maximum clique in a graph \(G\) and a global solution of a quadratic optimization problem determined by \(G\) which is called the Lagrangian function of \(G\). This connection and its extensions have been useful in both combinatorics and optimization. In 2009, Rota Bulò and Pelillo extended the Motzkin–Straus result to \(r\)-uniform hypergraphs by establishing a one-to-one correspondence between local (global) minimizers of a family of homogeneous polynomial functions of degree \(r\) (different from Lagrangian function) and the maximal (maximum) cliques of an \(r\)-uniform hypergraph. In this paper, we study similar optimization problems related to non-uniform hypergraphs and obtain some extensions of their results to non-uniform hypergraphs. In particular, we provide a one-to-one correspondence between local (global) minimizers of a family of non-homogeneous polynomial functions and the maximal (maximum) cliques of \(\{1, r\}\)-hypergraphs. An application of a main result gives an upper bound on the Turán density of complete \(\{1, r\}\)-hypergraphs. The approach applied in the proof follows from the approach in Rota Bulò and Pelillo (2009).