## 2 New Results on Closed-Form Formulas  
We first introduce some notations. For \(m<n\), define \(\binom{n}{m}\) to be the number of combinations of \(m\) elements out of \(n\), and let \(\varphi=\underset{i,j\in N}{\text{Max}}\{|q_{i,j}|\}\) and \(M=\varphi*(2,r)\). Furthermore, Lemmas 1 and 2, presented below, help to prove the results. Note that Lemma 1 is a direct deduction from previous results [11]. **Lemma 1**. : _Given a locally optimal solutionx \(=(x_{1},\cdots,x_{n})\)with respect to a 1-flip search, we have:_  
\[\big{(}x_{i}^{\prime}-x_{i}\big{)}E(x_{i})\leq 0,\text{ for }i=1,\,\ldots,\,n. \tag{11}\]  
**Proof. ** The condition of local optimality in Equation (5) indicates that:  
\[(E(x_{i})\geq 0\text{ iff }x_{i}=1),\text{ and }(E(x_{i})\leq 0,\text{ iff }x_{i}=0).\]Using this condition, we thus have:  
\[(x_{i}^{\prime}-x_{i})E(x_{i})\leq 0,\text{ for }i=1,\cdots,n.\]  
\(\square\)  
**Lemma 2. **_Let \(x=(x_{1},\cdots,x_{n})\)be any solution to the problem; then, we have:_  
\[\sum_{i,j\in S}\left(x_{i}^{\prime}-x_{i}\right)\left(x_{j}^{\prime}-x_{j} \right)q_{i,j}\leq M \tag{12}\]  
**Proof. ** For each pair of elements, \(i,j\in S\), the left-hand side can be \(q_{i,j}\) or \(-q_{i,j}\). Since \(\left|S\right|=r\), the summation on the left-hand side is, at most, equal to \(M\). \(\square\)  
**Theorem 1. **_Let \(\varphi\) and \(M\) be as defined above and let \(x=(x_{1},\cdots,x_{n})\) be a locally optimal solution of \(x^{T}Qx\) with respect to a \(1\)-flip search. A subset \(S\subseteq N\), with \(\left|S\right|=r\), is an improving \(r\)-flip move if and only if we have:_  
\[\sum_{i\in S}\left|E(x_{i})\right|\leq\sum_{i,j\in S}\left(x_{i}^{\prime}-x_{i }\right)\left(x_{j}^{\prime}-x_{j}\right)q_{i,j} \tag{13}\]  
**Proof. ** Using Equation (7), a subset \(S\subseteq N\) of \(\mathfrak{r}\) elements is an improving \(r\)-flip move if and only if we have:  
\[\Delta f=f\left(x^{\prime}\right)-f(x)=\sum_{i\in S}\left(x_{i}^{\prime}-x_{i }\right)E(x_{i})+\sum_{i,j\in S}\left(x_{i}^{\prime}-x_{i}\right)\left(x_{j} ^{\prime}-x_{j}\right)q_{i,j}>0 \tag{14}\]  
Since \(x\) is a locally optimal solution with respect to a \(1\)-flip search, it follows from Lemma 1 that Inequality (14) is equivalent to Equation (15); that completes the proof. \[\sum_{i,j\in S}\left(x_{i}^{\prime}-x_{i}\right)\left(x_{j}^{\prime}-x_{j} \right)q_{i,j}>-\sum_{i\in S}\left(x_{i}^{\prime}-x_{i}\right)E(x_{i})=\sum_{ i\in S}\left|E(x_{i})\right| \tag{15}\]  
\(\square\)  
**Proposition 1. **_Let \(\varphi\) and \(M\) be as defined above and let \(x=(x_{1},\cdots,x_{n})\) be any locally optimal solution of the \(x^{T}Qx\) problem with respect to a \(1\)-flip search. If a subset \(S\subseteq N\), with \(\left|S\right|=r\), is an improving \(r\)-flip move, then we must have \(\sum_{i\in S}\left|E(x_{i})\right|<M\)._  
**Proof. ** Since \(x\) is a locally optimal solution with respect to a \(1\)-flip search and \(S\) is an improving \(r\)-flip move, based on Theorem 1, we have:  
\[\sum_{i\in S}\left|E(x_{i})\right|<\sum_{i,j\in S}\left(x_{i}^{\prime}-x_{i} \right)\left(x_{j}^{\prime}-x_{j}\right)q_{i,j} \tag{16}\]  
Using Lemma 2, we also have Equation (17), which completes the proof. \[\sum_{i\in S}\left|E(x_{i})\right|<\sum_{i,j\in S}\left(x_{i}^{\prime}-x_{i} \right)\left(x_{j}^{\prime}-x_{j}\right)q_{i,j}\leq M \tag{17}\]  
\(\square\)  
The consequence of Theorem 1 is as follows. Given a locally optimal solution \(x\) with respect to a \(1\)-flip search, if there is no subset of \(S\) with \(\left|S\right|=r\) that satisfies Equation (13), then \(x\) is also locally optimal solution with respect to an \(r\)-flip search. Furthermore, if there is no subset \(S\) of any size that satisfies Equation (13), then \(x\) is also locally optimal solution with respect to an \(r\)-flip search for all \(r\leq n\). Similar statements are also true regarding Proposition 1. The result of Proposition 1 is significant in the implementation of an \(r\)-flip search.