Elementary Properties of Positive Concave Mappings With Applications to Network Planning and Optimization

Renato L. G. Cavalcante, Yuxiang Shen, Sławomir StańczakIEEE TSP 2015 · DOI · arXiv

Abstract

In wireless network planning, determining the feasibility of a network configuration—such as base station placement and power levels—is a critical but computationally intensive task. This paper introduces a novel framework for accelerating the computation of fixed points in positive concave mappings, which are the mathematical foundations of these feasibility checks. By constructing a "lower bounding matrix" based on the mapping's asymptotic behavior, the authors provide a necessary condition for network feasibility and a new iterative algorithm that converges significantly faster than standard methods. The approach is demonstrated through load and power estimation problems in LTE networks.

Introduction

Modern wireless network design requires engineers to evaluate whether a specific configuration can support the required user traffic. This "feasibility check" often involves solving a system of non-linear equations to estimate network load or power allocation. Mathematically, these problems are modeled as finding the fixed point of an interference mapping, denoted as $T(x) = x$.

While standard iterative algorithms exist to find these points, they can be slow, particularly in large-scale network planning scenarios. Furthermore, designers need a way to "fail fast"—to determine if a fixed point even exists before committing computational resources to a long iterative process. This paper addresses these challenges by utilizing tools from convex analysis to accelerate convergence and provide early indicators of infeasibility.

Methodology

The authors focus on positive concave mappings. Their approach relies on two primary innovations: the construction of a lower bounding matrix and the definition of an accelerated mapping.

1. The Lower Bounding Matrix ($M$)

The authors demonstrate how to construct a non-negative matrix $M$ that acts as a linear "floor" for the complex non-linear mapping. They provide two equivalent methods for building this matrix:

  • Supergradients: A generalization of derivatives for non-smooth concave functions.
  • Recession Functions: These describe the asymptotic behavior of the mapping as input values grow toward infinity.

A critical insight of this work is that if the spectral radius of this matrix, $\rho(M)$, is greater than or equal to one, a fixed point cannot exist. This provides a computationally inexpensive "certificate of infeasibility" for network designers.

2. The Accelerated Mapping ($T_A$)

Once the matrix $M$ is established, a new mapping is defined: $$T_A(x) = (I - M)^{-1}(T(x) - Mx)$$

This accelerated mapping is mathematically guaranteed to share the same fixed point as the original mapping $T$. By "subtracting out" the linear components captured by $M$, the iteration can focus on the remaining non-linearities. Crucially, $T_A$ preserves the properties of a standard interference mapping, ensuring robust convergence behavior while reaching the solution in fewer steps.

Experimental Setup

The proposed methods were evaluated using numerical simulations of an LTE network. The simulation parameters included a carrier frequency of 900 MHz and a network size of 25 base stations serving 200 users. The propagation was modeled using the Okumura-Hata model for urban environments, with users and base stations uniformly distributed over a 2500m x 2500m field.

Key Results

The acceleration method was tested on two fundamental problems: Load Estimation and Power Estimation.

  • Load Estimation: The accelerated mapping reached a Normalized Mean Error (NME) of $10^{-9}$ in approximately 10 iterations. In contrast, the standard mapping required significantly more iterations to achieve the same level of precision.
  • Power Estimation: The gains were even more pronounced in power estimation. While the standard iteration required nearly 200 iterations to reach an NME of $10^{-4}$, the accelerated version achieved the same result in fewer than 150 iterations, demonstrating a clear improvement in the convergence slope.
  • Computational Efficiency: Although $T_A$ requires a matrix inversion, this is a one-time cost. Subsequent iterations only require simple matrix-vector multiplication, making the per-iteration overhead minimal compared to the reduction in total iterations.

Discussion and Limitations

While the framework provides a powerful tool for network optimization, there are important considerations for its application. The condition $\rho(M) < 1$ is a necessary condition for the existence of a fixed point, but it is not always sufficient. In some cases, such as power estimation, a fixed point might not exist even if the spectral radius is less than one. Turning this into an "if and only if" condition requires additional assumptions on the mapping.

Additionally, the benefit of this method is most apparent when the original mapping $T$ is computationally expensive to evaluate. If $T$ is relatively simple, the initial overhead of calculating $M$ and its inverse may outweigh the savings gained from faster convergence.

Conclusion

This paper generalizes previous load-coupling models by using recession functions to prove that lower-bounding properties hold for any positive concave mapping. By providing both a faster iterative method and a shortcut for identifying infeasible network designs, this framework offers a significant improvement for large-scale wireless network planning and optimization tasks. Future research may extend these concepts to broader classes of mappings beyond the concave case.

Summary updated

Abstract

This paper presents novel methods for computing fixed points of positive concave mappings and for characterizing the existence of fixed points. These methods are particularly important in planning and optimization tasks in wireless networks. For example, previous studies have shown that the feasibility of a network design can be quickly evaluated by computing the fixed point of a concave mapping that is constructed based on many environmental and network control parameters such as the position of base stations, channel conditions, and antenna tilts. To address this and more general problems, given a positive concave mapping, we show two alternative but equivalent ways to construct a matrix that is guaranteed to have spectral radius strictly smaller than one if the mapping has a fixed point. This matrix is then used to build a new mapping that preserves the fixed point of the original positive concave mapping. We show that the standard fixed point iterations using the new mapping converges faster than the standard iterations applied to the original concave mapping. As exemplary applications of the proposed methods, we consider the problems of power and load estimation in networks based on the orthogonal frequency division multiple access (OFDMA) technology.
BibTeX
@article{cavalcante2015elementary,
  author = {Renato L. G. Cavalcante and Yuxiang Shen and Sławomir Stańczak},
  title = {{Elementary Properties of Positive Concave Mappings With Applications to Network Planning and Optimization}},
  journal = {IEEE Transactions on Signal Processing},
  year = {2015},
  doi = {10.1109/tsp.2015.2502544},
}
Figure