Recently, a novel hierarchy of standard polynomial programming formulations for the maximum clique problem has been proposed, inspired by the classical Motzkin–Straus formulation. The k-th formulation ( \({{\textbf {P}}}^k\) ) in this hierarchy expresses the problem of finding a maximum clique in a given graph G as maximization of degree-k multi-linear polynomial over the standard simplex, and every local maximizer of ( \({{\textbf {P}}}^{k+1}\) ) is also a local maximizer of ( \({{\textbf {P}}}^k\) ) for \(k\in \{2,\ldots , \omega -1\}\) , where \(\omega \) is the clique number of G. In particular, every local maximizer of ( \({{\textbf {P}}}^\omega \) ) is global. Similarly to Motzkin–Straus formulation, ( \({{\textbf {P}}}^k\) ) allows “spurious” local maxima, whose support does not correspond to a clique and needs to be further processed to obtain a clique. This drawback motivated several regularizations of Motzkin–Straus formulation proposed in the literature. This paper generalizes one such regularization to ( \({{\textbf {P}}}^k\) ), to ensure that each local maximizer of the regularized formulation corresponds to a maximal clique with at least \(k-1\) vertices in G, and vice versa. The performance of a local optimization solver on the original and proposed regularized formulations for \(k\in \{2, 3, 4, 5\}\) is compared through extensive numerical experiments. The results indicate that both approaches are competitive and that the multi-linear structure of ( \({{\textbf {P}}}^k\) ) can be advantageous to the correspondence between local maxima and maximal cliques ensured by regularized formulations.
