  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.
