# Beam Training for Millimeter-Wave Communication Based on Tabu Table Enhanced Rosenbrock Algorithm
## 5 Tabu-Search-Based Enhanced Rosenbrock Algorithm
### Tabu Search  
The basic idea of the proposed RA enhanced by the tabu table is described in this section. Specifically, the most recent searched solutions of RA is recorded in the tabu table, during the probe moving round, if a probed solution is in the tabu table after rounding to the integer operation, the tabu search is applied to obtain the solution, which optimally is near the solution before rounding operation, but different with the solution after the rounding operation. The proposed algorithm proceeds as follows. Firstly, the probed solution \(x^{(i+1)}\) is obtained by exploring the \(ith\) direction of the probe moving just like in the classical RA. If \(x^{(i+1)}\) is in the tabu table, the best solution among the neighborhood of \(x^{(i+1)}\) is selected as the starting point for the next move, and using the special criteria to reward some excellent states. In the next section, four important aspects of the RA enhanced by tabu table, including neighborhood definition, tabu table, aspiration criterion, and stopping criterion, will be elaborated in detail. 1. Neighborhood definition  
Neighborhood structure and size are vital parameters for the TS algorithm to improve performance. A larger neighborhood will reduce the time TS stays in a local optimal state and accelerate its movement towards the global optimum. However, if the neighborhood is too large, the time complexity will make the TS algorithm infeasible. In this paper, taking the current solution \(x^{(i)}\) as the center, and the open interval with \(R\) as the radius is called the neighborhood of \(x^{(i)}\), which is denoted as \(v_{R}\Big{(}x^{(i)}\Big{)}\). The neighborhood radius of 1 as an example is discussed in this paper. In TS, defined neighborhoods are not all searched, but can be a part of them. We can increase the scope of exploration by increasing the radius of the neighborhood, but the search complexity increases. To this end, some methods are adopted to select some neighborhood explorations, such as random selection, or steepest descending direction selection. For UPA with \(R=1\), the horizontal direction and vertical direction corresponding to \(v_{R}\Big{(}x^{(i)}\Big{)}\) satisfies: (1) It has only one column that is different from the corresponding column in \(x^{(i)}\); (2) The direction difference between the two corresponding columns equals one. Let \(x^{(i)}\) denotes the current solution of the proposed TS-based beam search, and \(v_{1}\Big{(}x^{(i)}\Big{)}=\Big{\{}U_{1}^{(i)},\ U_{2}^{(i)},\ldots,\ U_{|v_{1 }|}^{(i)}\Big{\}}\) presents the neighborhood of \(x^{(i)}\), where \(|v_{1}|\) is the cardinality of \(v_{1}\). Based on the neighborhood definition above, it is obvious that \(|v_{1}|=2\cdot 2^{n}=2^{n+1}\). We then define that the \(uth\) neighbor in \(v_{1}\Big{(}x^{(i)}\Big{)}\) is different from \(x^{(i)}\) in the \([u/2^{n}]th\) column [24]. According to the index definition  
\begin{table}
\begin{tabular}{c c c c c c} \hline  & **1** & \(\ldots\) & \(\mathbf{h_{t}}\) & \(\ldots\) & **32** \\ \hline \(\mathbf{v_{t}=1}\) & 1 & \(\ldots\) & \(I_{t}=(v_{t}-1)\cdot H_{t}+(-1)^{(v_{t}-1)}\cdot h_{t}\) & \(\ldots\) & 32 \\ \(\mathbf{v_{t}=2}\) & 64 & \(\ldots\) & \(I_{t}=v_{t}\cdot H_{t}+(-1)^{(v_{t}-1)}\cdot(h_{t}-1)\) & \(\ldots\) & 33 \\ \(\mathbf{v_{t}=3}\above, it is obvious that \(x^{(i)}=[index(v_{t},\;h_{t}),\;index(v_{r},\;h_{r})]\), which shows that in the current solution, the signal is transmitted along the \(h_{t}th\) horizontal direction and the \(v_{t}th\) vertical direction, and is received along the \(h_{t}th\) horizontal direction and the \(v_{r}th\) vertical direction. Both \(v_{t}\) and \(v_{r}\) are odd numbers. Take this case as an example, the neighborhood of \(x^{(i)}\) is: \[