PaperlayerView exact revision on arXiv

Source-linked AI summary

MAPEL: Achieving Global Optimality for a Non-convex Wireless Power Control Problem

Liping Qian, Ying Jun Zhang, Jianwei Huang

arXiv:0805.2675v2cs.NImath.NA

TL;DR

Weighted throughput maximization is typically non-convex because of complicated interference coupling, and strong interference can make geometric programming solutions far from optimum. MAPEL reformulates the objective using exponentiated linear fractional functions and is guaranteed to globally converge to an optimal solution despite nonconvexity, with a tunable performance–convergence-time tradeoff.

  • Problem

    Weighted throughput maximization is typically non-convex because of complicated interference coupling, while strong interferences can make geometric programming solutions far from optimum.

  • Method

    MAPEL is an algorithm based on a product of exponentiated linear fractional functions and an increasing objective formulation for power allocation.

  • Results

    MAPEL is guaranteed to find one global optimal solution of the weighted throughput maximization problem within a finite amount of time and globally converge despite nonconvexity.

  • Takeaways & Limitations

    Tuning MAPEL provides a tradeoff between performance and convergence time.

Abstract

from arXiv · show

Achieving weighted throughput maximization (WTM) through power control has been a long standing open problem in interference-limited wireless networks. The complicated coupling between the mutual interferences of links gives rise to a non-convex optimization problem. Previous work has considered the WTM problem in the high signal to interference-and-noise ratio (SINR) regime, where the problem can be approximated and transformed into a convex optimization problem through proper change of variables. In the general SINR regime, however, the approximation and transformation approach does not work. This paper proposes an algorithm, MAPEL, which globally converges to a global optimal solution of the WTM problem in the general SINR regime. The MAPEL algorithm is designed based on three key observations of the WTM problem: (1) the objective function is monotonically increasing in SINR, (2) the objective function can be transformed into a product of exponentiated linear fraction functions, and (3) the feasible set of the equivalent transformed problem is always normal although not necessarily convex. The MAPLE algorithm finds the desired optimal power control solution by constructing a series of polyblocks that approximate the feasible SINR region in increasing precision. Furthermore, by tuning the approximation factor in MAPEL, we could engineer a desirable tradeoff between optimality and convergence time. MAPEL provides an important benchmark for performance evaluation of other heuristic algorithms targeting the same problem. With the help of MAPEL, we evaluate the performance of several respective algorithms through extensive simulations.

I. INTRODUCTION

Weighted throughput maximization in interference-limited wireless networks remains difficult because interference coupling makes the feasible SINR region non-convex. MAPEL addresses this open problem in the general SINR regime by globally converging through polyblock approximation.

  • Problem: Joint SINR allocation and power control is harder than fixed-SINR targeting because the feasible SINR region is typically non-convex.The non-convexity arises from complicated interference coupling between links.
  • Prior approaches: High-SINR approaches approximate WTM and transform it into a convex geometric program, but the high-SINR assumption is not generally valid.Strong interference can also make standard GP solutions far from optimum.
  • Prior approaches: Existing non-high-SINR work transforms WTM into an NP-hard signomial program and uses successive convex programming that guarantees only local optimality.Improper initialization may considerably degrade system throughput.
  • MAPEL: MAPEL uses monotonicity, an exponentiated linear-fractional objective, and a normal feasible set to approximate the feasible SINR boundary with polyblocks.Increasing approximation accuracy supports solving the equivalent multiplicative linear fractional programming problem.
  • MAPEL: MAPEL is guaranteed to find a global optimal WTM solution within finite time, while its approximation factor tunes the tradeoff between performance and convergence time.The algorithm is intended for the general SINR regime and provides a benchmark for centralized, distributed, optimal, and heuristic algorithms.
  • Evaluation and extensions: Simulations use MAPEL as a benchmark to evaluate and improve the performance of two state-of-the-art centralized and distributed algorithms.The paper also notes that MAPEL can be adapted to the centralized max-min SINR problem.

II. SYSTEM MODEL

The paper models weighted sum-throughput maximization as power allocation in an interference-coupled wireless ad hoc network with power and minimum-rate constraints. In transmit-power variables, the resulting problem is non-convex, motivating an equivalent formulation for global optimization.

  • The system comprises M distinct wireless links, each with a transmitter, receiver, channel gains, transmit power, and receiving noise.
  • Each link’s SINR determines its Shannon-capacity data rate through log(1 + SINR), while interference depends on the other links’ transmit powers.
  • The optimization maximizes weighted sum throughput subject to individual minimum data-rate requirements and per-link power bounds.
  • Minimum rate requirements can be converted into minimum SINR constraints, and feasibility can be checked using a matrix maximum-eigenvalue test followed by a power-allocation bound check.
  • A feasible solution may not exist when the minimum-rate requirements cannot be jointly satisfied.
  • The problem is non-convex in transmit power, making efficient centralized computation of a global optimum difficult; the paper transforms it into MLFP for MAPEL.

III. POWER CONTROL AS MULTIPLICATIVE LINEAR FRACTIONAL PROGRAMMING (MLFP)

The power-control problem is reformulated as a multiplicative linear fractional program whose feasible SINR set is normal, enabling global optimization despite possible non-convexity.

  • The paper introduces GLFP and identifies the reformulated power-control problem as its multiplicative special case, MLFP.
  • Using logarithm properties, the original objective becomes a product of exponentiated linear fractional functions.
  • Positive noise power makes the relevant numerator and denominator functions strictly positive, supporting the MLFP reformulation.
  • Because the transformed objective is increasing in SINR, an optimum occurs on the boundary of the feasible SINR region and corresponds to the original power-control optimum.
  • The formulation preserves equivalence among Problems P1, P2, and P3 under the stated power-equation conditions.
  • The feasible transformed set is a union of infinitely many boxes and is therefore normal, although it is generally non-convex.

IV. THE MAPEL ALGORITHM

MAPEL is proposed as a specialized algorithm for solving the MLFP formulation of the transformed wireless power-control problem.

  • MAPEL is a novel algorithm designed to solve Problem P3 using the special characteristics of MLFP.
  • The algorithm is introduced after mathematical preliminaries needed to exploit the transformed problem’s structure.

A. Related Mathematical Preliminaries

The preliminaries define polyblocks, projections, upper boundaries, and proper vertices for approximating normal feasible sets. Increasing objectives attain their maxima at proper vertices, enabling iterative polyblock refinement.

  • Definitions: A polyblock is formed by taking the union of boxes anchored at the origin whose vertices come from a finite nonnegative vector set.
  • Definitions: A proper vertex has no distinct vertex that is component-wise greater than it, making proper vertices Pareto optimal.
  • Optimization property: For an increasing objective, the maximum over a polyblock occurs at one of its proper vertices.
  • Definitions: A projection maps a nonzero nonnegative vector to the boundary of a normal set along the halfline from the origin.
  • Polyblock refinement: Replacing a vertex with projected vertices and removing improper elements constructs a smaller polyblock that still contains the feasible normal set.
  • Illustrations: Figures 2(a) and 2(b) illustrate boxes, polyblocks, projections, and the vertex-replacement procedure used to improve approximation accuracy.

B. The MAPEL Algorithm

MAPEL approximates the feasible SINR region with a sequence of polyblocks and iteratively refines them using max-min projections until an optimal power allocation is obtained.

  • B. The MAPEL Algorithm: MAPEL begins with a polyblock containing the feasible SINR region and repeatedly replaces selected vertices with projected vertices.Improper vertices are removed, producing a nested sequence of polyblocks that contains the feasible region.
  • B. The MAPEL Algorithm: The algorithm terminates when the distance between the selected vertex and its projection satisfies the δ-based error tolerance.The parameter δ is a small positive approximation factor controlling the termination criterion.
  • B. The MAPEL Algorithm: The projection subproblem is a generalized linear fractional program solved with a modified Dinkelbach-type algorithm.Its inner iterations use linear programming in the convex power domain.
  • B. The MAPEL Algorithm: At each iteration, MAPEL selects the vertex maximizing the transformed objective over the current polyblock.The projection of that vertex onto the feasible region is computed through a max-min problem.
  • B. The MAPEL Algorithm: After termination, MAPEL computes the optimal power allocation from the final feasible SINR solution.The procedure can repeat polyblock construction and vertex projection until an optimal solution is found.

C. Global Convergence

MAPEL globally converges by generating nested polyblocks and a subsequence of projected vertices that approaches the boundary of the feasible SINR region.

  • C. Global Convergence: MAPEL globally converges to a global optimal solution of Problem P3.The convergence argument follows from the behavior of projected vertices within the nested polyblocks.
  • C. Global Convergence: A subsequence of generated vertices has infinite length and is formed through successive projections of polyblock vertices.The subsequence need not contain adjacent iterations because projections of other vertices may occur between its elements.
  • C. Global Convergence: The projected subsequence converges to the boundary of the feasible region.The projection distances between successive subsequence elements approach zero.
  • C. Global Convergence: Because each selected vertex maximizes the objective over its current set, the boundary limit is a global optimum of Problem P3.MAPEL terminates once the optimal solution to Problem P3 is found, so subsequence convergence establishes algorithm convergence.

D. Trade-off between Performance and Convergence Time

The approximation factor δ controls MAPEL’s performance–runtime trade-off: positive δ gives finite termination, while smaller δ improves accuracy but increases computation.

  • D. Trade-off between Performance and Convergence Time: 0 < δ ensures that MAPEL terminates in a finite number of steps.When δ = 0, the convergence time is infinite.
  • D. Trade-off between Performance and Convergence Time: The MAPEL solution is an optimal ε-solution with ε no greater than δ when the algorithm converges.The bound follows from the termination condition and the objective approximation inequality.
  • D. Trade-off between Performance and Convergence Time: In practice, the achieved error can be much smaller than δ, so the theoretical performance bound may be loose.This indicates that δ provides a practical tuning knob rather than an exact prediction of the observed error.
  • D. Trade-off between Performance and Convergence Time: Smaller δ yields a more accurate solution but causes the algorithm to run longer.The number of iterations increases as δ decreases, with a drastic change when δ is close to 0.

E. Extension to Max-min SINR Power Control

MAPEL also supports max-min SINR power control because that formulation is a generalized linear fractional program similar to the problem solved inside MAPEL.

  • E. Extension to Max-min SINR Power Control: Previous power-control work considered maximizing the minimum SINR across all links.This objective is formulated as a max-min optimization problem.
  • E. Extension to Max-min SINR Power Control: The max-min SINR formulation is a generalized linear fractional program similar to Problem (6).Therefore, the Dinkelbach-type algorithm used for Problem (6) can be extended to solve it.
  • E. Extension to Max-min SINR Power Control: MAPEL’s approximation factor improves performance as δ decreases, while the required iterations increase.In the example, δ = 0.1 produces 4.655bps/Hz, only 0.025% from the exact optimum.
  • E. Extension to Max-min SINR Power Control: MAPEL enables characterization of a global optimal solution for an arbitrary wireless network, which was previously impossible without exhaustive search.It is also used to investigate characteristics of global optimal power-control solutions.
  • E. Extension to Max-min SINR Power Control: In the four-link topology example, only Link 1 transmits at maximum power when links are very close together.As the topology parameter increases, Link 3 and then Link 4 begin transmitting, with larger channel gains receiving priority in this example.
  • E. Extension to Max-min SINR Power Control: The illustrated channel-gain priority pattern is not necessarily general because it comes from a particular toy example.MAPEL finds one of potentially many global optimal solutions depending on the initial conditions.

VI. PROVIDING BENCHMARK FOR EXISTING POWER CONTROL ALGORITHMS

MAPEL serves as a global-optimality benchmark for centralized and distributed algorithms addressing the WTM problem. The section reviews representative centralized methods, including SPC, which uses successive approximations.

  • MAPEL provides quantitative benchmarks for centralized and distributed WTM algorithms across network densities and topologies.The measurements include the probability of achieving global optimality and the sub-optimality gap.
  • The reviewed algorithms are representative centralized and distributed approaches for the same WTM problem.The section emphasizes MAPEL’s use as a benchmark rather than restricting evaluation to a particular existing algorithm.
  • Centralized algorithm: SPC: SPC is a centralized algorithm that rewrites WTM as minimizing a ratio between two posynomials.Each successive approximation replaces the signomial program with a geometric program solved by a centralized interior-point method.

2) Asynchronous Distributed Pricing (ADP) Algorithm [16]:

ADP is a distributed pricing algorithm whose links asynchronously update prices and transmit powers using limited network information. Experiments compare its performance with MAPEL and other algorithms across initializations, topologies, densities, and data-rate constraints.

  • ADP algorithm: ADP updates interference prices and transmit powers iteratively and asynchronously, requiring each link to acquire only limited network information.The algorithm is designed for WTM without minimum data-rate constraints.
  • ADP algorithm: ADP converges very fast in the numerical experiments because its updates use no stepsize, but theoretical convergence to the global optimum is difficult to prove.
  • Random initializations: MAPEL always converges to the global optimum regardless of the initial power allocation, whereas SPC and ADP sometimes become trapped in local optima.
  • Random initializations: 70.8% and 62.6% are the global-optimum rates for SPC and ADP, respectively, in one topology; the corresponding rates in another topology are 96% and 93.6%.These comparisons use 500 different initial feasible power allocations.
  • Average performance without minimum data rate constraints: GP performs reasonably well at low network density but has a much larger gap from the global optimum as density increases.At higher density, many links need to remain silent to avoid heavy interference.
  • Average performance with minimum data rate constraints: All algorithms’ sum throughputs decrease as minimum data-rate constraints become more stringent, while the GP–MAPEL gap narrows at high constraints.Higher required data rates force operation toward the high-SINR regime, where GP’s assumption becomes more reasonable.
  • Average performance with minimum data rate constraints: ADP is omitted from the minimum-data-rate experiment because it performs poorly in that setting.

VII. CONCLUSIONS AND DISCUSSIONS

MAPEL reformulates weighted throughput maximization into a monotonic optimization problem and globally converges despite nonconvexity. It also provides a performance benchmark for power-control heuristics and exposes a performance–convergence-time tradeoff.

  • Conclusions and Discussions: MAPEL is guaranteed to globally converge to an optimal solution despite the problem's nonconvexity.The paper identifies global convergence as the central theoretical result.
  • Conclusions and Discussions: MAPEL reformulates WTM as an MLFP and approximates the feasible region's upper boundary with shrinking polyblocks.The sequence increasingly approximates the region around the global optimum.
  • Conclusions and Discussions: Tuning MAPEL establishes a tradeoff between solution performance and convergence time.The approximation factor controls this tradeoff, allowing different accuracy–runtime choices.
  • Conclusions and Discussions: Although centralized, MAPEL provides a benchmark for evaluating existing and newly proposed power-control heuristics.The benchmark supports comparison across centralized and distributed approaches.
  • Conclusions and Discussions: Simulations compare MAPEL with the SPC and ADP algorithms, which achieve close-to-optimal average performance in the general SINR regime.The comparison covers state-of-the-art centralized and distributed power-control algorithms.
  • Conclusions and Discussions: The paper identifies general utility functions, time-varying channels, and faster MAPEL variants as directions for further research.These directions include concave and non-concave utilities, while algorithmic variants could reduce convergence time and computational complexity.
Loading 0805.2675v2…