# Percentile Optimization in Wireless Networks—
Part I: Power Control for Max-Min-Rate to Sum-Rate Maximization (and
Everything in Between)

Ahmad Ali Khan, Raviraj S. Adve Raviraj Adve is with the Edward S. Rogers Sr.
Department of Electrical and Computer Engineering, University of Toronto,
Toronto, Ontario, M5S 3G4, e-mail<EMAIL_ADDRESS>Ahmad Ali Khan is
with Ericsson R&D, Ottawa, Ontario, K2K 2V6, email<EMAIL_ADDRESS>The authors would like to acknowledge the support of Ericsson Canada.

###### Abstract

Improving throughput for cell-edge users through coordinated resource
allocation has been a long-standing driver of research in wireless cellular
networks. While a variety of wireless resource management problems focus on
sum utility, max-min utility and proportional fair utility, these formulations
do not explicitly cater to cell-edge users and can, in fact, be
disadvantageous to them. In this two-part paper series, we introduce a new
class of optimization problems called percentile programs, which allow us to
explicitly formulate problems that target lower-percentile throughput
optimization for cell-edge users. Part I focuses on the class of least-
percentile throughput maximization through power control. This class subsumes
the well-known max-min and max-sum-rate optimization problems as special
cases. Apart from these two extremes, we show that least-percentile rate
programs are non-convex, non-smooth and strongly NP-hard in general for
multiuser interference networks, making optimization extremely challenging. We
propose cyclic maximization algorithms that transform the original problems
into equivalent block-concave forms, thereby enabling guaranteed convergence
to stationary points. Comparisons with state-of-the-art optimization
algorithms such as successive convex approximation and sequential quadratic
programming reveal that our proposed algorithms achieve superior performance
while computing solutions orders of magnitude faster.

###### Index Terms:

Percentile optimization, cell-edge, power control, cyclic maximization, least-
percentile rate, greatest-percentile.

##  I Introduction

###  I-A Background and Overview

Coordinated resource allocation through optimization is an area of
considerable research interest due to its potential for improving service in
wireless cellular networks [1, 2, 3]. Due to the randomness and inherent
physical characteristics of the wireless propagation medium, however, there is
significant variation in the throughput, energy efficiency and power
consumption achieved by different users across a cellular network [4].  In
particular, users located close to the boundaries of cells (commonly referred
to as cell-edge users) consistently experience poor received signal strength
from their serving base station (BS) as well as strong interference from
neighboring cells [5, 6, 4], as illustrated in Figure 1. This leads to poor
achieved data rates for cell-edge users manifested in the lower percentiles
(e.g., $5^{\mathrm{th}}$\- and $10^{\mathrm{th}}$-percentile rates). Improving
these lower-percentile rates has been identified as a crucial requirement for
current and next-generation cellular networks to enhance access as well as
enabling new applications [7, 8, 9]. For example, the 3GPP industrial
standards for future wireless cellular networks call for a 3$\times$
improvement in $5^{\mathrm{th}}$-percentile rates as compared to the current
5G levels [7]; similar targets have been proposed in joint industry-academic
studies carried out by the 5G Public Private Partnership (5GPPP) [8].
Likewise, a recent work by a major cellular network infrastructure provider
suggests a target of 5 Gbps for the $5^{\mathrm{th}}$-percentile rate in 6G
networks [10]. As such, numerous research papers have been published by
equipment vendors [11, 10] exploring how increased physical resources, such as
number of transmission antennas and orthogonal frequency bands, can help
achieve these targets for lower-percentile rates.

Despite the clear necessity of improving lower-percentile service, prior
research works have, at best, proposed indirect techniques for tackling this
goal. Physical-layer techniques like fractional frequency reuse [12],
heterogeneous architectures [13] and densification [14] have been explored in
prior works with the aim of improving lower-percentile cell-edge rates. While
effective, these approaches are nonetheless heuristic in nature as they do not
directly address the mathematical problem of optimizing throughput for a
desired percentile. Additionally, these techniques exhibit various undesirable
characteristics; fractional frequency reuse schemes, for example, are
bandwidth-inefficient since the frequency allocations are static within each
cell, leading to under-utilization of the available spectrum. Additionally,
there is no optimal method to assign the frequency tones among different
users. It is critical to recognize that none of these aforementioned methods
are based on signal processing techniques.

Figure 1: A typical cell-edge user in a wireless cellular network.

In contrast to industrial targets, the $10^{\mathrm{th}}$-percentile
throughput is widely used as a measure of cell-edge rate in most academic
works including, but not limited to, [15, 16, 17]. However, prior research
works have come up with indirect ways to optimize this metric via signal
processing techniques like beamforming and power control. This is usually
accomplished by solving a network utility maximization problem, with the most
common choices of network utility function being sum-rate [18, 19], minimum
rate [18, 20, 21] and proportional fair (PF) (usually approximated as weighted
sum-rate (WSR)) [22, 23, 24, 5]; however, none of these utilities explicitly
targets cell-edge users.

Sum-rate maximization is well-known to be unfair to edge users: as noted in
[25], transmitting to edge users creates interference for cell-center users,
driving the network throughput down. Hence, optimal solutions to the sum-rate
maximization problem assign little to no power to these users [15]. In
contrast, the minimum rate caters to the weakest edge user in the network
resulting in a large rate penalty for most other users. This phenomenon makes
it an unsuitable utility for large networks: as noted by [26], the minimum
achievable rate in a multiuser network asymptotically approaches zero as the
number of users grows.

Sum-log-average-rate optimization (and the corresponding WSR maximization
problem) on the other hand, is proportionally fair (PF) and aims to serve all
users. Nevertheless, we emphasize that WSR maximization does not optimize the
edge user rates; essentially, this is an ad-hoc choice of metric. Hence, any
comparison of edge rates achieved by different WSR maximization algorithms,
such as the weighted minimum mean-squared error (WMMSE) scheme proposed in
[22], is not mathematically rigorous. Schemes that achieve higher sum-log-
utility do not necessarily achieve higher edge rates and vice versa; as a
specific example, the approach presented in [24] improves sum-log-utility over
the WMMSE algorithm, but results in lower $10^{\mathrm{th}}$-percentile rates.

Alternative utilities like $\alpha$-fair power allocation [27] and Jain’s
fairness index [28] have also been proposed to prioritize serving cell-edge
users, but as observed in [29], such fairness measures are not physically
interpretable as we cannot distinguish whether one measure is ‘better’ than
another. Enforcing constraints on individual throughputs is also a similar
heuristic to enable fairer resource allocation [30, 31].

Finally, we note that cell-edge throughput optimization has been attempted
indirectly under the framework of stochastic analysis [32, 6]. A resource
allocation scheme is chosen and closed-form expressions for distributions of
the desired metric are obtained using stochastic geometry. The resource
allocation parameters that yield the highest cell-edge throughput for a
desired percentile are then empirically chosen [32, 6]. It should be
emphasized, however, that such schemes enable analysis but not direct
optimization of cell-edge throughput as the power control and precoding
strategies are essentially pre-determined.

In summary, despite the crucial importance of throughput optimization at
desired percentiles for future generations of wireless networks, none of the
prior resource allocation works (including the aforementioned FP [15] and
WMMSE methods [22]) have tackled this class of problems. Therefore, we believe
that there is a clear need to study these problems as a result of their
practical significance as well as the lack of a rigorous theoretical framework
to solve them in the available literature. Motivated by the practical
significance, theoretical challenges, and the lack of a coherent framework,
this two-part paper series addresses this critical gap by formulating
percentile programs in wireless networks and showcases iterative optimization
methods to solve them effectively.

###  I-B Contributions of Part I

In this paper, we introduce a new class of optimization problem with specific
reference to resource allocation problems in communications, which we
henceforth term as percentile programs. Part I of this two-paper series
focuses on sum-percentile rate optimization problems. Specifically, the
contributions of this part can be summarized as follows:

  * •

Problem formulation: We develop an explicit problem formulation for the
maximization of sum-least-percentile rate via power control for a multicell,
multiuser single-input, single-output (MU-SISO) network for any choice of
percentile. The proposed formulation enables us to directly optimize the
throughput for any choice of percentile; to the best of our knowledge, our
work is the first of its kind to directly tackle this class of problems.

  * •

Optimizing cell-edge rates: This formulation directly targets cell-edge
optimization by targeting lower percentiles, e.g. $5^{\mathrm{th}}$-percentile
rate, in accordance with the industrial targets for next-generation networks
[7, 8, 9, 10]. Additionally, we show that the choice of the percentile level
allows us to control the tradeoff between favoring cell-center (i.e., sum-
rate) users or cell-edge users.

  * •

Complexity analysis: Through a polynomial-time reduction from the maximum
independent set problem, we demonstrate that the power-control sum-percentile
rate optimization problem is strongly NP-hard, in general, for all percentiles
strictly greater than the minimum percentile. In this regard, this work is the
first of its kind to generalize the previous results that were restricted to
the max-min-rate and sum-rate problems [18].

  * •

Cyclic optimization to stationarity: We transform the original sum-least-
percentile utility into equivalent block-concave forms, yielding convenient
cyclic maximization algorithms. Furthermore, we demonstrate that the proposed
algorithms belong to the broader class of minorization-maximization
algorithms, and present proofs of non-decreasing convergence to stationary
points of the original problem.

###  I-C Notation

Prior to proceeding further, we define some notation used in this paper.
$\mathbb{R}$, ${\mathbb{R}}_{{+}}$ and ${\mathbb{R}}_{{++}}$ represent the set
of real numbers, non-negative real numbers, and positive numbers respectively.
Similarly, we use $\mathbb{Z}$, ${\mathbb{Z}}_{{+}}$ and ${\mathbb{Z}}_{{++}}$
to denote the set of integers, non-negative integers, and positive integers
respectively. We denote scalars using lowercase letters (e.g., $x$), vectors
using lowercase boldface (e.g., $\mathbf{x}$), matrices using uppercase
boldface (e.g., $\mathbf{X}$) and sets using script typeface (e.g.,
$\mathcal{X}$). The optimal value of a variable is denoted by a $*$ sign in
superscript (e.g., $x^{*}$, $\mathbf{x}^{*}$, $\mathbf{X}^{*}$). We denote the
all-ones and all-zeros vectors by $\mathbf{1}$ and $\mathbf{0}$, respectively,
with dimension determined by the context. The operator $\left|\cdot\right|$
denotes the absolute value when applied to a scalar and cardinality when
applied to a set.

For a vector $\mathbf{x}\in\mathbb{R}^{n}$, we denote by
$\mathbf{x}^{\downarrow}$ the vector with identical components, but sorted in
descending order; likewise, we denote by $\mathbf{x}^{\uparrow}$ the vector
with identical components but sorted in ascending order. Hence,
$x_{i}^{\downarrow}$ ($x_{i}^{\uparrow}$) then denotes the $i^{\mathrm{th}}$
entry in $\mathbf{x}^{\downarrow}$ ($\mathbf{x}^{\uparrow}$), i.e., the
$i^{\mathrm{th}}$ largest (smallest) entry in $\mathbf{x}$. The number of ways
of picking $k$ unordered outcomes from $n$ possibilities (i.e., the binomial
coefficient) is denoted by ${}_{n}{C}_{k}$.

###  I-D Organization

Part I is organized as follows:

  * •

In Section II, we define sum-percentile functions and discuss key properties
needed to construct the subsequent optimization problems.

  * •

We formulate and solve the sum-least percentile throughput optimization
problem for the special setting of parallel Gaussian channels in Section III.

  * •

Section IV deals with the more realistic setting of an interference-limited
multicell, multiuser network. Finally, we draw conclusions in Section V.

To maintain consistency, Sections III and IV follow an identical order: we
first introduce the problem formulation, then describe the proposed
approach(es) and finally present the numerical results at the end of section.
Thus, the numerical results for the simplified parallel Gaussian channel
setting are given in Section III-C while those for the more realistic
interference-limited cellular network are given in Section IV-C.

Part II deals with the more general setting of beamforming for a multiuser
multiple-input multiple-output (MIMO) network, as well as the construction of
novel utility functions by composition, and ergodic percentile throughput
optimization.

##  II Sum-Percentile Functions and Their Properties

###  II-A Definitions

We begin by defining two classes of sum-percentile utility functions. Given an
integer $K\in\mathbb{Z_{++}}$ and a percentile $q\in\left(0,100\right]$, we
define the corresponding percentile number $K_{q}$ as

$K_{q}=\mathrm{min}\left\\{k\in\mathbb{Z_{++}}\left|\frac{100k}{K}\geq
q\right.\right\\}$

Given the vector $\mathbf{x}=[x_{1},\ldots,x_{K}]^{T}$, we define the sum-
greatest-$q^{\mathrm{th}}$-percentile (SGqP) utility function
$F_{K_{q}}\left(\mathbf{x}\right):\mathbb{R}^{K}\mapsto\mathbb{R}$ as the sum
of the $K_{q}$ largest components of $\mathbf{x}$, i.e.,

$F_{K_{q}}\left(\mathbf{x}\right)=\sum_{i=1}^{K_{q}}x_{i}^{\downarrow}$ (1)

Similarly, we define the sum-least-$q^{\mathrm{th}}$-percentile (SLqP) utility
function $f_{K_{q}}\left(\mathbf{x}\right):\mathbb{R}^{K}\mapsto\mathbb{R}$ as
the sum of the smallest $K_{q}$ components of $\mathbf{x}$, i.e.,

$f_{K_{q}}\left(\mathbf{x}\right)=\sum_{i=1}^{K_{q}}x_{i}^{\uparrow}$ (2)

We shall often find it convenient to explicitly indicate the components of a
vector when dealing with SLqP and SGqP functions; thus, throughout this paper,
$f_{K_{q}}\left(\mathbf{x}\right)$ and
$f_{K_{q}}\left(x_{1},\ldots,x_{n}\right)$ are equivalent.

###  II-B Properties

We now state some key properties of the SLqP and SGqP utility functions. The
latter class of functions is dealt with only in Part II and may be safely
skipped for readers wishing to focus on the power control problems examined in
Part I.

######  Property 1.

The SGqP (resp. SLqP) utility function is convex (resp. concave) for all
values of $q\in\left(0,100\right]$.

###### Proof.

Observe that we can express the SGqP utility function in an alternative form
as follows. We define the following set:

$\mathcal{A}_{K_{q}}\coloneqq\left\\{\left.\mathbf{a}\in\left\\{0,1\right\\}^{K}\right|\mathbf{1}^{T}\mathbf{a}=K_{q}\right\\}$
(3)

In other words, $\mathcal{A}_{K_{q}}$ is the set of binary vectors of length
$K$ with Hamming weight of $K_{q}$; this set has cardinality
${}_{K}C_{K_{q}}$. Then the SGqP utility function can be equivalently
expressed as

$F_{K_{q}}\left(\mathbf{x}\right)=\underset{\mathbf{a}\in\mathcal{A}_{K_{q}}}{\mathrm{max}}\hskip
5.0pt\mathbf{a}^{T}\mathbf{x}$ (4)

which is the pointwise maximum over a set of functions that are linear in
$\mathbf{x}$, and is thus convex [33]. Next, observe that we can similarly
write the SLqP utility function equivalently as:

$f_{K_{q}}\left(\mathbf{x}\right)=\mathbf{1}^{T}\mathbf{x}-F_{K-K_{q}}\left(\mathbf{x}\right)$
(5)

which is the difference of a linear and a convex function, and thus concave
overall in $\mathbf{x}$ [33]. ∎

######  Property 2.

The SGqP and SLqP utility functions are non-decreasing in each component.

###### Proof.

For a fixed value of $q$, the SGqP (resp. SLqP) utility function is the
pointwise maximum (resp. pointwise minimum) of non-decreasing linear functions
and is therefore also non-decreasing. ∎

######  Property 3.

The SGqP utility function contains as special cases the sum and maximum
utility functions.

###### Proof.

Observe that if $q=100$, we have $K=K_{q}$, in which case the SGqP utility
function simply becomes the sum of all components of the vector:

$F_{K}\left(\mathbf{x}\right)=\sum_{i=1}^{K}x_{i}^{\downarrow}=\mathbf{1}^{T}\mathbf{x}^{\downarrow}=\mathbf{1}^{T}\mathbf{x}$

Similarly, if we set $q=100/K$, we have $K_{q}=1$ and

$F_{1}\left(\mathbf{x}\right)=x_{1}^{\downarrow}=\underset{i=1,\ldots,K}{\mathrm{max}}x_{i}$

∎

######  Property 4.

The SLqP utility function contains as special cases the sum and minimum
utility functions.

###### Proof.

This property follows from similar reasoning to Property 3; we have

$f_{K}\left(\mathbf{x}\right)=\sum_{i=1}^{K}x_{i}^{\uparrow}=\mathbf{1}^{T}\mathbf{x}^{\uparrow}=\mathbf{1}^{T}\mathbf{x}$
$f_{1}\left(\mathbf{x}\right)=x_{1}^{\uparrow}=\underset{i=1,\ldots,K}{\mathrm{min}}x_{i}$

∎

######  Property 5.

The SGqP and SLqP utility functions are non-smooth for $K_{q}\neq{K}$.

###### Proof.

This property is readily apparent from the form of the SGqP utility function
in (4); since it is the pointwise maximum of ${}_{K}C_{K_{q}}$ distinct linear
functions, it follows that the function, although continuous, is not
necessarily smooth [34].∎

We note that the $q=100$ case is an exception to Property 5: for $K_{q}=K$,
both the SGqP and SLqP functions are equivalent to the sum utility function,
which is smooth.

######  Property 6.

The SGqP and SLqP functions are connected through the following symmetry
property:

$F_{K_{q}}\left(\mathbf{x}\right)=-f_{K_{q}}\left(\mathbf{-x}\right)$

###### Proof.

Following the definition of $\mathcal{A}_{K_{q}}$ in (3), we observe that

$F_{K_{q}}\left(-\mathbf{y}\right)=\underset{\mathbf{a}\in\mathcal{A}_{K_{q}}}{\mathrm{max}}\hskip
5.0pt-\mathbf{a}^{T}\mathbf{y}=-\underset{\mathbf{a}\in\mathcal{A}_{K_{q}}}{\mathrm{min}}\hskip
5.0pt\mathbf{a}^{T}\mathbf{y}=-f_{K_{q}}\left(\mathbf{y}\right)$

The property follows from the change of variables $\mathbf{y}=-\mathbf{x}$. ∎

######  Property 7.

For all $\mathbf{x}\in\mathbb{R}_{+}^{K}$, the SGqP and SLqP functions are
ordered by the percentile number: for $K_{q_{1}}<K_{{q_{2}}}$, we have
$f_{K_{q_{1}}}\left(\mathbf{x}\right)\leq
f_{K_{{q_{2}}}}\left(\mathbf{x}\right)$ and
$F_{K_{q_{1}}}\left(\mathbf{x}\right)\leq
F_{K_{{q_{2}}}}\left(\mathbf{x}\right)$.

###### Proof.

We illustrate this property for the SLqP function; the proof for the SGqP
function is similar. Suppose that $K_{q_{1}}+i=K_{{q_{2}}}$ where
$i\in\mathbb{Z_{++}}$. Then, from the definition of the SLqP function in (2)
we can write:

$f_{K_{q_{2}}}\left(\mathbf{x}\right)=f_{K_{q_{1}}}\left(\mathbf{x}\right)+x_{K_{q_{1}}+1}^{\uparrow}+\ldots+x_{K_{q_{1}}+i}^{\uparrow}$

The property then follows from the fact that $x_{k}^{\uparrow}\geq{0}$ for
$k=1,\ldots,K$. ∎

To summarize, the SGqP and SLqP functions are non-smooth utilities. Due to
their respective convexity and concavity, we can formulate minimization
problems for the former and maximization problems for the latter utility.

##  III Optimization for Parallel Gaussian Channels

###  III-A Problem Formulation

We are now ready to formally introduce the class of sum-
least-$q^{\mathrm{th}}$-percentile rate maximization problems. We begin by
considering the problem of SLqP rate maximization under a interference-free
parallel channel model with unity channel gains. We study this setting for two
key reasons. First, percentile rate problems have never been studied in this
particular setting in the prior literature (other than the special max-min-
rate and sum-rate problems [18]). Second, the problem is convex in this
simplified setting, enabling derivation of many useful properties of the
optimal solution structure that are not possible in the more general non-
convex and NP-hard interference-limited scenario for real-world cellular
networks.

We assume a total of $K$ transmitter-receiver pairs; for convenience, we refer
to each pair as a user throughout this paper. Further, we denote the transmit
power of user $k$ as $p_{k}$ and receiver additive white Gaussian noise (AWGN)
power by $z_{k}$; the former is collected in the vector $\mathbf{p}$ while the
latter is collected in the vector $\mathbf{z}$ for notational clarity. For
simplicity of notation and without loss of generality, we subsequently assume
that the users are ordered according to descending noise powers, i.e.,
$z_{1}\geq{z_{2}}\geq{\ldots}\geq{z_{K}}$. In keeping with prior resource
allocation works, we assume that these noise powers are known [15, 16].
Assuming parallel channels with a gain of unity for all users, it follows that
the rate achievable by user $k$ is given by

$r_{k}\left(\mathbf{p}\right)=\log\left(1+\frac{p_{k}}{z_{k}}\right)$ (6)

Our aim can be concisely expressed as follows: under a sum-power constraint of
$P_{T}$ in the given setting, how should the powers be allocated to maximize
the sum of the smallest $K_{q}$ rates in the network? The SLqP rate
optimization problem that encapsulates this goal can be expressed as follows:

$\displaystyle\underset{\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad
f_{K_{q}}\left(r_{1}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)\hskip
20.00003pt\hskip 40.00006pt$ (7a) $\displaystyle\mathrm{subject\,to}\quad
p_{k}\geq 0,\,k=1,\ldots,K\hskip 73.00014pt$ (7b)
$\displaystyle\sum_{k=1}^{K}p_{k}\leq{P}_{\mathrm{max}}\hskip 103.00018pt$
(7c)

Note that the order of the users here does not matter to the SlqP utility
function.

######  Remark 1.

The percentile program in (7) is equivalent to maximization of the sum-rate
when $K_{q}=K$ and maximization of the minimum rate when $K_{q}=1$.

###### Proof.

This follows as a direct consequence of Property 4. ∎

######  Remark 2.

Problem (7) is a convex program.

###### Proof.

The convexity can be established using the composition rule, described in
detail in [33]. Consider a function $h:\mathbb{R}^{K}\mapsto\mathbb{R}$, and a
sequence of functions $g_{k}:\mathbb{R}^{N}\mapsto\mathbb{R};\hskip
3.00003ptk=1,\ldots,K$. Next, define the following composition:

$h\left(g_{1}\left(\mathbf{x}\right),g_{2}\left(\mathbf{x}\right),\ldots,g_{K}\left(\mathbf{x}\right)\right):\mathbb{R}^{N}\mapsto\mathbb{R}$
(8)

This composition is concave in $\mathbf{x}$ if the following conditions are
satisfied [33]:

  * •

$h$ is concave and non-decreasing in each argument.

  * •

Each of the functions $g_{k}:\mathbb{R}^{N}\mapsto\mathbb{R};\hskip
3.00003ptk=1,\ldots,K$ is concave in $\mathbf{x}$.

We apply this rule to Problem (7) as follows. First, we observe that the term
inside the logarithm, $1+\frac{p_{k}}{z_{k}}$, is obviously linear (and hence
concave) in $\mathbf{p}$. The logarithm function is concave and non-
decreasing, hence it follows that
$\mathrm{log}\left(1+\frac{p_{k}}{z_{k}}\right)$ is also concave in the
powers. Thus, the functions $r_{k}\left(\mathbf{p}\right);i=1,\ldots,K$ are
all concave in $\mathbf{p}$.

As established in Property 2, the SLqP utility function is non-decreasing in
each component. Furthermore, as shown in Property 1, it is also concave, since
it is the pointwise minimum of a set of concave functions (which is also known
to be concave according to [33]).

Identifying $f_{K_{q}}$ as $h$, and $r_{k}$ as $g_{k}$ from 8, the concavity
of the objective function in 7a then follows straightforwardly. Since we are
maximizing a concave function (subject to convex constraints), it follows that
Problem (7) is indeed a convex program. ∎

######  Remark 3.

Denote by $f_{K_{q},\mathrm{opt}}$ the optimal objective value of Problem (7).
Then the optimal values are ordered according to the percentile number: if
$K_{q_{1}}<K_{{q_{2}}}$ then we must have $f_{K_{q_{1}},\mathrm{opt}}\leq
f_{K_{{q_{2}}},\mathrm{opt}}$.

###### Proof.

Let $\mathcal{R}\left(\mathbf{z},P_{T}\right)$ denote the set of $K$-tuples of
achievable rates for all users given $\mathbf{z}$ and $P_{T}$, i.e.,

$\mathcal{R}\left(\mathbf{z},P_{T}\right)=\left\\{\left(r_{1}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)\left|\begin{array}[]{c}\sum_{k=1}^{K}p_{k}\leq
P_{T},\\\ p_{k}\geq 0,k=1,\ldots,K\end{array}\right.\right\\}$

Then from Property 7, it follows that we must have

$\underset{\left(r_{1}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)\in\mathcal{R}\left(\mathbf{z},P_{T}\right)}{\mathrm{max}}\quad
f_{K_{q_{1}}}\left(r_{1}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)\\\
\leq\underset{\left(r_{1}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)\in\mathcal{R}\left(\mathbf{z},P_{T}\right)}{\mathrm{max}}\quad
f_{K_{{q_{2}}}}\left(r_{1}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)$
(9)

which yields the desired result. ∎

As a special case, we note that this inequality implies that the optimal sum-
rate should be greater than or equal to the optimal min-rate; this subsumes
the prior results presented in [18].

######  Remark 4.

Denote by $r_{k,\mathrm{opt}}$ the rate achieved by the $k^{\mathrm{th}}$ user
in the optimal solution for the problem in (7). Then we must have
$r_{K_{q},opt}=r_{K_{q}+1,opt}=,\ldots,=r_{K,opt}$.

###### Proof.

This remark follows by contradiction. Suppose we are given an optimal solution
with $r_{k,\mathrm{opt}}>r_{K_{q},\mathrm{opt}}$ for some
$k\in\left\\{K_{q}+1,K_{q}+2,\ldots,K\right\\}$. Then we can improve the
objective by lowering $p_{k}$ and correspondingly increasing $p_{K_{q}}$ up
until user $K_{q}$ achieves an identical rate to user $k$, thereby
contradicting the optimality of the solution. Thus, in the optimal solution,
the $K-K_{q}+1$ highest achieved rates must be identical.  ∎

A well-established illustration of the preceding remark is that the max-min-
rate problem (i.e. $q=100/K$) leads to equal rates for all users.

###  III-B Solution Techniques and Implementation

Having established the convexity of Problem (7), we note that there are a
number of ways to numerically solve it. One method is to utilize the
subgradient technique, described in detail in [35]; with decaying step sizes,
the method is guaranteed to converge to the optimal solution. Alternatively,
an easier way is to utilize the CVX package, which includes the SLqP and SGqP
utilities in its standard library as the `sum_smallest(x,k)` and
`sum_largest(x,k)` functions respectively. The package can then be utilized to
numerically solve Problem (7) using the standard interior-point methods [36].

###  III-C Numerical Results

To better understand how the optimal solution changes for different values of
the percentile parameter $q$, we construct a sample network with $K=6$ users,
total power $P_{\mathrm{max}}=10$, and the following AWGN noise powers:

$\mathbf{z}=\left[0.1,\,0.05,\,250.1,\,200.4,\,5.4,\,3.7\right]^{T}$

Figure 2: Achieved rates for optimal solutions to the parallel channel SLqP
rate optimization problem for different values of $q$.

Figure 2 illustrates the rates achieved by users corresponding to the optimal
solution of Problem (7), obtained using the CVX convex solver, for $q=100$
(sum-rate), $50$ ($50^{\mathrm{th}}$ percentile) and $16.\overline{6}$
(minimum rate) respectively. In particular, the $50^{\mathrm{th}}$ percentile
setting maximizes the rates of the worst half (i.e., 3 out of 6) users. We
observe that the achieved rates vary significantly depending upon the
percentile we choose to optimize. For the max-sum-rate problem, Users 1 and 2
achieve extremely high rates but this comes at the expense of zero and near-
zero rates achieved by User 3 and User 4 respectively due to their high
receiver noise powers. In contrast, for the max-min-rate problem, as expected
from Property 4, all users achieve equal rates. This comes at the cost of
considerably reduced rates for Users 1 and 2.

On the other hand, the $50^{\mathrm{th}}$ percentile SLqP rate optimization
problem effects a favorable compromise: Users 3 and 4 achieve significantly
improved rates compared to the max-sum-rate setting while the rates achieved
by Users 1 and 2 are not curtailed as drastically as in the max-min-rate
formulation. In moving from the $50^{\mathrm{th}}$ percentile problem to the
max-min-rate problem, the rates achieved by Users 3 and 4 improve by only
$73.6\%$ and $26.8\%$ respectively yet this is achieved at the expense of a
$70.8\%$ reduction in the rates for Users 1, 2, 5, and 6.

These results illustrate a fundamental property of the SLqP rate utility:
higher values of $q$ favor users with better transmission conditions;
conversely, lower values of $q$ favor weaker users. Consequently, the value of
$q$ allows us to control the tradeoff between allocating resources to either
the weakest or strongest users in the network. The max-sum-rate and max-min-
rate optimization problems are clearly the extreme endpoints of the class of
SLqP rate optimization problems, and as such, neither may be desirable in
terms of the compromises they give rise to by either favoring the strongest or
weakest users in the network.

We also note that for the given example, we have $f_{6,\mathrm{opt}}=24.4$,
$f_{3,\mathrm{opt}}=5.52$ and $f_{1,\mathrm{opt}}=1.15$; the ordering is as
expected from Remark 3. The property from Remark 4 also holds; as expected,
for $q=50$, the $(K-K_{q}+1=4)$ largest rates are identical.

These results also illustrate that there is no inherent optimum choice of
percentile. Ultimately, the choice of this parameter is up to the network
operators; for instance, if they wish to maximize sum-rate (and favour the
cell-centre users), they would set $q=100$. As discussed earlier, however, the
main focus of our work is to help improve cell-edge service to enable new
applications [7] which is emphasized by selecting lower percentiles (e.g.,
$q=5$ or $q=10$).

###  III-D Least-$q^{\mathrm{th}}$-Percentile (LqP) Rate Optimization

At this juncture, it is natural to question why we would choose to optimize
the sum of the smallest $K_{q}$ rates rather than the $K_{q}^{\mathrm{th}}$
smallest rate (which we shall henceforth refer to as the
least-$q^{\mathrm{th}}$-percentile (LqP) rate). It turns out that the optimal
solution to the LqP rate maximization problem has undesirable properties which
makes it unsuitable for use in the context of improving service for cell-edge
users.

Observing that the $K_{q}^{\mathrm{th}}$ element in a vector can be written as
the difference between the sum of the smallest $K_{q}$ elements and the sum of
the smallest $K_{q}-1$ elements, it follows that the LqP rate maximization
problem is given by

$\displaystyle\begin{split}\underset{\mathbf{p}}{\mathrm{maximize}}\quad
f_{K_{q}}\left(r_{1}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)\hskip
70.0001pt\\\
-f_{K_{q}-1}\left(r_{1}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)\hskip
30.00005pt\end{split}$ (10a)
$\displaystyle\begin{split}\mathrm{subject\,to}\quad p_{k}\geq
0,\,k=1,\ldots,K\hskip 3.00003pt\end{split}$ (10b)
$\displaystyle\begin{split}\hskip
52.00005pt\sum_{k=1}^{K}p_{k}\leq{P}_{\mathrm{max}}\end{split}$ (10c)

######  Remark 5.

Denote by $r_{k,\mathrm{opt}}$ the rate achieved by the $k^{\mathrm{th}}$ user
in the optimal solution for the problem in (10). Then we must have
$r_{1,opt}=r_{2,opt}=,\ldots,=r_{K_{q}-1,opt}=0$.

###### Proof.

Suppose that we are given an optimal solution to Problem (10) in which
$r_{k,opt}\neq{0}$ for some user ${k\in\left\\{1,2,\ldots,K_{q}-1\right\\}}$
(and hence the power for this user, $p_{k}$, is non-zero). Since the LqP rate
in (10a), corresponding to the rate achieved by user $K_{q}$, does not depend
on the rates achieved by users $K_{q}-1,\ldots,1$, it can always be improved
by increasing $p_{K_{q}}$ by $p_{k}$ and setting user $k$’s power to zero.
Note that this change ensures that the sum-power constraint in (10c) is
respected. Thus, we conclude that the optimal solution to Problem (10) would
assign zero powers to the $K_{q}-1$ weakest users. ∎

We note that while the LqP utility function is non-concave for $K_{q}\neq{K}$
(since it is the difference of two concave functions), Remark 5 allows us to
straightforwardly derive the optimal solution for Problem (10).

######  Remark 6.

The optimal solution to Problem (10) can be found by solving the following
max-min-rate problem:

$\displaystyle\underset{\mathbf{p}}{\mathrm{maximize}}\quad
f_{1}\left(r_{K_{q}}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)\hskip
56.00014pt$ (11a) $\displaystyle\mathrm{subject\,to}\quad p_{k}\geq
0,\,k=1,\ldots,K\hskip 69.00003pt$ (11b)
$\displaystyle\sum_{k=1}^{K}p_{k}\leq{P}_{\mathrm{max}}\hskip 99.00008pt$
(11c)

###### Proof.

From Remark 5, it follows that since the rates achieved by users
$1,\ldots,K_{q}-1$ are zero in the optimal solution, the LqP objective in
(10a) is equivalent to the smallest rate achieved among the rates achieved
among the remaining users $K_{q},K_{q}+1,\ldots,K$. ∎

This assignment of zero rates to $K_{q}-1$ users makes the maximization of LqP
rate utility undesirable. This result also holds true in the wireless cellular
networks we consider in Section IV, since transmitting to users below the
$q^{\mathrm{th}}$-percentile would lead to interference, thereby decreasing
the LqP objective function value. We henceforth focus on SLqP-rate problems.

##  IV Short-Term Sum-Percentile Rate Optimization

###  IV-A Problem Formulation

We are now ready to tackle the power control problem for SLqP rate
optimization in the more realistic setting of an interference-limited network
which models real-world cellular networks. Unlike the parallel Gaussian
channel setting, the problem is now no longer convex, necessitating the
development of a distinct algorithmic framework to solve it effectively.

We consider a network with $K$ interfering single-antenna users with the
channel from the transmitter of user $j$ to the receiver of user $k$ denoted
by $h_{j\rightarrow k}$. Furthermore, the transmit power and AWGN receiver
noise power for user $k$ are denoted by $p_{k}$ and ${\sigma}^{2}$
respectively. It follows that the rate achievable by user $k$ is given by

$r_{k}\left(\mathbf{p}\right)=\mathrm{log}\left(1+\frac{p_{k}\left|h_{k\rightarrow
k}\right|^{2}}{\sum_{j\neq k}p_{j}\left|h_{j\rightarrow
k}\right|^{2}+{\sigma}^{2}}\right)$ (12)

Accordingly, the SLqP rate optimization problem for the $n^{\mathrm{th}}$ time
slot can be expressed as:

$\displaystyle\underset{\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad
f_{K_{q}}\left(r_{1}\left(\mathbf{p}\right),\ldots,r_{K}\left(\mathbf{p}\right)\right)\hskip
25.50006pt$ (13a) $\displaystyle\mathrm{subject\,to}\quad 0\leq p_{k}\leq
P_{\mathrm{max}},\,k=1,\ldots,K\hskip 3.00003pt$ (13b)

where $P_{T}$ denotes the maximum per-link power constraint.

As with the parallel Gaussian setting, this problem formulation allows us to
flexibly control the tradeoff between cell-centre and cell-edge users in
wireless communication networks. In particular, to target the cell-edge users,
we can choose smaller values of $q$. For example, with $q=5$ the problem in
(13) optimizes the $5^{\mathrm{th}}$-percentile throughput in a wireless
cellular network. Therefore, this formulation achieves the practical goal of
improving data rates for cell-edge users in accordance with the 3GPP and other
targets for 6G networks [7, 8, 10].

Although similar in appearence to Problem (7), this problem is considerably
more challenging to solve.

######  Theorem 1.

For a fixed value of $q$ such that $K_{q}>1$, the percentile program in (13)
is strongly NP-hard in the number of users $K$.

The proof, detailed in Appendix A, is based on a polynomial-time reduction
from the maximum independent set problem. This reduction is considerably more
challenging than the sum-rate setting since we have to consider the entire
class of SLqP rate maximization problems which, in general, can have a
countably infinite number of instances as the number of users grows.

Further, we also remark that the proof of NP-hardness holds only for non-
minimum percentiles, i.e., $K_{q}>1$ (corresponding to $q>100/K$). This is in
agreement with the prior results in the literature: in contrast to the max-
sum-rate problem, the max-min-rate power control problem can be expressed as a
parametric linear program and solved to optimality in polynomial time [20].

The NP-hardness of Problem (13) has a major implication for solution
techniques: finding the global optimum is computationally intractable; thus,
reaching directional stationary points is the best we can hope to achieve with
polynomial-time (i.e., computationally efficient) algorithms [18].

######  Remark 7.

Problem (13) is non-convex and non-smooth for
$K_{q}\notin\left\\{1,K\right\\}$.

To establish the non-convexity, we note that the objective in (13a) can be
expressed as the pointwise maximum of the sum of every subset of $K_{q}$ users
in the network. The sum-of-rates function (for $K_{q}>1$) is well-known to be
non-convex in the powers [15, 22]; hence, the pointwise maximum of these sums
is also non-convex in general.

The non-smoothness follows directly from Property 5 and has important
consequences for the choice of optimization algorithm for solving Problem
(13): first-order methods like steepest descent cannot be directly implemented
[37], while second-order algorithms like Newton’s method are similarly
inapplicable since the Hessian is not defined [33].

In order to deal with non-smooth problems (such as max-min-rate), the min-max
WMSE [20], FP [23], and numerous prior [38] works all introduce additional
variables and constraints to ‘smooth’ the problem. Introducing a slack
variable $t$ and applying this approach to Problem (13), we obtain the
following equivalent smooth problem:

$\displaystyle\underset{t,\hskip
1.00006pt\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad t\hskip
20.00003pt\hskip 123.00021pt$ (14a)
$\displaystyle\mathrm{subject\,to}\quad\sum_{l=1}^{K_{q}}r_{i_{l}}\left(\mathbf{p}\right)\geq
t,\,\begin{array}[]{c}i_{k}\in\left\\{1,\ldots,K\right\\}\\\
i_{j}\neq{i}_{k},\forall{j\neq{k}}\end{array}$ (14d) $\displaystyle 0\leq
p_{k}\leq P_{\mathrm{max}},\,k=1,\ldots,K\hskip 13.00005pt$ (14e)

This problem is now amenable to gradient-based techniques. Yet this smoothed
reformulation suffers from a serious issue which makes its optimization
computationally intractable. To illustrate this, we consider the following
example. Suppose that we have a SISO network with 4 users, and wish to
optimize the $50^{\mathrm{th}}$-percentile throughput. This means that
$K_{q}=0.50\times 4=2$, i.e., we are maximizing the sum of the smallest two
rates.

$\displaystyle\underset{\mathbf{p},t}{\mathrm{maximize}}\quad t\hskip
124.00012pt$ (15a) $\displaystyle\mathrm{subject\,to}\quad 0\leq p_{k}\leq
P_{\mathrm{max}},\,k=1,\ldots,4\hskip 6.00006pt$ (15b) $\displaystyle
r_{1}\left(\mathbf{p}\right)+r_{2}\left(\mathbf{p}\right)\geq t\hskip
50.00008pt$ (15c) $\displaystyle
r_{1}\left(\mathbf{p}\right)+r_{3}\left(\mathbf{p}\right)\geq t\hskip
50.00008pt$ (15d) $\displaystyle
r_{1}\left(\mathbf{p}\right)+r_{4}\left(\mathbf{p}\right)\geq t\hskip
50.00008pt$ (15e) $\displaystyle
r_{2}\left(\mathbf{p}\right)+r_{3}\left(\mathbf{p}\right)\geq t\hskip
50.00008pt$ (15f) $\displaystyle
r_{2}\left(\mathbf{p}\right)+r_{4}\left(\mathbf{p}\right)\geq t\hskip
50.00008pt$ (15g) $\displaystyle
r_{3}\left(\mathbf{p}\right)+r_{4}\left(\mathbf{p}\right)\geq t\hskip
50.00008pt$ (15h)

In other words, we wish to maximize the slack variable $t$ such that the sum
of any two rates exceeds it. There are

${}_{4}C_{2}=\frac{4!}{\left(4-2\right)!2!}=6$

ways of choosing 2 users out of 4; hence, the number of additional constraints
introduced is 6.

In general, for a network with $K$ users and optimizing the throughput for the
weakest $K_{q}$ users, the smoothed variant of the SLqP rate maximization
problem will comprise

${}_{K}C_{K_{q}}=\frac{K!}{\left(K-K_{q}\right)!K_{q}!}$

constraints.

The issue now becomes obvious: even for very small problem sizes, dealing with
this combinatorial number of constraints quickly becomes impractical. To make
matters worse, the constraints (e.g. (15c-15h)) are in a sum-of-rates form,
which is known to be non-convex [22, 23, 15]. Therefore, applying the prior
techniques incurs formidable computational complexity.

In summary, published approaches used to optimize classical metrics do not
apply to our percentile problem. Therefore, we seek an alternative method
which allows us to overcome these formidable challenges.

###  IV-B Proposed Approaches

To derive effective optimization strategies for the problem in (13), we
develop techniques to transform it into equivalent block-concave forms.
Specifically, we develop two algorithmic approaches that allow for iterative
optimization of the original problem to stationarity. We discuss each of these
separately in the subsequent subsections.

####  IV-B1 Quadratic Fractional Transform

Our first technique utilizes the quadratic fractional transform (QFT), first
proposed in [39] by Benson and subsequently exploited by Shen and Yu in [15]
primarily for weighted sum-rate maximization problems. As explained in the
previous section, while this transform has also been utilized for the non-
smooth max-min-rate optimization problem [15], the direct application of this
transform to Problem (13) for non-minimum percentiles would be based on the
aforementioned hypograph form with ${}_{K}C_{K_{q}}$ constraints. In contrast,
we develop an approach that allows us to transform the original problem while
side-stepping the associated combinatorial number of non-convex constraints.

We begin by re-stating the transform below:

######  Lemma 1.

Let $A\left(\mathbf{p}\right):\mathbb{R}^{K}\mapsto\mathbb{R}_{+}$,
$B\left(\mathbf{p}\right):\mathbb{R}^{K}\mapsto\mathbb{R}_{++}$ and
$\mathcal{P\subseteq}\mathbb{R}^{K}$. Then the fractional optimization problem

$\displaystyle\underset{\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad\frac{A\left(\mathbf{p}\right)}{B\left(\mathbf{p}\right)}\hskip
50.00008pt$ (16a)
$\displaystyle\mathrm{subject\,to}\quad\mathbf{p}\in\mathcal{P}\hskip 49.0pt$
(16b)

is equivalent to the following auxiliary optimization problem

$\displaystyle\underset{x,\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad
2x\sqrt{A\left(\mathbf{p}\right)}-x^{2}B\left(\mathbf{p}\right)\hskip 5.0pt$
(17a) $\displaystyle\mathrm{subject\,to}\quad\mathbf{p}\in\mathcal{P}\hskip
68.00012pt$ (17b)

where the equivalence is in the sense of both the optimal variables and
objective function value.

###### Proof.

Observe that the objective in (17a) is concave in the auxiliary variable $x$.
Furthermore, setting the first order condition with respect to this variable,
we obtain:

$\frac{\partial}{\partial
x}\left\\{2x\sqrt{A\left(\mathbf{p}\right)}-x^{2}B\left(\mathbf{p}\right)\right\\}=0\Rightarrow
x=\frac{\sqrt{A\left(\mathbf{p}\right)}}{B\left(\mathbf{p}\right)}$

Substituting this value of $x$ back into the objective in (17a) we obtain the
original objective in (16a). ∎

Based on this transform, we now proceed to derive an equivalent reformulation
of the problem in (13).

######  Theorem 2.

The optimization problem in (13) is equivalent to the following auxiliary
problem:

$\displaystyle\underset{\mathbf{x},\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad
f_{K_{q}}\left(\hat{r}_{1}\left(x_{1},\mathbf{p}\right),\ldots,\hat{r}_{K}\left(x_{K},\mathbf{p}\right)\right)$
(18a) $\displaystyle\mathrm{subject\,to}\quad 0\leq p_{k}\leq
P_{\mathrm{max}},\,k=1,\ldots,K\hskip 10.00002pt$ (18b)

where

$\hat{r}_{k}\left(x_{k},\mathbf{p}\right)=\mathrm{log}\left(1+2x_{k}\sqrt{A_{k}\left(\mathbf{p}\right)}-\right.\left.\left(x_{k}\right)^{2}B_{k}\left(\mathbf{p}\right)\right)$
(19)

and $A_{k}\left(\mathbf{p}\right)$ and $B_{k}\left(\mathbf{p}\right)$
represent the signal and interference-plus-noise powers at the $k^{th}$ user
respectively, i.e.,

$\displaystyle A_{k}\left(\mathbf{p}\right)=p_{k}\left|h_{k\rightarrow
k}\right|^{2}\hskip 38.20012pt$ (20a) $\displaystyle
B_{k}\left(\mathbf{p}\right)=\sum_{j\neq k}p_{j}\left|h_{j\rightarrow
k}\right|^{2}+\sigma^{2}$ (20b)

The equivalence between the two problems is in the sense of the optimal
variables and objective function values.

The details of the proof are provided in Appendix B.

The problem in (18) is now in a form that is amenable to a cyclic optimization
strategy. First, we observe that with $\mathbf{p}$ fixed, an optimal choice of
$\mathbf{x}$ to maximize the auxiliary objective in (18a) is given by Lemma 1
as

$x_{k}=\frac{\sqrt{A_{k}\left(\mathbf{p}\right)}}{B_{k}\left(\mathbf{p}\right)},\quad{k}{=}{1,\ldots,K}$
(21)

where $A_{k}\left(\mathbf{p}\right)$ and $B_{k}\left(\mathbf{p}\right)$ are
given as in (20a) and (20b) respectively.

######  Remark 8.

It is crucial to note that, unlike other uses of fractional programming in the
literature [15, 40, 16], $f_{K_{q}}\left(\cdot\right)$ is not strictly
concave; hence, there may be (infinitely many) other optimal choices of
$\mathbf{x}$ that achieve an identical maximum value of the auxiliary
objective. However, the update in (21) uniquely preserves the equivalence with
the original problem in (13).

We next turn our attention to optimizing the power variables. To do so, we
make use of the following critical insight:

######  Remark 9.

The auxiliary objective function in (18a) is concave in the power variables
$\mathbf{p}$ when the auxiliary variables $\mathbf{x}$ are fixed.

This block-concavity can be understood as follows: observe that the terms
$A_{k}\left(\mathbf{p}\right)$ and $B_{k}\left(\mathbf{p}\right)$ are linear
and affine functions of $\mathbf{p}$ respectively and hence concave. From
(21), we note that the auxiliary variables $x_{k}$ are always non-negative
owing to the non-negativity of $A_{k}\left(\mathbf{p}\right)$ and
$B_{k}\left(\mathbf{p}\right)$. Taken together with the concavity and
monotonicity of the logarithm function, it follows that
$\tilde{r}_{k}\left(x_{k},\mathbf{p}\right)$ is concave in $\mathbf{p}$.
Finally, from Properties 1 and 2, we note that $f_{K_{q}}\left(\cdot\right)$
is concave and non-decreasing in each component. Therefore, similar to the
parallel Gaussian channel setting, it follows from the composition rule that
the auxiliary objective in (18a) is concave in the power variables when the
auxiliary variables are fixed. Thus, an optimal $\mathbf{p}$ can be obtained
straightforwardly when $\mathbf{x}$ is fixed by solving a convex optimization
problem using CVX or the subgradient method as discussed earlier.

Combining these updates together, Algorithm 1 summarizes the proposed QFT
approach for maximizing the SLqP rate in (13a).

Algorithm 1 QFT Algorithm for SLqP Rate Maximization

1:initialize $\mathbf{p}$

2:for $i=1,\ldots$ do

3: update $\mathbf{x}$ using (21).

4: update $\mathbf{p}$ by solving (18) for fixed $\mathbf{x}$.

5:until some convergence criterion is met.

$\displaystyle
f_{K_{q}}\left(r_{1}\left(\mathbf{p}\left[i+1\right]\right),\ldots,r_{K}\left(\mathbf{p}\left[i+1\right]\right)\right)=f_{K_{q}}\left(\tilde{r}_{1}\left(x_{1}\left[i+1\right],\mathbf{p}\left[i+1\right]\right),\ldots,\tilde{r}_{K}\left(x_{K}\left[i+1\right],\mathbf{p}\left[i+1\right]\right)\right)$
(22a) $\displaystyle\geq
f_{K_{q}}\left(\tilde{r}_{1}\left(x_{1}\left[i+1\right],\mathbf{p}\left[i\right]\right),\ldots,\tilde{r}_{K}\left(x_{K}\left[i+1\right],\mathbf{p}\left[i\right]\right)\right)$
(22b) $\displaystyle\geq
f_{K_{q}}\left(\tilde{r}_{1}\left(x_{1}\left[i\right],\mathbf{p}\left[i\right]\right),\ldots,\tilde{r}_{K}\left(x_{K}\left[i\right],\mathbf{p}\left[i\right]\right)\right)\hskip
9.90007pt$ (22c)
$\displaystyle=f_{K_{q}}\left(r_{1}\left(\mathbf{p}\left[i\right]\right),\ldots,r_{K}\left(\mathbf{p}\left[i\right]\right)\right)\hskip
62.55006pt$ (22d)

######  Theorem 3.

Algorithm 1 is non-decreasing in the SLqP rate objective given in (13a) after
each iteration.

###### Proof.

The non-decreasing nature of the algorithm can be understood by considering
the chain of reasoning in (22a)–(22d), where $\mathbf{p}\left[i\right]$ and
$\mathbf{x}\left[i\right]$ indicate the values of these variables in the
$i^{\mathrm{th}}$ iteration. Specifically, (22a) follows from Theorem 2; (22b)
follows from the fact that updating $\mathbf{p}$ when $\mathbf{x}$ is fixed
maximizes the auxiliary objective in (18a); (22c) follows from similar
reasoning applied to the update of $\mathbf{x}$ when $\mathbf{p}$ is fixed,
and (22d) follows from Theorem 2. Further, we note that since the SLqP rate
objective is upper bounded, the algorithm must converge. ∎

######  Theorem 4.

Algorithm 1 is a cyclic minorization-maximization (MM) algorithm and is
guaranteed to converge to a directional stationary point of Problem (13).

The proof is detailed in Appendix C. We remark that this convergence result is
different from those in the prior FP/WMMSE works [23, 15, 22] which primarily
focus on reaching stationary points of weighted sum-rate problems. For the WSR
(and by extension the special sum-rate case), it is sufficient to show that
the objective function is non-decreasing after each iteration of the
algorithms. In contrast, the SLqP rate objective function is non-smooth in
general, which means that we instead have to prove convergence to a
directional stationary point, which is considerably more challenging.

####  IV-B2 Logarithmic Fractional Transform

The quadratic transform is well-established in the literature as a means of
tackling sum-of-ratios optimization problems [15, 24]. In principle, however,
any similar transform that converts the rate expression into block-concave
form would allow us to optimize SLqP utility in an identical fashion. Hence,
the quadratic fractional transform is sufficient, but not necessary to solve
percentile programs. Accordingly, in this section, we introduce a novel
transform, called the logarithmic fractional transform (LFT), which similarly
allows us to tackle percentile rate programs by converting them into block-
concave forms. While similar in spirit to the QFT, the resultant approach is
algorithmically distinct, and thus generally converges to distinct directional
stationary points.

######  Theorem 5.

Let $A\left(\mathbf{p}\right):\mathbb{R}^{K}\mapsto\mathbb{R}_{+}$,
$B\left(\mathbf{p}\right):\mathbb{R}^{K}\mapsto\mathbb{R}_{++}$ and
$\mathcal{P\subseteq}\mathbb{R}^{K}$. Then the fractional optimization problem

$\displaystyle\underset{\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad\mathrm{log}\left(1+\frac{A\left(\mathbf{p}\right)}{B\left(\mathbf{p}\right)}\right)\hskip
5.0pt$ (23a)
$\displaystyle\mathrm{subject\,to}\quad\mathbf{p}\in\mathcal{P}\hskip 49.0pt$
(23b)

is equivalent to the following auxiliary optimization problem

$\displaystyle\underset{x,\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad-
xB\left(\mathbf{p}\right)+\mathrm{log}\left(x\left(A\left(\mathbf{p}\right)+B\left(\mathbf{p}\right)\right)\right)+1$
(24a) $\displaystyle\mathrm{subject\,to}\quad\mathbf{p}\in\mathcal{P}\hskip
141.00027pt$ (24b)

where the equivalence is in the sense of both the optimal variables and
objective function value.

###### Proof.

The proof is similar to that for Theorem 1. The objective in (24a) is concave
in the auxiliary variable $x$; hence, setting the first order condition with
respect to this variable, we obtain:

$\frac{\partial}{\partial
x}\left\\{-xB\left(\mathbf{p}\right)+\mathrm{log}\left(x\left(A\left(\mathbf{p}\right)+B\left(\mathbf{p}\right)\right)\right)+1\right\\}=0\\\
\Rightarrow x=\frac{1}{B\left(\mathbf{p}\right)}$ (25)

Substituting this value of $x$ back into the objective in (24a) we obtain the
original objective in (23a). ∎

######  Theorem 6.

The optimization problem in (13) is equivalent to the following auxiliary
problem:

$\displaystyle\underset{\mathbf{x},\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad
f_{K_{q}}\left(\check{r}_{1}\left(x_{1},\mathbf{p}\right),\ldots,\check{r}_{K}\left(x_{K},\mathbf{p}\right)\right)$
(26a) $\displaystyle\mathrm{subject\,to}\quad 0\leq p_{k}\leq
P_{\mathrm{max}},\,k=1,\ldots,K\hskip 10.00002pt$ (26b)

where

$\check{r}_{k}\left(x_{k},\mathbf{p}\right)=-x_{k}B_{k}\left(\mathbf{p}\right)+\mathrm{log}\left(x\left(A_{k}\left(\mathbf{p}\right)+B_{k}\left(\mathbf{p}\right)\right)\right)+1$
(27)

and $A_{k}\left(\mathbf{p}\right)$ and $B_{k}\left(\mathbf{p}\right)$ are the
received signal and interference-plus-noise powers at the $k^{th}$ user given
in (20a) and (20b) respectively. The equivalence between the two problems is
in the sense of the optimal variables and objective function values.

###### Proof.

The proof follows from a reasoning similar to Theorem 2; the details are
omitted for brevity. ∎

Similar to the quadratic transform auxiliary objective, the logarithmic
transform auxiliary objective in (26) is now in a form amenable to
optimization. With the power variables $\mathbf{p}$ fixed, an optimal choice
for the auxiliary variables $\mathbf{x}$ is given by

$x_{k}=\frac{1}{B_{k}\left(\mathbf{p}\right)},\quad{k}=1,\ldots,K$ (28)

######  Remark 10.

The auxiliary objective function in (26a) is concave in the power variables
$\mathbf{p}$ when the auxiliary variables $\mathbf{x}$ are fixed.

###### Proof.

The proof follows from similar reasoning to Remark 9. ∎

From the preceding remark, it follows that a similar block coordinate ascent
strategy to Algorithm 1 can be utilized to derive an effective optimization
strategy by alternately fixing the power variables $\mathbf{p}^{(n)}$ while
updating $\mathbf{x}^{(n)}$, and vice versa. Combining these update steps
together, we summarize the second proposed approach for SLqP rate optimization
in Algorithm 2.

Algorithm 2 LFT Algorithm for SLqP Rate Maximization

1:initialize $\mathbf{p}$

2:for $i=1,\ldots$ do

3: update $\mathbf{x}$ using (28).

4: update $\mathbf{p}$ by solving (26) for fixed $\mathbf{x}$.

5:until some convergence criterion is met.

######  Theorem 7.

Algorithm 2 is a cyclic MM algorithm and converges in a non-decreasing fashion
to reach a directional stationary point of the original SLqP rate objective in
(13a).

###### Proof.

The proof follows from similar reasoning to Theorems 3 and 4; the details are
omitted for brevity. ∎

###  IV-C Numerical Results

To evaluate the performance of the proposed algorithms, we simulate a network
with $7$ hexagonal wrapped-around cells and BSs located at the center of each
cell. Each cell contains $8$ users; thus, the total number of users in the
network is $K=56$. The distance between adjacent BSs is set as $2000\hskip
1.00006pt\mathrm{m}$, and we assume Rayleigh fading with a block-fading model.
The path loss between a user and BS separated by a distance of $d$ meters is
given by $\left(1+{d}/{d_{0}}\right)^{-\zeta/2}$ where $d_{0}=0.3920$ is a
model-dependent reference distance, and $\zeta=3.76$ is the pathloss exponent.
The noise power spectral density (PSD) is $-143\hskip
1.00006pt\mathrm{dBm/Hz}$; we assume a system bandwidth of $20\hskip
1.00006pt\mathrm{MHz}$ and maximum per-user transmit power constraint of
$43\hskip 1.00006pt\mathrm{dBm}$. The path loss exponent and reference
distance that we utilize are based on the COST231 model which simulates LTE
channels in real-world conditions. As such, these parameters have been
identically utilized in numerous prior works including, but not limited to,
[23, 15, 16, 32].

We begin by considering the performance of the proposed approach for the SLqP
rate maximization problem for $K_{q}=14$, i.e., the $25^{\mathrm{th}}$
percentile throughput for a single channel realization with the user and BS
locations illustrated in Figure 4. For these and subsequent results, we
initialize each user’s transmission power by sampling uniformly randomly in
the interval $\left[0,P_{\mathrm{max}}\right]$. We observe from the results in
Figure 3 that for both the quadratic fractional transform algorithm and
logarithmic fractional transform algorithm, the auxiliary objective function
values are equivalent after each iteration as per Theorems 2 and 6.
Furthermore, as predicted by Theorems 4 and 7, both algorithms converge in a
non-decreasing fashion (starting from an identical random initialization) to a
stationary point.

Figure 3: Convergence of proposed algorithms for $25^{\mathrm{th}}$-percentile
SLqP rate maximization problem, $K=56$, $K_{q}=14$. Figure 4: User and BS
locations for a single realization in a network with $K=70$ users.

Additionally, we compare the performance of the proposed QFT and LFT
algorithms against several well-known prior algorithms from the resource
allocation literature. Specifically, we compare against the following four
algorithms:

  * •

Successive Convex Approximation (SCA): this approach has widely been used in a
number of signal processing problems and resource management algorithms [41,
42, 43]; we use the variant in [38, 44].

  * •

Sequential Quadratic Programming (SQP): This has been widely utilized as a
benchmark in prior resource management algorithms [16]. For our
implementation, we utilize this method using the standard `fmincon` solver in
MATLAB.

  * •

Subgradient Ascent (SGA): The subgradient ascent method is a heuristic for
optimizing non-smooth problems, and is an analogue of the well-known gradient
ascent method [35]. Specifically, for problems in which the objective function
is non-differentiable, this method repeatedly computes and then takes steps in
the direction of a subgradient of the objective function. Compared to the
aforementioned SCA and SQP methods, this approach has the unique benefit of
running much faster, as we do not introduce a combinatorial number of
constraints.

  * •

Channel Weighted Sum-Rate (CWSR): We also compare against a heuristic of
weighted sum-rate in which the weights are set to the inverse of the channel
strength for each user. This favours the cell-edge users by weighting them
higher as compared to the cell-centre users.

Figure 5 shows the convergence for a randomly-generated set of identical
channel realizations for $K=14$ and $K_{q}=7$. We observe that the QFT and LFT
algorithms converge quickly, and in a non-decreasing fashion, to a directional
stationary point within as little as 6 iterations and achieve the highest
objective function value. Among the competitors, the SCA approach performs the
best and converges in a non-decreasing fashion. On the other hand, the CWSR
approach increases initially but then decreases after the second iteration. We
note that this heuristic optimizes a different, proxy utility function (i.e.,
WSR) as compared to the true objective function (i.e., SLqP) rate; hence, this
result is unsurprising.

Figure 5: Convergence of SLqP utility for $K=14$ and $K_{q}=7$.

We also considered another set of parameters, with $K=21$ and $K_{q}=3$ and
averaged across a large set of random channel realizations. The results for
this case are illustrated in Table I. It can be clearly seen that the QFT and
LFT algorithms achieve the best performance, followed by the SCA and SGA
algorithms. The SCA algorithm has the best performance once again among the
competitors but the proposed QFT and LFT algorithms still achieve about 30%
higher objective function values.

As mentioned earlier, an additional critical point that cannot be ignored is
the computation time. Since the prior optimization algorithms smooth the
problem prior to solving it, the computation time needed to deal with the
combinatorial number of non-convex constraints is excessive. To measure the
execution times, we ran all algorithms on a machine with a 12-core AMD Ryzen 9
5900X CPU and 128 GB of memory; these are also given in Table I. We observe
that the proposed QFT and LFT schemes converge to a solution more than 1,000
times faster than the SCA and SQP algorithms. This is to be expected, since
the smoothed variant of the problem required by these algorithms will have
${}_{21}C_{3}=1,330$ non-convex constraints, which will lead to a longer
computational time. On the other hand, while the CWSR and SGA approaches
execute much faster compared to CVX, they achieve low objective function
values. Consequently, we affirm that our QFT and LFT schemes demonstrate
superior speed and performance compared to the benchmarks.

We note that it is possible to write custom solvers (e.g. based on subgradient
methods [35]) which may be able to solve the problem more efficiently than
calling CVX. It is also not clear if closed-form algorithms can be found to
solve the general SLqP-rate maximization problem; nonetheless, this would be
an extremely interesting direction for future research.

TABLE I: Execution times and SLqP utility for different resource algorithms. Algorithm | SLqP Utility | Execution Time (seconds)
---|---|---
QFT | 1.49 | 13
LFT | 1.47 | 13
SCA | 1.20 | 18,953
SQP | 0.81 | 21,559
SGA | 0.93 | 24
CWSR | 0.86 | 3

To further evaluate the performance, we next consider SLqP rate optimization
for the scenario when there are $K=70$ users in the network for $K_{q}=7$
(corresponding to $q=10$, and shown in Figure 6) and $K_{q}=4$ (corresponding
to $q=5.7$, and shown in Figure 7). We ran the QFT and LFT algorithms for 1000
identically chosen random channel and user location initializations and
plotted the performance as compared to randomized power control, sum-rate
optimized power control (using the WMMSE-SR algorithm [22]) and PF control
(using the WMMSE-PF algorithm as in [22]) for $P_{\mathrm{max}}$ values
ranging between 10 dBm and 50 dBm. The PF power control scheme aims to
maximize the sum of the logarithm of the achieved rates across the network;
for a single time slot, this is a convex optimization problem [18] and hence
the WMMSE-PF algorithm converges to the optimum.

As we observe in Figure 6, the sum-rate optimized power control achieves
nearly zero cell-edge SLqP rate across the entire range of transmission
powers; as mentioned earlier, this is to be expected since this optimization
is unfair to cell-edge users. Random power control is better than sum-rate
optimized power control while PF power control improves on both. Nevertheless,
the proposed QFT and LFT algorithms comprehensively outperform even the PF
power control scheme, achieving almost double the cell-edge throughput
compared to the WMMSE-PF power control scheme at the typical LTE power level
of 43 dBm. At a transmission power of 50 dBm, the gap between the proposed
approaches and the PF benchmark is even larger. Notably, the QFT algorithm
marginally outperforms the LFT algorithm across the range of transmit powers.
A similar trend holds for the $5.7^{\mathrm{th}}$-percentile SLqP utility in
Figure 7.

Figure 6: $10^{\mathrm{th}}$-percentile SLqP rate as a function of
$P_{\mathrm{max}}$ for $K=70$, $K_{q}=7$. Figure 7:
$5.7^{\mathrm{th}}$-percentile SLqP rate as a function of $P_{\mathrm{max}}$
for $K=70$, $K_{q}=4$.

Finally, it is important to note that while both the QFT and LFT algorithms
are minorization-maximization methods they are, in fact, completely distinct
from a mathematical perspective. This means that even when initialized from
the same starting point, in general they do not necessarily converge to the
same directional stationary point. For example, different algorithms for
weighted sum-rate maximization such as FP and WMMSE achieve different levels
of performance in different wireless settings [23, 15].

With this context, the closely matched performance of both algorithms is, in
itself, a very interesting result. While the reasons for this are not clear,
it seems to indicate that improving upon the performance of the QFT and LFT
algorithms may require a radically different approach (perhaps one that is not
necessarily based on block-concavity inducing transforms).

##  V Conclusions

In this paper, we formulated explicit optimization problems to target sum-
percentile throughput maximization through power control in interference-
constrained wireless networks. The general class of SLqP throughput problems
subsumes the well-known max-min and max-sum-rate optimization problems, and
the choice of percentile allows us to flexibly control the inherent tradeoff
between favouring cell-center and cell-edge users. With the exception of the
two aforementioned extremes of the percentile problems, these problems are
non-convex, non-smooth and NP-hard in general. We proposed two iterative
algorithms that transform the original intractable problems into block-concave
form, thereby enabling guaranteed convergence to stationary points.

Finally, we note that although we have focused on wireless cellular networks
in this work, the concept of optimizing metrics at desired percentiles is
applicable regardless of the scale, architecture and nature of a
communications network.

## References

  * [1] E. Björnson, “Optimal Resource Allocation in Coordinated Multi-Cell Systems,” _Found. Trends Commun. Inf. Theory_ , vol. 9, no. 2-3, pp. 113–381, 2013.
  * [2] D. Gesbert, S. G. Kiani, A. Gjendemsjo, and G. E. Oien, “Adaptation, Coordination, and Distributed Resource Allocation in Interference-Limited Wireless Networks,” _Proc. IEEE_ , vol. 95, no. 12, pp. 2393–2409, Dec. 2007.
  * [3] B. Soret, A. D. Domenico, S. Bazzi, N. H. Mahmood, and K. I. Pedersen, “Interference Coordination for 5G New Radio,” _IEEE Wireless Commun._ , vol. 25, no. 3, pp. 131–137, Jun. 2018.
  * [4] J. Ma, S. Zhang, H. Li, N. Zhao, and V. C. M. Leung, “Interference-Alignment and Soft-Space-Reuse Based Cooperative Transmission for Multi-cell Massive MIMO Networks,” _IEEE Trans. Wireless Commun._ , vol. 17, no. 3, pp. 1907–1922, Mar. 2018.
  * [5] H. Zhang, L. Venturino, N. Prasad, P. Li, S. Rangarajan, and X. Wang, “Weighted Sum-Rate Maximization in Multi-Cell Networks via Coordinated Scheduling and Discrete Power Control,” _IEEE J. Select. Areas Commun._ , vol. 29, no. 6, pp. 1214–1224, Jun. 2011.
  * [6] H. H. Yang, G. Geraci, T. Q. S. Quek, and J. G. Andrews, “Cell-Edge-Aware Precoding for Downlink Massive MIMO Cellular Networks,” _IEEE Trans. Signal Process._ , vol. 65, no. 13, pp. 3344–3358, Jul. 2017\.
  * [7] 3GPP Technical Report 38.913 V17.0.0, “Study on Scenarios and Requirements for Next Generation Access Technologies,” Mar. 2022.
  * [8] 5G Public Private Partnership, “Whitepaper: Beyond 5g/6g kpis and target values,” Jun. 2022.
  * [9] ITU-R, “Minimum requirements related to technical performance for IMT-2020 radio interface(s),” Nov. 2017.
  * [10] V. Ziegler and S. Yrjola, “6G Indicators of Value and Performance,” in _2020 2nd 6G Wireless Summit (6G SUMMIT)_. Levi, Finland: IEEE, Mar. 2020, pp. 1–5.
  * [11] B. Sihlbom, M. I. Poulakis, and M. D. Renzo, “Reconfigurable Intelligent Surfaces: Performance Assessment Through a System-Level Simulator,” _IEEE Wireless Communications_ , pp. 1–10, 2022.
  * [12] H.-B. Chang and I. Rubin, “Optimal Downlink and Uplink Fractional Frequency Reuse in Cellular Wireless Networks,” _IEEE Trans. Veh. Technol._ , vol. 65, no. 4, pp. 2295–2308, Apr. 2016.
  * [13] P. D. Mankar, G. Das, and S. S. Pathak, “Load-Aware Performance Analysis of Cell Center/Edge Users in Random HetNets,” _IEEE Trans. Veh. Technol._ , vol. 67, no. 3, pp. 2476–2490, Mar. 2018.
  * [14] D. Lopez-Perez, M. Ding, H. Claussen, and A. H. Jafari, “Towards 1 Gbps/UE in Cellular Systems: Understanding Ultra-Dense Small Cell Deployments,” _IEEE Commun. Surv. Tutorials_ , vol. 17, no. 4, pp. 2078–2101, 2015.
  * [15] K. Shen and W. Yu, “Fractional Programming for Communication Systems—Part II: Uplink Scheduling via Matching,” _IEEE Trans. Signal Process._ , vol. 66, no. 10, pp. 2631–2644, May 2018.
  * [16] A. A. Khan, R. Adve, and W. Yu, “Optimizing Downlink Resource Allocation in Multiuser MIMO Networks via Fractional Programming and the Hungarian Algorithm,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 8, pp. 5162–5175, Aug. 2020, arXiv: 2006.12549.
  * [17] N. Naderializadeh, J. J. Sydir, M. Simsek, and H. Nikopour, “Resource Management in Wireless Networks via Multi-Agent Deep Reinforcement Learning,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 6, pp. 3507–3523.
  * [18] Zhi-Quan Luo and Shuzhong Zhang, “Dynamic Spectrum Management: Complexity and Duality,” _IEEE J. Sel. Top. Signal Process._ , vol. 2, no. 1, pp. 57–73, Feb. 2008.
  * [19] J. V. C. Evangelista, Z. Sattar, G. Kaddoum, and A. Chaaban, “Fairness and Sum-Rate Maximization via Joint Subcarrier and Power Allocation in Uplink SCMA Transmission,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 12, pp. 5855–5867, Dec. 2019.
  * [20] M. Razaviyayn, M. Hong, and Z.-Q. Luo, “Linear Transceiver Design for a MIMO Interfering Broadcast Channel Achieving Max–Min Fairness,” _Signal Process._ , vol. 93, no. 12, pp. 3327–3340, 2013.
  * [21] M. M. Naghsh, M. Masjedi, A. Adibi, and P. Stoica, “Max–Min Fairness Design for MIMO Interference Channels: A Minorization–Maximization Approach,” _IEEE Trans. Signal Process._ , vol. 67, no. 18, pp. 4707–4719, Sep. 2019.
  * [22] Q. Shi, M. Razaviyayn, Z.-Q. Luo, and C. He, “An Iteratively Weighted MMSE Approach to Distributed Sum-Utility Maximization for a MIMO Interfering Broadcast Channel,” _IEEE Trans. Signal Process._ , vol. 59, no. 9, pp. 4331–4340, Sep. 2011.
  * [23] K. Shen and W. Yu, “Fractional Programming for Communication Systems—Part I: Power Control and Beamforming,” _IEEE Trans. Signal Process._ , vol. 66, no. 10, pp. 2616–2630, May 2018.
  * [24] A. A. Khan, R. Adve, and W. Yu, “Optimizing Multicell Scheduling and Beamforming via Fractional Programming and Hungarian Algorithm,” in _IEEE Globecom Workshops (GC Wkshps)_ , Abu Dhabi, United Arab Emirates, Dec. 2018, pp. 1–6.
  * [25] M. Rahman, H. Yanikomeroglu, and W. Wong, “Interference Avoidance with Dynamic Inter-Cell Coordination for Downlink LTE System,” in _IEEE Wireless Commun. Netw. Conf. (WCNC)_ , Budapest, Hungary, Apr. 2009, pp. 1–6.
  * [26] A. Ghazanfari, H. V. Cheng, E. Bjornson, and E. G. Larsson, “Enhanced Fairness and Scalability of Power Control Schemes in Multi-Cell Massive MIMO,” _IEEE Trans. Commun._ , vol. 68, no. 5, pp. 2878–2890.
  * [27] C. Guo, Y. Zhang, M. Sheng, X. Wang, and Y. Li, “$\alpha$-Fair Power Allocation in Spectrum-Sharing Networks,” _IEEE Trans. Veh. Technol._ , vol. 65, no. 5, pp. 3771–3777, May 2016.
  * [28] A. B. Sediq, R. H. Gohary, R. Schoenen, and H. Yanikomeroglu, “Optimal Tradeoff Between Sum-Rate Efficiency and Jain’s Fairness Index in Resource Allocation,” _IEEE Trans. Wireless Commun._ , vol. 12, no. 7, pp. 3496–3509, Jul. 2013.
  * [29] T. Lan, D. Kao, M. Chiang, and A. Sabharwal, “An Axiomatic Theory of Fairness in Network Resource Allocation,” in _Proc. IEEE INFOCOM_ , San Diego, CA, USA, Mar. 2010, pp. 1–9.
  * [30] M. Eisen, C. Zhang, L. F. O. Chamon, D. D. Lee, and A. Ribeiro, “Learning Optimal Resource Allocations in Wireless Systems,” _IEEE Trans. Signal Process._ , vol. 67, no. 10, pp. 2775–2790, May 2019.
  * [31] Y. Li, S. Han, and C. Yang, “Multicell Power Control Under Rate Constraints With Deep Learning,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 12, pp. 7813–7825, Dec. 2021.
  * [32] K. Hosseini, C. Zhu, A. A. Khan, R. S. Adve, and W. Yu, “Optimizing the MIMO Cellular Downlink: Multiplexing, Diversity, or Interference Nulling?” _IEEE Trans. Commun._ , vol. 66, no. 12, pp. 6068–6080, Dec. 2018.
  * [33] S. P. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, Mar. 2004.
  * [34] M. J. Todd, “On max-k-sums,” _Math. Program._ , vol. 171, no. 1, pp. 489–517, Sep. 2018.
  * [35] Y. Nesterov, “Subgradient methods for huge-scale optimization problems,” _Math. Program._ , vol. 146, no. 1-2, pp. 275–297, Aug. 2014.
  * [36] “CVX Reference Guide.” [Online]. Available: http://cvxr.com/cvx/doc/funcref.html
  * [37] J. V. Burke, A. S. Lewis, and M. L. Overton, “A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization,” _SIAM J. Optim._ , vol. 15, no. 3, pp. 751–779, Jan. 2005.
  * [38] G. Scutari, F. Facchinei, L. Lampariello, S. Sardellitti, and P. Song, “Parallel and Distributed Methods for Constrained Nonconvex Optimization-Part II: Applications in Communications and Machine Learning,” _IEEE Trans. Signal Process._ , vol. 65, no. 8, pp. 1945–1960, Apr. 2017.
  * [39] H. P. Benson, “On the Global Optimization of Sums of Linear Fractional Functions Over a Convex Set,” _J. Optim. Theory Appl._ , vol. 121, no. 1, pp. 19–39.
  * [40] Z. Wei, D. W. K. Ng, and J. Yuan, “NOMA for Hybrid mmWave Communication Systems With Beamwidth Control,” _IEEE J. Sel. Top. Signal Process._ , vol. 13, no. 3, pp. 567–583.
  * [41] C. Shen, T.-H. Chang, J. Gong, Y. Zeng, and R. Zhang, “Multi-UAV Interference Coordination via Joint Trajectory and Power Control,” _IEEE Trans. Signal Process._ , vol. 68, pp. 843–858, 2020.
  * [42] M. S. Ibrahim, A. Konar, and N. D. Sidiropoulos, “Fast Algorithms for Joint Multicast Beamforming and Antenna Selection in Massive MIMO,” _IEEE Trans. Signal Process._ , vol. 68, pp. 1897–1909, 2020.
  * [43] M. Dong and Q. Wang, “Multi-Group Multicast Beamforming: Optimal Structure and Efficient Algorithms,” _IEEE Trans. Signal Process._ , vol. 68, pp. 3738–3753, 2020.
  * [44] G. Scutari, F. Facchinei, and L. Lampariello, “Parallel and Distributed Methods for Constrained Nonconvex Optimization—Part I: Theory,” _IEEE Trans. Signal Process._ , vol. 65, no. 8, pp. 1929–1944, Apr. 2017, number: 8.
  * [45] Y. Sun, P. Babu, and D. P. Palomar, “Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning,” _IEEE Trans. Signal Process._ , vol. 65, no. 3, pp. 794–816, Feb. 2017.
  * [46] M. W. Jacobson and J. A. Fessler, “An Expanded Theoretical Treatment of Iteration-Dependent Majorize-Minimize Algorithms,” _IEEE Trans. Image Process._ , vol. 16, no. 10, pp. 2411–2422, 2007.

##  Appendix A Proof of Theorem 1

We now present a proof for the general NP-hardness of the short-term SLqP rate
power allocation problem. We extend the technique utilized to prove the strong
NP-hardness of the max-sum-rate problem in [18] to all general SLqP rate power
control problems for $q\geq\frac{200}{K}$.

We begin by noting that the rates for users in a single time slot can be
expressed in the equivalent form:

$r_{k}\left(\mathbf{p}\right)=\mathrm{log}\left(1+\frac{p_{k}}{\sum_{j\neq
k}p_{j}\eta_{j\rightarrow k}+\hat{\sigma}_{k}}\right)$

where, for notational convenience, we have dropped the superscript denoting
the current time slot, and

$\eta_{j\rightarrow k}=\frac{\left|h_{j\rightarrow
k}\right|^{2}}{\left|h_{k\rightarrow
k}\right|^{2}},\hat{\sigma}_{k}=\frac{\sigma_{k}}{\left|h_{k\rightarrow
k}\right|^{2}}$

The coefficient $\eta_{j\rightarrow k}$ can be thought of as the normalized
interference channel from transmitter $j$ to receiver $k$; further, we assume
$P_{\mathrm{max}}=1$.

Consider a $K$-node graph $G=(V,E)$, where
$V=\left\\{v_{1},v_{2},\ldots,v_{K}\right\\}$ denotes the set of vertices and
$E$ denotes the set of edges connecting these vertices. Further, suppose that
the graph consists of $K-K_{q}+1$ components defined as follows:

$C_{i}=\left\\{\begin{array}[]{cc}\left\\{v_{i}\right\\}&i=1,\ldots,K-K_{q}\\\
\left\\{v_{K-K_{q}+1},v_{K-K_{q}+2},\ldots,v_{K}\right\\}&i=K-K_{q}+1\end{array}\right.$
(29)

In other words, the first $K-K_{q}$ vertices are isolated, while the subgraph
induced by the last $K_{q}$ vertices is connected; Figure 8 illustrates an
example for $K=10$ and $K_{q}=5$.

Now, for each $v\in{V}$, we define

$\eta_{j\rightarrow k}=\begin{cases}LK_{q}^{2}&\mathrm{if}\hskip
3.00003pt{v_{j}}\hskip 3.00003pt\mathrm{is\hskip 3.00003ptadjacent\hskip
3.00003ptto}\hskip 3.00003pt{v_{k}}\\\ 0&\mathrm{otherwise}\end{cases}$

where $L>K_{q}$; further, we set $P_{\mathrm{max}}=1$ and
$\hat{\sigma}_{k}=L$. The vertices $v_{,}\ldots,v_{K-K_{q}}$ can be thought of
as cell-center users as they are exempt from interference effects and are
therefore capable of achieving the highest rates; on the other hand, users
represented by vertices $v_{K-K_{q}+1},\ldots,v_{K}$ can be thought of as a
cell-edge users as they both create interference to, and receive interference
from, adjacent vertices within component $\mathcal{C}_{K-K_{q}+1}$. We claim
that the SLqP rate problem has an optimal value
$f_{\mathrm{opt}}=\left|I_{\mathcal{C}_{K-K_{q}+1}}\right|\mathrm{log}\left(1+\frac{1}{L}\right)$
if and only if the subgraph induced by the component $\mathcal{C}_{K-K_{q}+1}$
has a maximum independent set of size
$\left|I_{\mathcal{C}_{K-K_{q}+1}}\right|$.

Figure 8: Network interference dynamics for a constructed instance of the SLqP
problem with $K=10$ and $K_{q}=5$. Nodes (i.e., users) that are connected
mutually interfere. The users indicated in green transmit at the maximum
available power to achieve the highest SLqP ($q=50$) rate.

For achievability, we note that if the subgraph induced by the component
$\mathcal{C}_{K-K_{q}+1}$ has a maximum independent set of size
$\left|I_{\mathcal{C}_{K-K_{q}+1}}\right|$, then we can set

$p_{k}=\begin{cases}1&\mathrm{if}\hskip
3.00003pt{k=1,\ldots,K-K_{q}}\mathrm{\hskip 3.00003ptor\hskip
3.00003pt}{v_{k}\in I_{\mathcal{C}_{K-K_{q}+1}}}\\\
0&\mathrm{otherwise}\end{cases}$

yielding an objective value of
$\left|I_{\mathcal{C}_{K-K_{q}+1}}\right|\mathrm{log}\left(1+\frac{1}{L}\right)$.

$\displaystyle\underset{\mathbf{p}}{\mathrm{max}}\;f_{K_{q}}\left(\mathrm{log}\left(1+\frac{A_{1}\left(\mathbf{p}\right)}{B_{1}\left(\mathbf{p}\right)}\right),\ldots,\mathrm{log}\left(1+\frac{A_{K}\left(\mathbf{p}\right)}{B_{K}\left(\mathbf{p}\right)}\right)\right)\hskip
282.40056pt$ (30a)
$\displaystyle=\underset{\mathbf{p}}{\mathrm{max}}\;f_{K_{q}}\left(\mathrm{log}\left(\underset{x_{1}}{\mathrm{max}}\;\left\\{1+2x_{1}\sqrt{A_{1}\left(\mathbf{p}\right)}-\left(x_{1}\right)^{2}B_{1}\left(\mathbf{p}\right)\right\\}\right),\ldots,\mathrm{log}\left(\underset{x_{K}}{\mathrm{max}}\;\left\\{1+2x_{K}\sqrt{A_{K}\left(\mathbf{p}\right)}-\left(x_{K}\right)^{2}B_{K}\left(\mathbf{p}\right)\right\\}\right)\right)\hskip
4.40002pt$ (30b)
$\displaystyle=\underset{\mathbf{p}}{\mathrm{max}}\;f_{K_{q}}\left(\underset{x_{1}}{\mathrm{max}}\;\left\\{\mathrm{log}\left(1+2x_{1}\sqrt{A_{1}\left(\mathbf{p}\right)}-\left(x_{1}\right)^{2}B_{1}\left(\mathbf{p}\right)\right)\right\\},\ldots,\underset{x_{K}}{\mathrm{max}}\;\left\\{\mathrm{log}\left(1+2x_{K}\sqrt{A_{K}\left(\mathbf{p}\right)}-\left(x_{K}\right)^{2}B_{K}\left(\mathbf{p}\right)\right)\right\\}\right)\hskip
11.19997pt$ (30c)
$\displaystyle=\underset{\mathbf{x},\mathbf{p}}{\mathrm{max}}\;f_{K_{q}}\left(\mathrm{log}\left(1+2x_{1}\sqrt{A_{1}\left(\mathbf{p}\right)}-\left(x_{1}\right)^{2}B_{1}\left(\mathbf{p}\right)\right),\ldots,\mathrm{log}\left(1+2x_{K}\sqrt{A_{K}\left(\mathbf{p}\right)}-\left(x_{K}\right)^{2}B_{K}\left(\mathbf{p}\right)\right)\right)\hskip
74.80019pt$ (30d)

For the converse, suppose that we are given an optimal value
$f_{\mathrm{opt}}$. Observe that since the vertices
$v_{1},v_{2},\ldots,v_{K-K_{q}}$ are isolated they neither experience nor
create interference; therefore, the SLqP objective is non-decreasing in
$p_{1},p_{2},\ldots,p_{K-K_{q}}$ and these users achieve the $K-K_{q}$ highest
rates in the network. Thus, we can assume that $p_{k}=1$ for
$k=1,\ldots,K-K_{q}$ without loss of generality.

It follows that the SLqP rate on the given graph is therefore equivalent to
the sum-rate achieved on the subgraph induced by $\mathcal{C}_{K-K_{q}+1}$.
The rest of the derivation follows from the proof of Theorem 1 in [18].
Denoting the sum-rate achieved on component $\mathcal{C}_{K-K_{q}+1}$ as
$f_{K_{q}}^{\mathcal{C}_{K-K_{q}+1}}$, we can compute its second derivative
with respect to $p_{k}$ as:

$\frac{\partial{{}^{2}}f_{K_{q}}^{\mathcal{C}_{K-K_{q}+1}}}{\partial
p_{k}^{2}}=-\frac{1}{\left(p_{k}+L+LK_{q}^{2}\sum_{\left(v_{k},v_{j}\right)\in\mathcal{C}_{K-K_{q}+1}}p_{j}\right)^{2}}\\\
+\sum_{\left(v_{k},v_{j}\right)\in\mathcal{C}_{K-K_{q}+1}}\frac{1}{\left(K_{q}^{-2}+\sum_{\left(v_{k},v_{j}\right)\in\mathcal{C}_{K-K_{q}+1}}p_{j}\right)^{2}}$
(31)

Since each component of the graph is connected (by definition), the summation
in the second term of (31) is non-zero. Further, since $L>K_{q}$, the diagonal
terms of the Hessian of the sum-rate on the subgraph induced by
$\mathcal{C}_{K-K_{q}+1}$ (as given in (31)) are non-negative. Thus, the
objective is convex with respect to each individual power variable (although
not jointly convex). The maximum of a convex function over a polyhedron is
attained at the extreme points of the set. It follows that the optimal power
vector $\mathbf{p^{*}}$ must be a binary vector. Now define

$P_{\mathcal{C}_{K-K_{q}+1}}^{*}\coloneqq\left\\{v_{k}\in\mathcal{C}_{K-K_{q}+1}\left|p_{k}=1\right.\right\\}$

Let $\left|I_{\mathcal{C}_{K-K_{q}+1}}\right|$ be the maximum independent set
in $\mathcal{C}_{K-K_{q}+1}$. Using the fact that the first $K-K_{q}$ users
attain the maximum rates in the network, we can write the SLqP rate objective
equivalently as the sum-rate achieved over $\mathcal{C}_{K-K_{q}+1}$.

Define $\mathcal{E}_{K-K_{q}+1}$ as the set of connected vertices in
$\mathcal{C}_{K-K_{q}+1}$, i.e.,

$\mathcal{E}_{K-K_{q}+1}\coloneqq\left\\{v_{j}\in\mathcal{C}_{K-K_{q}+1}\left|\left(v_{j},v_{k}\right)\in
E\right|\right\\}$ (32)

It follows that the sum-rate (and hence optimal SLqP rate objective) over
$\mathcal{C}_{K-K_{q}+1}$ can be bounded according to the procedure given in
[18] as:

$\displaystyle
f^{\mathrm{opt}}=\sum_{v_{k}\in\mathcal{C}_{K-K_{q}+1}}\mathrm{log}\left(1+\frac{1}{L+LK_{q}^{2}\left|\left\\{\left(v_{j},v_{k}\right)\in\mathcal{E}_{K-K_{q}+1}\right\\}\right|}\right)\hskip
47.7001pt$ (33a)
$\displaystyle<\left|I_{\mathcal{C}_{K-K_{q}+1}}\right|\mathrm{log}\left(1+\frac{1}{L}\right)\hskip
166.50027pt$ (33b)

We observe that the number of nodes in the subgraph induced by
$\mathcal{C}_{K-K_{q}+1}$ is exactly $K_{q}$, which grows linearly with the
number of nodes $K$ for a fixed value of $q\geq\frac{200}{K}$. Thus, it
follows that the SLqP rate is strongly NP-hard since the maximum independent
set problem is strongly NP-hard.

Note that the given proof does not hold for the max-min-rate problem; for
$K_{q}=1$ all vertices are isolated and the maximum independent set is $V$
itself. This result is to be expected, since as mentioned earlier, the max-
min-rate power allocation problem can be solved to optimality in polynomial
time [18]. $\blacksquare$

##  Appendix B Proof of Theorem 2

Here we present the proof for the equivalence of the interference-limited SLqP
rate maximization problem in (13) with the problem in (18). The equivalence
can be seen by considering the chain of reasoning in (30a)–(30d).
Specifically, (30b) follows from the result in Theorem (1); (30c) follows
since $\mathrm{log}\left(\cdot\right)$ is a non-decreasing function, so we can
move the $\mathrm{max}\left(\cdot\right)$ operator outside it; (30d) follows
since $f_{K_{q}}\left(\cdot\right)$ is non-decreasing in each component, so we
can move the $\mathrm{max}\left(\cdot\right)$ operators corresponding to each
component outside it. $\blacksquare$

##  Appendix C Proof of Theorem 4

We begin by reviewing the MM framework as described in [45]. Consider the
optimization problem

$\displaystyle\underset{\mathbf{p^{\mathit{}}}}{\mathrm{maximize}}\quad
f\left(\mathbf{p}\right)\hskip 54.3pt$ (34a)
$\displaystyle\mathrm{subject\,to}\quad\mathbf{p}\in\mathcal{P}\hskip 49.0pt$
(34b)

where $f\left(\mathbf{p}\right):\mathbb{R}^{n}\mapsto\mathbb{R}$ is continuous
(but not necessarily either smooth or convex), and
$\mathcal{P}\subseteq\mathbb{R}^{n}$ is non-empty, closed and convex.

The MM procedure as applied to this problem consists of two alternating steps.
At the $i^{\mathrm{th}}$ iteration, a feasible point
$\mathbf{p}\left[i\right]\in\mathcal{P}$ (initialized with some choice of
$\mathbf{p}\left[1\right]\in\mathcal{{P}}$) is used to construct a minorizing
function $g\left(\mathbf{p}\left|\mathbf{p}\left[i\right]\right.\right)$ such
that

$g\left(\mathbf{p}\left|\mathbf{p}\left[i\right]\right.\right)+c\left[i\right]\leq
f\left(\mathbf{p}\right)\;\forall\mathbf{p}\in\mathcal{P}$

where

$c\left[i\right]=f\left(\mathbf{p}\left[i\right]\right)-g\left(\mathbf{p}\left[i\right]\left|\mathbf{p}\left[i\right]\right.\right)$
(35)

Next, the minorizing function is maximized to obtain the next feasible
iteration point $\mathbf{p}\left[i+1\right]$ as follows:

$\mathbf{p}\left[i+1\right]\in\mathrm{arg}\,\underset{\mathbf{p}\in\mathcal{P}}{\mathrm{max}}\quad
g\left(\mathbf{p}\left|\mathbf{p}\left[i\right]\right.\right)$

Furthermore, define the set of directional stationary points as

$\mathcal{P}^{*}=\left\\{\mathbf{p}\left|f^{\prime}\left(\mathbf{p}\left[i\right],\mathbf{d}\right)\leq
0\quad\forall\left(\mathbf{p}+\mathbf{d}\right)\in\mathcal{P}\right.\right\\}$

where $f^{\prime}\left(\mathbf{p},\mathbf{d}\right)$ denotes the directional
derivative of $f$ in the direction $\mathbf{p}$ and is given by

$f^{\prime}\left(\mathbf{p}\left[i\right],\mathbf{d}\right)=\mathrm{lim}\,\underset{t\downarrow
0}{\mathrm{inf}}\;\frac{f\left(\mathbf{p}\left[i\right]+t\mathbf{d}\right)-f\left(\mathbf{p}\left[i\right]\right)}{t}$

When $f$ is non-smooth, the MM procedure is guaranteed to converge to a point
within $\mathcal{P}^{*}$ if the following conditions are satisfied [45]:

  1. 1.

The superlevel set $\mathcal{S}_{\geq
f\left(\mathbf{p}_{0}\right)}=\left\\{\mathbf{p}\in\mathcal{P}\left|f\left(\mathbf{p}\right)\geq
f\left(\mathbf{p}_{0}\right)\right.\right\\}$ is compact given that
$f\left(\mathbf{p}_{0}\right)>-\infty$.

  2. 2.

The directional derivatives of $f$ and $g$ are identical for all directions
$\mathbf{d}$ over $\mathcal{{P}}$, i.e.,

$f^{\prime}\left(\mathbf{p}\left[i\right],\mathbf{d}\right)=g^{\prime}\left(\mathbf{p}\left[i\right];\mathbf{d}\left|\mathbf{p}\left[i\right]\right.\right)\quad$

  3. 3.

$g\left(\mathbf{p}\left|\mathbf{p}\left[i\right]\right.\right)$ is continuous
in both $\mathbf{p}$ and $\mathbf{p}\left[i\right]$.

We now demonstrate that the proposed QFT and LFT algorithms are MM algorithms
and satisfy these convergence conditions.

Consider the auxiliary objective for the QFT algorithm in (18a); we henceforth
denote it by $f_{K_{q}}^{\mathrm{QFT}}\left(\mathbf{p},\mathbf{x}\right)$. We
note that the optimal auxiliary variables $\mathbf{x}$ obtained from (21) are
a function of $\mathbf{p}$; hence, we denote them subsequently as
$\mathbf{x}_{\mathrm{opt}}\left(\mathbf{p}\right)$.

Then it follows that for all $\mathbf{p}\left[i\right]\in{\mathcal{P}}$, we
must have

$f_{K_{q}}^{\mathrm{QFT}}\left(\mathbf{p},\mathbf{x}_{\mathrm{opt}}\left(\mathbf{p}\left[i\right]\right)\right)\leq
f_{K_{q}}^{\mathrm{QFT}}\left(\mathbf{p},\mathbf{x}_{\mathrm{opt}}\left(\mathbf{p}\right)\right)=f_{Kq}\left(\mathbf{p}\right)$
(36)

The inequality follows since the auxiliary objective
$f_{K_{q}}^{\mathrm{QFT}}\left(\mathbf{p},\mathbf{x}\right)$ is maximized when
the auxiliary variables are updated according to (21) for the given fixed
value of $\mathbf{p}$ rather than for $\mathbf{p}\left[i\right]$. The equality
holds since the update of the auxiliary variable defined in (21) preserves
equality with the original objective function. Thus, it follows that the
auxiliary objective
$f_{K_{q}}^{\mathrm{QFT}}\left(\mathbf{p},\mathbf{x}\right)$ minorizes
$f_{K_{q}}\left(\mathbf{p}\right)$.

Having established that the QFT algorithm is indeed an MM algorithm, we now
proceed to verify the conditions in (C) to guarantee convergence to a
directional stationary point.

  1. 1.

For Problem (13), the set $\mathcal{P}=\left[0,P_{\mathrm{max}}\right]^{K}$ is
non-empty, closed, and convex. Next, observe that the SLqP objective in (13a)
is trivially upper bounded by the interference-free SLqP rate which, in turn,
is upper bounded by the interference-free sum-rate from Property 7. Thus,
denoting the optimal value of Problem (13) as $f_{K_{q},\mathrm{opt}}$, we
must have

$f_{K_{q},\mathrm{opt}}\leq
K{\underset{k=1,\ldots,K}{\mathrm{max}}\mathrm{log}}\left(1+\frac{P_{\mathrm{max}}\left|h_{k\rightarrow
k}\right|^{2}}{\sigma^{2}}\right)$

Taken together with the compactness of $\mathcal{P}$, the continuity and
boundedness of the objective in (13a) imply that the superlevel sets of
Problem (13) are compact.

  2. 2.

We observe that (36) implies that $c\left[i\right]=0$ in (35); hence, the
auxiliary objective is a so-called tangent minorant [46]. In particular, this
implies that the directional derivative of
$f_{K_{q}}^{\mathrm{QFT}}\left(\mathbf{p},\mathbf{x}\right)$ equals that of
$f_{K_{q}}\left(\mathbf{p}\right)$ at $\mathbf{p}=\mathbf{p}\left[i\right]$
[46].

  3. 3.

We note that $\hat{r}_{k}$ in (19) is a continuous function of both
$\mathbf{p}$ and $\mathbf{x}$ for all $k$. Since the SLqP utility function is
continuous and the composition of two continuous functions is also continuous,
it follows that the auxiliary QFT objective is also continuous.

Taken together, these conditions imply the convergence of the QFT algorithm to
a directional stationary point of Problem (13). An identical series of
arguments can be utilized for the LFT algorithm. $\blacksquare$