PaperlayerView exact revision on arXiv

Source-linked AI summary

Fractional Programming for Communication Systems--Part I: Power Control and Beamforming

Kaiming Shen, Wei Yu

arXiv:1802.10192v2cs.IT

TL;DR

Communication-system design often involves multiple-ratio FP problems built from several SINRs, while classical FP methods mainly address single-ratio or max-min cases. The paper introduces a quadratic transform for continuous problems, recasting them into iterative sequences of convex optimizations. Across power control, beamforming, and energy-efficiency applications, the resulting algorithms have provable convergence to stationary points, with connections to fixed-point iteration and related methods.

  • Problem

    Communication-network optimization often contains multiple SINR-based ratios, but existing FP techniques mainly handle single-ratio or max-min problems.

  • Method

    The paper introduces a quadratic transform that decouples ratio numerators and denominators through auxiliary variables and solves continuous communication problems via iterative convex optimization.

  • Results

    The proposed FP reformulations yield efficient iterative algorithms with provable convergence to stationary points for continuous communication-system optimization.

  • Takeaways & Limitations

    The approach broadens FP-based optimization to multiple-ratio continuous problems in power control, beamforming, and energy-efficiency maximization.

Abstract

from arXiv · show

This two-part paper explores the use of FP in the design and optimization of communication systems. Part I of this paper focuses on FP theory and on solving continuous problems. The main theoretical contribution is a novel quadratic transform technique for tackling the multiple-ratio concave-convex FP problem--in contrast to conventional FP techniques that mostly can only deal with the single-ratio or the max-min-ratio case. Multiple-ratio FP problems are important for the optimization of communication networks, because system-level design often involves multiple signal-to-interference-plus-noise ratio terms. This paper considers the applications of FP to solving continuous problems in communication system design, particularly for power control, beamforming, and energy efficiency maximization. These application cases illustrate that the proposed quadratic transform can greatly facilitate the optimization involving ratios by recasting the original nonconvex problem as a sequence of convex problems. This FP-based problem reformulation gives rise to an efficient iterative optimization algorithm with provable convergence to a stationary point. The paper further demonstrates close connections between the proposed FP approach and other well-known algorithms in the literature, such as the fixed-point iteration and the weighted minimum mean-square-error beamforming. The optimization of discrete problems is discussed in Part II of this paper.

I. OVERVIEW

The paper extends fractional programming to communication-system problems with multiple ratio terms, where conventional methods are mainly limited to single-ratio or max-min cases. Part I introduces a quadratic transform for continuous optimization and applies it to power control, beamforming, and energy efficiency.

  • Motivation: Multiple-ratio FP is important for communication networks because system performance often depends on multiple SINRs from interfering links.Such problems are NP-hard, and globally optimal methods require exponential running time.
  • FP Theory: The quadratic transform decouples each ratio’s numerator and denominator using auxiliary variables, converting concave-convex FP into sequential convex optimizations.The approach decouples signal and interference terms in multi-link SINR problems.
  • Power Control: For power control, the paper maximizes weighted sum rate in a nonconvex SISO cellular network using direct iterative updates and a closed-form-update method.The closed-form method is connected to fixed-point iteration.
  • Beamforming: For beamforming, the vector quadratic transform is applied to maximize weighted sum rate in a MIMO wireless cellular network.
  • Energy Efficiency: For energy efficiency, FP is nested by treating the sum-rate numerator as an inner multiple-ratio problem within the outer single-ratio objective.The objective is overall data rate divided by total power consumption.
  • Classical FP: The paper reviews classical single-ratio transforms, which decouple numerator and denominator but do not readily extend to general multiple-ratio problems.The Charnes-Cooper transform can yield a convex reformulation for concave-convex single-ratio FP, whereas its extension to sum-of-ratios problems is difficult.

B. Proposed Quadratic Transform

The quadratic transform preserves both the optimal solution and objective value while enabling multiple-ratio fractional programs to be reformulated for iterative optimization. Its key condition supports extensions to sum-of-ratios, sum-of-functions-of-ratio, and max-min-ratio problems.

  • Classic fractional-programming transforms do not readily generalize to multiple ratios because transformed objective values may differ from the original.Therefore, applying a single-ratio transform independently to each ratio does not generally preserve equivalence.
  • The quadratic transform introduces auxiliary variables and decouples each ratio’s numerator and denominator while preserving the objective value.It is motivated by Dinkelbach’s transform but adds an equivalent-objective requirement.
  • The transform is designed to satisfy four conditions: separability, equivalent solutions, equivalent objective values, and concavity in the auxiliary variable.The equivalent-objective condition is stronger than solution equivalence alone and enables convex optimization over the auxiliary variable.
  • Theorem 1 establishes the quadratic transform, and under a strengthened curvature condition its admissible form is unique up to an affine transformation in the auxiliary variable.The theorem states the transform satisfies conditions C1–C4.
  • Condition C3 enables equivalent reformulations of sum-of-ratios, sum-of-functions-of-ratio, and max-min-ratio problems.The quadratic transform can therefore be extended beyond the single-ratio setting, unlike a straightforward Dinkelbach extension.

D. Multidimensional and Complex FP

The paper extends quadratic-transform fractional programming to multidimensional complex ratios and multiple-ratio concave-convex problems. Under stated concavity, convexity, and constraint assumptions, alternating optimization converts the reformulation into convex subproblems with convergence guarantees.

  • Multidimensional and Complex FP: The multidimensional complex extension handles vector numerators and matrix denominators arising in multi-antenna communication systems.
  • Multidimensional and Complex FP: Theorem 2 establishes equivalence between the multidimensional complex FP problem and its quadratic-transform reformulation using auxiliary variables.The auxiliary variables are collected as y = {y1, · · · , yM}.
  • Concave-Convex FP: The method targets multiple-ratio concave-convex FP under concave numerators, convex denominators, and a convex constraint set.For functions-of-ratio problems, the outer functions are additionally assumed concave and nondecreasing.
  • Iterative Algorithm: Alternating updates optimize the auxiliary variables and the primal variable, with the latter obtained by solving a convex optimization problem for fixed auxiliary variables.The quadratic-transformed objective is concave in x under the stated assumptions, enabling numerical convex optimization.
  • Convergence: For concave-convex sum-of-functions-of-ratio problems, Algorithm 1 produces nondecreasing objective values and converges to a stationary point.
  • Convergence: For single-ratio and max-min-ratio concave-convex problems, the same algorithm converges to the globally optimal solution.The single-ratio result follows from pseudo-convexity, even though the original problem need not be convex.

F. Convergence Rate

For the single-ratio concave-convex problem, Dinkelbach’s transform converges faster than the quadratic transform, whose slower convergence reflects its broader multiple-ratio applicability.

  • Dinkelbach’s transform converges at a superlinear rate for the single-ratio concave-convex problem.
  • The quadratic transform can converge strictly more slowly than Dinkelbach’s transform on a single-ratio problem.
  • The quadratic transform alternates auxiliary-variable and primal-variable updates, with the latter obtained from a convex optimization.
  • Dinkelbach’s faster convergence is restricted to single-ratio problems, whereas the quadratic transform handles multiple ratios.
  • For multiple-ratio problems without guaranteed global convergence, slower convergence can allow more extensive exploration of the solution space.

III. POWER CONTROL

The paper applies quadratic-transform FP to nonconvex weighted-sum-rate power control in SISO cellular networks. The reformulation yields iterative convex subproblems that converge to stationary points and extend to broader rate-utility and multiband settings.

  • The power-control problem maximizes weighted sum rate by optimizing transmit powers under per-base-station power budgets.
  • The original weighted-sum-rate power-control problem is nonconvex, motivating an efficient method targeting a stationary point.
  • The direct FP method applies the quadratic transform to each SINR and alternates auxiliary-variable updates with convex power optimization.
  • Algorithm 2 is guaranteed to converge to a stationary point of the power-control problem.
  • The approach extends to multiple frequency bands and to nondecreasing concave rate-utility or minimum-rate objectives.

C. Closed-Form FP Approach

The closed-form FP approach reformulates power control through a Lagrangian-dual construction and quadratic transforms. It replaces numerical convex optimization with closed-form iterative updates while retaining stationary-point convergence.

  • The closed-form FP approach uses a Lagrangian-dual reformulation so each iteration can be performed with closed-form updates.
  • The reformulation introduces auxiliary variables γ and y and alternately updates them with the transmit powers.
  • The optimal γ_i equals the downlink SINR of base station i when the powers are fixed.
  • Unlike direct FP, the closed-form method is not conventional block coordinate ascent because its optimizing objective changes across updates.
  • Despite this distinction, convergence to a stationary point is established, with the detailed constructive proof deferred to Part II.

D. Connection with Fixed-Point Iteration

The closed-form FP power update can be interpreted as a fixed-point iteration with a particular choice of fixed components. Simulations compare FP with Newton and SCALE under flat- and frequency-selective fading.

  • D. Connection with Fixed-Point Iteration: Stationary-point power control is equivalent to solving the first-order condition, which motivates fixed-point updates by isolating each transmit power.
  • D. Connection with Fixed-Point Iteration: Existing fixed-point iterations do not necessarily converge, although convergence is guaranteed when resulting SINRs are sufficiently high.
  • D. Connection with Fixed-Point Iteration: The power-update portion of Algorithm 3 is a fixed-point iteration with a crucial convergence guarantee, plus projection onto the constraint set.
  • E. Numerical Example: In flat-fading simulations, closed-form FP uses the most iterations but has the lowest per-iteration cost and was fastest in the authors’ experience.
  • E. Numerical Example: Under frequency-selective fading, Newton’s heuristic projection no longer guarantees a stationary point and performs much worse in simulation.
  • E. Numerical Example: Across power-control experiments, FP approaches are competitive, while closed-form FP has lower overall complexity; all methods guarantee only stationary-point convergence.

IV. BEAMFORMING

The beamforming problem maximizes weighted sum rate over vector beamformers under per-base-station power budgets. Direct multidimensional FP decouples each SINR with auxiliary variables, yielding iterative convex optimization with stationary-point convergence.

  • Weighted sum-rate maximization over vector beamformers is a challenging nonconvex problem with transmit power budgets.
  • Direct FP applies the multidimensional quadratic transform to every SINR term.
  • For fixed auxiliary variables, optimizing the beamformers is a convex problem.
  • Algorithm 4 alternates auxiliary-variable updates with convex beamformer optimization until its objective converges.
  • The direct FP beamforming algorithm converges to a stationary point.
  • Each iteration requires numerical solution of a convex problem.

C. Multidimensional Closed-Form FP Approach

The closed-form beamforming approach reformulates the weighted sum-rate problem through a Lagrangian dual transform and multidimensional quadratic transform. It updates auxiliary variables and beamformers iteratively, with efficient power-constraint handling and a connection to WMMSE.

  • C. Multidimensional Closed-Form FP Approach: The method first converts the sum-logarithm objective to a sum-of-ratios form, then applies the multidimensional quadratic transform.
  • C. Multidimensional Closed-Form FP Approach: With beamformers fixed, each γim is updated by setting the corresponding derivative to zero.
  • C. Multidimensional Closed-Form FP Approach: Algorithm 5 cycles through Y, γ, and V updates until the objective converges.
  • C. Multidimensional Closed-Form FP Approach: The reformulation facilitates iterative optimization over beamformers and auxiliary variables.
  • C. Multidimensional Closed-Form FP Approach: The beamformer update uses a dual variable ηi for the power constraint.
  • C. Multidimensional Closed-Form FP Approach: The optimal ηi is determined efficiently by bisection search.
  • D. Numerical Example: In the numerical model, each cell has two randomly located users and two antennas at both base stations and users, with unit weights for sum-rate maximization.
  • D. Numerical Example: 470Mbps is reached within 10 iterations by direct FP, whereas closed-form FP requires 25 iterations; closed-form FP is preferred because its updates are closed form.

V. ENERGY EFFICIENCY MAXIMIZATION

The paper applies FP to energy-efficiency maximization for single-link and multiple-link systems. A nested quadratic-transform formulation makes the multiple-link beamforming subproblem convex for fixed auxiliary variables and converges to a stationary point.

  • Energy efficiency is defined as data rate divided by total power consumption, and the single-link problem is generally nonconvex.
  • For a single link, conventional Dinkelbach FP gives a globally optimal solution, while quadratic-transform updates solve a convex problem for fixed y.
  • The multiple-link setting uses multiple beamformers and receiver data rates in an energy-efficiency objective.
  • Dinkelbach’s reformulation is no longer concave in the beamformers, making fixed-y optimization numerically difficult.
  • The nested FP approach applies an outer transform to energy efficiency and an inner transform to the SINR terms.
  • The reformulation introduces y and zm as auxiliary variables for the outer and inner FP steps.
  • Algorithm 6 updates Z, y, and V, solving a convex V-subproblem when Z and y are fixed.
  • The nested FP objective is nondecreasing after each iteration and converges to a stationary point of the original problem.

C. Numerical Example

The numerical examples evaluate energy-efficiency FP under single-link and multiple-link channel models. Dinkelbach converges faster for the single link, while nested FP substantially improves multiple-link energy efficiency where Dinkelbach is unavailable.

  • The simulations use flat-fading channels, 1MHz bandwidth, 21dBm maximum transmit power, 5dBm on-power, and −100dBm background noise.
  • The single-link case uses one antenna at each endpoint and −120dB pathloss.
  • The multiple-link case has one three-antenna sender, three two-antenna receivers, Rayleigh fading, and −120dB pathloss.
  • Dinkelbach reaches optimal single-link energy efficiency in 4 iterations, compared with 8 iterations for quadratic transform.
  • The single-link convergence comparison agrees with the paper’s convergence-rate analysis.
  • More than four-fold energy-efficiency improvement is achieved after 8 iterations for the multiple-link case.
  • Dinkelbach’s transform is not applicable to the multiple-link scenario.
  • Part I uses quadratic-transform FP for continuous power-control, beamforming, and energy-efficiency problems, with iterative stationary-point convergence; discrete problems are deferred to Part II.

APPENDIX A PROOF OF THEOREM 1

The proof characterizes the general form of g(x, y) that satisfies the strengthened conditions and yields max_y g(x, y) = A/B. It derives necessity by examining limiting and zero cases, then verifies sufficiency for the resulting parameterization.

  • Necessity: The strengthened condition that ∂2g/∂y2 be independent of y constrains g(x, y) to a specific functional form.The proof begins by deriving this form under the strengthened C4 condition and C1.
  • Necessity: The proof evaluates max_y g(x, y) in closed form and requires it to equal A/B, with ∂2g(x, y)/∂y2 nonzero to satisfy C3.If the second derivative were zero, the maximum would be unbounded, violating C3.
  • Quadratic transform: A proposed parameter choice recovers the quadratic transform (7), while the proof establishes a more general form (8) as the unique solution satisfying the conditions.The choice α0 = 0, β0 = 0, α1 = 2, β1 = 0, α2 = 0, β2 = 1, f(A) = √A, and h(B) = B yields (7).
  • Boundary cases: Setting A = 0 forces the maximized expression to vanish for every B, while taking B → 0+ forces it to diverge for nonzero A.These cases impose constraints on the terms depending only on B and only on A, respectively.
  • Sufficiency: Substituting the resulting identities gives the summarized form of g(x, y), which can be rewritten as (8) using t1 = s1α1/2 and t2 = s1α0/2.The final verification states that this form satisfies the strengthened C1-C4 when t1 ≠ 0, proving necessity and sufficiency.
Loading 1802.10192v2…