# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 5 Linear Programming-Based Approximation Algorithm
### Mathematical Foundations
If there exist \(x_{1}^{\prime},x_{2}^{\prime},...,x_{n}^{\prime}\), such that for any \(i\in\{1,2,...,n\}\), the following equations hold:_  
\[\min\sum_{i=1}^{n}\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}p_{i}^{l_{i}+j}\leq\sum _{i=1}^{n}\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}^{\prime}p_{i}^{l_{i}+j}=\sum_ {i=1}^{n}f_{i}(z_{i}^{\prime})=\min\sum_{i=1}^{n}f_{i}(z_{i}) \tag{15}\]1  
_then \(x_{1}^{\prime},...,x_{n}^{\prime}\) are the optimal solutions to the following problem._  
\[ \begin{split}&\max\sum_{i=1}^{n}\left(1-p_{i}^{x_{i}}\right)\\ & s.t.\sum_{i=1}^{n}a_{i}x_{i}\leq\Delta\\ & x_{i}\in R,i\in\{1,2,...,n\}\end{split}  \tag{19}\]  
Proof. : For any \(i\in\{1,2,...,n\}\), \(p_{i}^{x}\) is a decreasing function. By contradiction, it is easily proven that the objective function achieves the maximum if and only if \(\sum_{i=1}^{n}a_{i}x_{i}=\Delta\). Since \(x_{1},x_{2},...,x_{n}\) are real numbers and the only constraint is equality, then we can derive the optimal solutions by the Lagrange multiplier method. We integrate the objective function and the constraint multiplied by \(\omega\) to the following Lagrange function:  
\[\Lambda(x_{1},x_{2},...,x_{n},\omega)=\sum_{i=1}^{n}\left(1-p_{i}^{x_{i}} \right)+\omega\left(\sum_{i=1}^{n}a_{i}x_{i}-\Delta\right)\]  
Since \(\sum_{i=1}^{n}a_{i}x_{i}-\Delta=0\), \(\Lambda(x_{1},...,x_{n},\omega)\) is a function with respect to \(x_{1},...,x_{n}\). The gradients on \(x_{1},...,x_{n}\) and \(\omega\) are as follows:  
\[\left\{ \begin{array}{l}\frac{\partial\Lambda}{\partial x_{1}} \mathbf{=}-p_{1}^{x_{1}}\ln(p_{1})+\omega a_{1}\\ \vdots\\ \frac{\partial\Lambda}{\partial x_{1}}\mathbf{=}-p_{i}^{x_{i}}\ln(p_{i})+ \omega a_{i}\\ \vdots\\ \frac{\partial\Lambda}{\partial x_{n}}\mathbf{=}-p_{n}^{x_{n}}\ln(p_{n})+ \omega a_{n}\\ \frac{\partial\Lambda}{\partial\omega}\mathbf{=}\sum_{i=1}^{n}a_{i}x_{i}- \Delta\end{array} \right. \tag{20}\]  
For any \(i\in\{1,2,...,n\}\) and \(j\in\{1,2,...,n\}\), we have \(\frac{\partial^{2}\Lambda}{\partial x_{2}\partial x_{2}}=0\) if \(i\
eq j\). For any \(i\in\{1,2,...,n\}\), it is easily derived that \(\frac{\partial^{2}\Lambda}{\partial^{2}x_{i}}=-p_{i}^{x_{i}}\ln^{2}(p_{i})\). The Hessian matrix of \(\Lambda(x_{1},x_{2},...,x_{n})\) is as follows. \[\frac{\partial^{2}\Lambda}{\partial x_{i}\partial x_{j}}=-\left( \begin{array}[] {cccc}p_{1}^{x_{1}}\ln^{2}(p_{1})&0&\ldots&\ldots&0\\ 0&\ddots&0&\ldots&\ldots\\ \ldots&0&p_{i}^{x_{1}}\ln^{2}(p_{i})&0&\ldots\\ \ldots&\ldots&0&\ddots&0\\ \ldots&\ldots&\ldots&0&p_{n}^{x_{n}}\ln^{2}(p_{n})\end{array} \right)\]  
Then, the following equalities can be easily derived. \[ \begin{split}&\lambda\mathbf{E}-\frac{\partial^{2}\Lambda(x_{1},x_ {2},...,x_{n})}{\partial x_{2}\partial x_{2}}\\ &=\left(\begin{array}{cccc}\lambda+p_{1}^{x_{1}}\ln^{2}(p_{1})&0& \ldots&\ldots&0\\ 0&\ddots&0&\ldots&\ldots\\ \ldots&0&\lambda+p_{i}^{x_{i}}\ln^{2}(p_{i})&0&\ldots\\ \ldots&\ldots&0&\ddots&0\\ \ldots&\ldots&\ldots&0&\lambda+p_{n}^{x_{n}}\ln^{2}(p_{n})\end{array}\right)\\ &\left|\lambda\mathbf{E}-\frac{\partial^{2}\Lambda(x_{1},x_{2},...,x_{n})}{ \partial x_{2}\partial x_{2}}\right|=\prod\limits_{i=1}^{n}\left(\lambda+p_{i} ^{x_{i}}\ln^{2}(p_{i})\right)\end{split} \]Since all of the eigenvalues of \(\frac{\partial^{2}\Delta(x_{1},...,x_{n})}{\partial x_{i}\partial x_{j}}\) are negative, the Hessian matrix of \(\Lambda(x_{1},...,x_{n})\) is negative definite. In conclusion, if there exist \(x_{1}^{\prime},...,x_{n}^{\prime}\), such that for any \(i\in\{1,2,...,n\}\), \(\frac{\partial\Lambda}{\partial x_{i}^{\prime}}=0\), then \(x_{1}^{\prime},...,x_{n}^{\prime}\) are the optimal solutions to Equation (19). **Theorem 11**. : \(x_{1}^{\prime},...,x_{n}^{\prime}\) _are the optimal solutions to Equation (19), if for any \(i\in\{1,2,...,n\}\), \(x_{i}^{\prime}\) satisfies Equation (21)._  
\[x_{i}^{\prime}=\frac{\Delta-\sum_{i=1}^{n}a_{i}\log_{p_{i}}^{-a_{i}(\ln p_{i} )^{-1}}}{\ln p_{i}\sum_{i=1}^{n}a_{i}(\ln p_{i})^{-1}}+\log_{p_{i}}^{-a_{i}( \ln p_{i})^{-1}} \tag{21}\]  
Proof.