## 2 New Results on Closed-Form Formulas
### Strategy 1  
We first define a set, \(D(n)\), of candidates for improving moves. Given a locally optimal solution \(x\) with respect to a 1-flip move, let the elements of \(x\) be ordered in ascending absolute value of derivatives, as given in Equation (19). \[\big{|}E\big{(}x_{\pi(1)}\big{)}\big{|}\leq\cdots\leq\big{|}E\big{(}x_{\pi(n) }\big{)}\big{|} \tag{19}\]  
Here, \(\pi(i)\) means the \(i\)-th element of \(x\) in the order \((\pi(1),\cdots,\pi(n))\). Let \(K\) be the largest value of \(k=1,2,\cdot\cdot,n\), where Inequality (20) is satisfied. The set \(D(n)\) is now defined by Equation (21). \[\sum\
olimits_{i=1}^{k}\big{|}E\big{(}x_{\pi(i)}\big{)}\big{|}<M\text{ for }k=1,2,3,\cdots,n \tag{20}\]  
\[D(n)=\big{\{}x_{\pi(1)},\cdots,x_{\pi(K)}\big{\}} \tag{21}\]  
**Lemma 3**. : _Any subset \(S\subseteq D(n)\) satisfies the necessary condition for an improving move._  
**Proof. ** It follows from Proposition 1. There are some advantages to having elements of \(x\) in an ascending order, i.e., Inequality (19):  
1. The smaller the value of \(|E(x_{i})|\) is, the more likely that \(x_{i}\) is involved in an improving \(k\)-flip move for \(k\leq r\) (this might be due to the fact that the right-hand-side value \(M\) in Equation (20) for a given \(r\) is constant. Thus, smaller values of \(|E(x_{i})|\) on the left-hand side might help to satisfy the inequality more easily. 2. Because the elements of \(D(n)\) are in ascending order of absolute values of derivatives, a straightforward implementable series of alternatives to be considered for improving subsets, \(S\), may be the elements of the set given in Equation (22). Note that there are many more subsets of \(D(n)\) compared to the sets in Equation (21) that are candidates for consideration in possible \(k\)-flip moves. Here, we only provide one possible efficient implementable strategy. \[S\in\{\{\pi(1),\pi(2)\},\{\pi(1),\pi(2),\pi(3)\},\cdots,\{\pi(1),\cdots,\pi(K )\}\}\] (22)It is important to note that, if Proposition 1 is used in the process of implementing an algorithm given a locally optimal solution \(x\) with respect to a 1-flip search, after an \(r\)-flip implementation for a subset \(\left|S\right|=r\) with \(r>1\), the locally optimal solution with respect to a 1-flip search for the new solution, \(x^{\prime}\), can be destroyed. Thus, if an \(r\)-flip search needed to be continued, a 1-flip search might be necessary on solution \(x^{\prime}\) before a new \(r\)-flip move could continue. However, there are many practical situations where this problem may be avoided for many subsets, especially when the problem is very large scale, i.e., the value of \(n\) is large and/or \(Q\) is sparse. Proposition 2 is a weaker condition of Proposition 1 that can help be overcome to a certain point in the aforementioned problem. In the proof of Theorem 1 and Proposition 1, we only used a condition of optimality for a 1-flip search satisfied for the members of the subset \(S\). We now define a condition as follows and call it \"condition of optimality with respect to a 1-flip search for a set \(S^{\prime}\), or simply, \"condition of optimality for \(S^{\prime}\)\". Given a solution \(x\), the condition of optimality for any subset \(S\subseteq N\) is satisfied if and only if we have:  
\[\mathit{Either}\ \ (x_{i}=0\ iff\ E(i)<0)\ \ or\ \ (x_{i}=1\ iff\ E(i)\geq 0)\ \text{for}\ i\in S \tag{23}\]  
\(\square\)  
Of course, if we have \(N\) in Equation (23) instead of \(S\), \(x\) is a locally optimal solution, as was defined in Fact 1. For \(m<n\), let \((m,n)\) be the number of combinations of \(m\) elements out of \(n\) elements, \(\varphi_{S}=\max\limits_{i,j\in S}\left\{|q_{i,j}|\right\}\), and \(M_{S}=\varphi_{S}*(2,r)\). With these definitions, we now state Proposition 2. **Proposition 2**. : _(Weak necessary condition): Let \(S\subseteq N\), \(\left|S\right|=r\), and \(\varphi_{S}\) and \(M_{S}\) are as defined above. Given any solution \(x=(x_{1},\cdots,x_{n})\) of \(x^{T}Qx\), assume the condition of optimality is satisfied for a subset \(S\).