## 2 Sensor Network Localization
### Semidefinite Programming (SDP) for Sensor Network Localization  
The section considers localization problem when information on distances for anchor nodes and unknown sensors nodes are given. Suppose we consider localization problem on the plane. We have \(m\) known points \(a_{k}\in\mathit{I\!R}^{2}\), \(k=1,...,m\) and \(n\) unknown nodes \(x_{j}\in\mathit{I\!R}^{2}\), \(j=1,...,n\). Let us consider three sets of node pairs \(N_{e}\), \(N_{l}\), \(N_{u}\). For pairs in \(N_{e}\) we know exact distances \(d_{kj}\) between \(a_{k}\) and \(x_{j}\) and \(\hat{d_{ij}}\) between \(x_{i}\) and \(x_{j}\). \(N_{l}\) is a set of pairs with known lower bounds \(\underline{r}_{kj}\) and \(\underline{r}_{ij}\). Finally, \(N_{u}\) is a set of upper bounds \(\overline{r}_{kj}\) and \(\overline{r}_{ij}\). Naturally our goal is to minimize estimation error which immediately lead us to the following non-convex optimization problem  
\[ \begin{split}\min&\sum_{(i,j)\in N_{e},\ i<j}||x_{i} -x_{j}||^{2}-\hat{d}_{ij}^{2}|\\ &+\sum_{(k,j)\in N_{e}}||a_{k}-x_{j}||^{2}-d_{kj}^{2}|\\ &+\sum_{(i,j)\in N_{l},\ i<j}(||x_{i}-x_{j}||^{2}-\underline{r}_ {ij}^{2})_{-}\\ &+\sum_{(k,j)\in N_{l}}(||a_{k}-x_{j}||^{2}-\underline{r}_{kj}^{ 2})_{-}\\ &+\sum_{(i,j)\in N_{u},\ i<j}(||x_{i}-x_{j}||^{2}-\overline{r}_{ ij}^{2})_{+}\\ &+\sum_{(k,j)\in N_{u}}(||a_{k}-x_{j}||^{2}-\overline{r}_{kj}^{ 2})_{+},\end{split}  \tag{1}\]  
where \((u)_{-}\) and \((u)_{+}\) are defined as  
\[ \begin{split}(u)_{-}&=\max\{0,-u\}\\ (u)_{+}&=\max\{0,u\}.\end{split} \]  
The norm of vector \(x\) is defined as \(\|x\|=\sqrt{x^{T}x}\). In [18; 19] the authors study semidefinite relaxations of the problem. Figure 2: Node A computes its bearing to L using information from B and CThe formulated problem can be rewritten by introducing matrix notation and slack variables as  
\[\min\sum_{(i,j)\in N_{e},\ i<j} (\alpha_{ij}^{+}+\alpha_{ij}^{-})+\sum_{(k,j)\in N_{e},}(\alpha_{kj} ^{+}+\alpha_{kj}^{-})\] \[+\sum_{(i,j)\in N_{l},\ i<j}\beta_{ij}^{-}+\sum_{(k,j)\in N_{l}} \beta_{kj}^{-}\] \[+\sum_{(i,j)\in N_{u},\ i<j}\beta_{ij}^{+}+\sum_{(k,j)\in N_{u}} \beta_{ij}^{+}\] s.t. \[s_{ij}^{T}Ye_{ij}-d_{ij}2=\alpha_{ij}^{+}-\alpha_{ij}^{-},\ \forall i,j\in N_{e},\ i<j,\] \[(a_{k};e_{j})^{T}\left( \begin{array}{cc}I&X\\ X^{T}&Y\end{array} \right)(a_{k};e_{j})-(\hat{d}_{kj})^{2}=\alpha_{kj}^{+}- \alpha_{kj}^{-},\] \[\forall k,j\in N_{e},\] \[e_{ij}^{T}Ye_{ij}-(d_{ij})^{2}\geq-\beta_{ij}^{-},\ \forall i,j\in N_{l},\ i<j\] \[(a_{k};e_{j})^{T}\left( \begin{array}{cc}I&X\\ X^{T}&Y\end{array} \right)(a_{k};e_{j})-(\underline{r}_{kj})^{2}\geq-\beta_{kj}^ {-},\] \[\forall k,j\in N_{l},\] \[e_{ij}^{T}Ye_{ij}-(d_{ij})^{2}\leq\beta_{ij}^{-},\ \forall i,j\in N_{l},\ i<j\] \[(a_{k};e_{j})^{T}\left( \begin{array}{cc}I&X\\ X^{T}&Y\end{array} \right)(a_{k};e_{j})-(\underline{r}_{kj})^{2}\leq\beta_{kj}^ {-},\] \[\forall k,j\in N_{l},\] \[\alpha_{ij}^{+},\alpha_{ij}^{-},\alpha_{kj}^{+},\alpha_{kj}^{-}, \beta_{ij}^{+},\beta_{ij}^{-},\beta_{kj}^{+},\beta_{kj}^{-}\leq 0,\] \[Y=X^{T}X.\]  
Here \(X=[x_{1},x_{2},\ldots,x_{n}]\) is a \(2\times n\) matrix. In order to cope with nonconvexity equality, \(Y=X^{T}X\) is replaced with \(Y\succeq X^{T}X\) or equivalently  
\[Z:=\left( \begin{array}{cc}I&X\\ X^{T}&I\end{array} \right)\succeq 0.\]The last relation leads to a standard SDP formulation:  
\[\min\sum_{(i,j)\in N_{e},\ i<j} (\alpha_{ij}^{+}+\alpha_{ij}^{-})+\sum_{(k,j)\in N_{e},}(\alpha_{kj} ^{+}+\alpha_{kj}^{-})\] \[+\sum_{(i,j)\in N_{l},\ i<j}\beta_{ij}^{-}+\sum_{(k,j)\in N_{l}} \beta_{kj}^{-}\] \[+\sum_{(i,j)\in N_{u},\ i<j}\beta_{ij}^{+}+\sum_{(k,j)\in N_{u}} \beta_{ij}^{+}\] s.t.