# UAV-BS Site Planning Based on Circular Coverage Strategy
## 3 Theory
### Optimality Conditions  
(1) **Lagrange Dual Problem:** This involves incorporating the constraints into the objective function of the original problem, allowing the problem to be solved by minimizing a new function. Specifically, suppose we want to minimize the objective function \(f(x)\), subject to some inequality constraints \(g(x)\leq 0\) and equality constraints \(h(x)=0\). Then, we can introduce the following Lagrangian function:  
\[L(x,\lambda,\
u)=f(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}(x)+\sum_{j=1}^{p}\
u_{j}h _{j}(x), \tag{4}\]  
where \(\lambda\) and \(\
u\) are the Lagrange multipliers associated with the inequality and equality constraints, respectively.  
Among them, \(\lambda_{i}\) and \(\
u_{j}\) are the Lagrange multipliers. Subsequently, the original problem can be solved by minimizing the Lagrangian function, that is, the following:  
\[\min_{x}\max_{\lambda,\
u;\lambda_{i}\geq 0}L(x,\lambda,\
u), \tag{5}\]  
The solution to this problem is known as the Lagrangian dual problem of the original problem. If both the original problem and the dual problem have solutions and their optimal values are equal, then the problem is said to satisfy strong duality.  
(2) **Saddle Point Theorem:** Let \(L(x,\lambda,\
u)\) be the Lagrangian function, and suppose \(x^{*}\in\mathbb{R}^{n}\), \(\lambda^{*}\in\mathbb{R}^{m}\), \(\lambda^{*}\geq 0\), and \(\
u^{*}\in\mathbb{R}^{p}\). If for every \(x\in\mathbb{R}^{n}\), \(\lambda\in\mathbb{R}^{m}\), \(\lambda\geq 0\), and \(\
u\in\mathbb{R}^{p}\), the conditions  
\[L(x,\lambda,\
u)\leq L(x^{*},\lambda^{*},\
u^{*})\leq L(x,\lambda^{*},\
u^{*}), \tag{6}\]  
are satisfied, it is said that \((x^{*},\lambda^{*},\
u^{*})\) is a saddle point of \(L(x,\lambda,\
u)\).  
Assume \((x^{*},\lambda^{*},\
u^{*})\) is a saddle point of the Lagrangian function \(L(x,\lambda,\
u)\) for the original problem. Then, \(x^{*}\) is the optimal solution of the original problem, and \((\lambda^{*},\
u^{*})\) is the optimal solution of its dual problem. Conversely, suppose \(f(x)\) is a convex function, the inequality constraints are convex functions, and the equality constraints are all linear functions--i.e., \(h(x)=Ax-b\), where \(A\) is a full-rank coefficient matrix. Suppose there exists \(\hat{x}\) such that \(g(\hat{x})>0\) and \(h(\hat{x})=0\). If \(x\) is the optimal solution of the original problem, then there exist \((\lambda^{*},\
u^{*})\) with \(\lambda^{*}\geq 0\) such that \((x^{*},\lambda^{*},\
u^{*})\) is a saddle point of the Lagrangian function of the original problem.  
The Saddle Point Theorem provides a sufficient condition for the optimal solution and, in the latter part, illustrates a necessary condition for convex programming. It is important to note that the existence of an optimal solution for the original problem does not imply that the corresponding Lagrangian function necessarily has a saddle point. That is, the existence of a saddle point is not a necessary condition for the original problem to have an optimal solution.  
(3) KKT Conditions: If an optimal solution of a convex optimization problem satisfies certain constraints, then this optimal solution must also satisfy the following requirements:  
1. The inequality constraints of the original problem must be satisfied: \(g_{i}(x^{*})\leq 0\).
2. The equality constraints of the original problem must be satisfied: \(h_{j}(x^{*})=0\),
3. The Lagrange multipliers must be non-negative: \(\lambda_{i}\geq 0\).
4. KKT Conditions: \(\lambda_{i}g_{i}(x^{*})=0\), meaning that the corresponding Lagrange multipliers are non-zero only when the constraints are active.  
The conditions A, B, C, and D are necessary but not sufficient conditions for determining whether a solution is optimal. In practice, KKT conditions can be used to solveoptimization problems with constraints and to verify whether the solutions satisfy the optimality conditions.