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$$ G and a global solution of a quadratic optimization problem determined by $$G$$ G which is called the Lagrangian function of $$G$$ 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$$ r -uniform hypergraphs by establishing a one-to-one correspondence between local (global) minimizers of a family of homogeneous polynomial functions of degree $$r$$ r (different from Lagrangian function) and the maximal (maximum) cliques of an $$r$$ 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\}$$ { 1 , r } -hypergraphs. An application of a main result gives an upper bound on the Turán density of complete $$\{1, r\}$$ { 1 , r } -hypergraphs. The approach applied in the proof follows from the approach in Rota Bulò and Pelillo (2009).