Given a graph G whose adjacency matrix is A, the Motzkin–Strauss formulation of the Maximum-Clique Problem is the quadratic program (QP) max (T)(x)(A)(x) | (x) (T) (e) = 1, x ≥ 0. It is well known that the global optimum value of this QP is (1 − 1/ω(G)), where ω(G) is the clique number of G. Here, we characterize the following properties pertaining to the above QP: (1) first order optimality, (2) second order optimality, (3) local optimality, (4) strict local optimality. These characterizations reveal interesting underlying discrete structures, and are polynomial time verifiable. A parametrization of the Motzkin–Strauss QP is then introduced and its properties are investigated. Finally, an extension of the Motzkin–Strauss formulation is provided for the weighted clique number of a graph.
