1 Introduction

A common problem in combinatorial optimization is the maximization of a quadratic form over \(\{-1,1\}^n\)

$$\begin{aligned} \max _{x \in \{-1,1\}^n} x^T A x = \max _{\begin{array}{c} X = x x^T \\ x \in \{-1,1\}^n \end{array}} \langle A, X \rangle \end{aligned}$$
(1)

where \(\langle \cdot , \cdot \rangle \) denotes the usual scalar product on real symmetric matrices of size n.

The decision problem associated to this optimization problem is NP-complete. Indeed the Max-Cut problem, one of Karp’s 21 NP-complete problems, can be reduced in polynomial time to the maximization of a quadratic form over \(\{-1,1\}^n\) [3]. The reformulation in the form of (1) of several common hard combinatorial optimization problems such as vertex cover, knapsack, traveling salesman, etc, can be found in [4].

Consider the set

$$\begin{aligned} \mathcal {SR}= \{ X \succeq 0 ~|~ {{\,\mathrm{diag}\,}}X = 1 \} \end{aligned}$$

in the space of real symmetric \(n \times n\) matrices, where \(X \succeq 0\) means that X is a positive semidefinite matrix. It serves as a simple and convex outer approximation of the Max-Cut polytope

$$\begin{aligned} \mathcal {MC}= {{\,\mathrm{conv}\,}}\{ X \in \mathcal {SR}~|~ {{\,\mathrm{rk}\,}}X = 1\}, \end{aligned}$$

where \({{\,\mathrm{conv}\,}}\) denotes the convex envelope and \({{\,\mathrm{rk}\,}}X\) denotes the rank of X.

Note that \(\{ X \in \mathcal {SR}~|~ \text {rk } X = 1 \} = \{ X ~|~ \exists x \in \{-1,1\}^n,~ X = x x^T\}\). Indeed a positive semidefinite matrix X has rank 1 if and only if there exists a nonzero vector x such that \(X = x x^T\). Then the condition \({{\,\mathrm{diag}\,}}X = 1\) implies that \(x_i^2 = 1\) for every \(i \in \{1, ..., n\}\), i.e., \(x_i = \pm 1\), and conversely.

The maximal value of a linear functional \( \langle A, . \rangle \) over a set E does not change if the set E is replaced by its convex envelope \({{\,\mathrm{conv}\,}}E\). Therefore

$$\begin{aligned} \max _{\begin{array}{c} X = x x^T \\ x \in \{-1,1\}^n \end{array}} \langle A, X \rangle = \max _{X \in \mathcal {MC}} \langle A, X \rangle . \end{aligned}$$

However, the Max-Cut polytope is a difficult polytope. Indeed, “due to the NP-completeness of the max-cut problem, it follows from a result of Karp and Papadimitriou [1982] that there exists no polynomially concise linear description of \(\mathcal {MC}\) unless NP = co-NP” [1, Section 4.4]. A good review of results on the Max-Cut polytope can be found in [1].

Maximizing \(\langle A, X \rangle \) over \(\mathcal {SR}\) instead of \(\mathcal {MC}\) for \(A \succeq 0\) approximates the exact solution of the problem with relative accuracy \(\mu = \dfrac{\pi }{2} - 1\) [5]:

$$\begin{aligned} \dfrac{2}{\pi } \max _{X \in \mathcal {SR}} \langle A, X \rangle \leqslant \max _{X \in \mathcal {MC}} \langle A, X \rangle \leqslant \max _{X \in \mathcal {SR}} \langle A, X \rangle . \end{aligned}$$

Define a function \(f: [-1, 1] \rightarrow [-1, 1]\) by \(f(x) = \dfrac{2}{\pi } \arcsin x\). Let \({\mathbf {f}}\) be the operator which applies f element-wise to a matrix. A non-convex inner approximation of \(\mathcal {MC}\) is given by the trigonometric approximation [3, Section 4]

$$\begin{aligned} \mathcal {TA}= \{ {\mathbf {f}}(X) ~|~ X \in \mathcal {SR}\}. \end{aligned}$$

Nesterov proved in [5, Theorem 2.5] that

$$\begin{aligned} \max _{X \in \mathcal {TA}} \langle A, X \rangle = \max _{X \in \mathcal {MC}} \langle A, X \rangle . \end{aligned}$$

Although not convex, \(\mathcal {TA}\) is simpler than \(\mathcal {MC}\) in the sense that checking whether a matrix X is in \(\mathcal {TA}\) can be done in polynomial time by computing \({\mathbf {f}}^{-1}(X)\) and checking whether \({\mathbf {f}}^{-1}(X)\) is in \(\mathcal {SR}\). This allows to reformulate the initial difficult problem (1) as an optimization problem over the algorithmically accessible set \(\mathcal {TA}\). The complexity of the problem in this form arises solely from the non-convexity of this set.

Hirschfeld studied \(\mathcal {TA}\) in [3, Section 4]. In this work, we prove that \(\mathcal {TA}\) possesses an additional beneficial property. Namely, we prove the conjecture of Hirschfeld that it is starlike, i.e., for every \(X \in \mathcal {TA}\) and every \(\lambda \in [0, 1]\), the convex combination \(\lambda X + (1 - \lambda ) I\) of X and the central point I, the identity matrix, is in \(\mathcal {TA}\) (Fig. 1).

Fig. 1
figure 1

\(\mathcal {TA}\), \(\mathcal {MC}\) and \(\mathcal {SR}\)

Full size image

Although this result does not directly lead to a better algorithm, it has the potential to do so because we know something about \(\mathcal {TA}\) that we did not know before (a review of the properties and applications of starshaped sets can be found in [6] and [2]).

2 Hirschfeld’s conjecture

In this section, we describe the conjecture and related results which have been obtained by Hirschfeld in his thesis [3, Section 4.3].

In order to show that \(\mathcal {TA}\) is star-like, one has to prove that

$$\begin{aligned} \forall X \in \mathcal {SR}, ~\forall \lambda \in [0,1],~\mathbf {f}^{-1}(\lambda {\mathbf {f}} X + (1 - \lambda ) I) \in \mathcal {SR}. \end{aligned}$$

Note that the operator acting on X is nearly an element-wise one, defined by the function

$$\begin{aligned} f_\lambda&:&[-1, 1] \longrightarrow [-1, 1] \\&x \longmapsto f^{-1}(\lambda f(x)) = \sin (\lambda \arcsin x) \end{aligned}$$

acting on the off-diagonal elements, while the diagonal elements remain equal to 1, contrary to \({f_\lambda (1) = f^{-1}(\lambda ) = \sin \dfrac{\pi \lambda }{2}}\). Thus one has to show that

$$\begin{aligned} \forall X \in \mathcal {SR}, \forall \lambda \in [0,1],~ {\mathbf {f}}_\lambda (X) + \left( 1 - \sin \dfrac{\pi \lambda }{2} \right) I \succeq 0. \end{aligned}$$

A sufficient condition is that \({\mathbf {f}}_\lambda (X) \succeq 0\) for all \(X \in \mathcal {SR}\) and for all \(\lambda \in [0,1]\), i.e., the element-wise operator \({\mathbf {f}}_\lambda \) is positivity preserving. Hirschfeld conjectured that this sufficient condition is verified [3, Conjecture 4.9].

Lemma 1

$$\begin{aligned} \forall X \in \mathcal {SR}, \forall \lambda \in [0,1],~ {\mathbf {f}}_\lambda (X) \succeq 0 \end{aligned}$$

A sufficient (and necessary) condition for an operator of this type to be positivity preserving is that all of the Taylor coefficients of \(f_\lambda \) are nonnegative [7].

Lemma 1 proves the following theorem.

Theorem 1

\(\mathcal {TA}\) is star-like.

3 Proof of the conjecture

In this section, we prove Lemma 1.

Proof

Let \(\lambda \in [0, 1]\) and write \(f_\lambda \) as a power series

$$\begin{aligned} f_\lambda (x) = \displaystyle \sum _{n \in {\mathbb {N}}}{a_n(\lambda ) x^n}. \end{aligned}$$

The first two derivatives of \(f_\lambda \) are given by

$$\begin{aligned} f_\lambda '(x) = \dfrac{\lambda }{\sqrt{1 - x^2}} \cos (\lambda \arcsin x) \end{aligned}$$

and

$$\begin{aligned} f_\lambda ''(x) = \dfrac{x}{1 - x^2} \dfrac{\lambda \cos (\lambda \arcsin x)}{\sqrt{1 - x^2}} - \dfrac{\lambda ^2}{1 - x^2} \sin (\lambda \arcsin x). \end{aligned}$$

Hence \(f_\lambda \) is a solution on \((-1, 1)\) of the differential equation

$$\begin{aligned} (1 - x^2) f_\lambda '' - x f_\lambda ' + \lambda ^2 f_\lambda = 0. \end{aligned}$$

Therefore, the Taylor coefficients of \(f_\lambda \) verify the recurrence relation

$$\begin{aligned} (n + 2) (n + 1) a_{n + 2}(\lambda ) - n (n - 1) a_n(\lambda ) - n a_n(\lambda ) + \lambda ^2 a_n(\lambda ) = 0 \end{aligned}$$

which can be re-expressed as

$$\begin{aligned} a_{n + 2}(\lambda ) = \dfrac{n^2 - \lambda ^2}{(n + 2) (n + 1)} a_n(\lambda ) \end{aligned}$$
(2)

with initial conditions

$$\begin{aligned} \left\{ \begin{array}{c c c} a_0(\lambda ) &{} = &{} 0 \\ a_1(\lambda ) &{} = &{} \lambda \end{array} \right. . \end{aligned}$$

Given that \(\lambda \in [0, 1]\), a trivial induction shows that

$$\begin{aligned} \forall n \in {\mathbb {N}},\quad a_n(\lambda ) \geqslant 0. \end{aligned}$$

\(\square \)

Recursion (2) also proves that the roots of the polynomials \(a_n(\lambda )\) are located at \(0, \pm 1, ..., \pm n\) and are given by the polynomials \({\widetilde{P}}_n(\lambda )\) [3, eq. 4.23], as also conjectured by Hirschfeld.