Dual methods for nonconvex spectrum optimization of multicarrier systems

TLDR

Multicarrier communication system design typically maximizes throughput under resource constraints, yet the problem is numerically challenging when nonconvex. The study shows that the time‑sharing condition guarantees zero duality gap for nonconvex multicarrier spectrum optimization and proposes a low‑complexity iterative algorithm that achieves near‑optimal performance. The approach establishes zero duality gap via the time‑sharing condition and suggests approximate evaluation of the dual objective, enabling efficient dual‑domain algorithms. The authors verify that the time‑sharing condition holds in practical multi‑user spectrum optimization as carriers increase, leading to efficient dual‑domain algorithms, and demonstrate that the DSL optimal spectrum‑balancing algorithm is a dual method whose reinterpretation yields faster dual updates and near‑optimal performance.

Abstract

The design and optimization of multicarrier communications systems often involve a maximization of the total throughput subject to system resource constraints. The optimization problem is numerically difficult to solve when the problem does not have a convexity structure. This paper makes progress toward solving optimization problems of this type by showing that under a certain condition called the time-sharing condition, the duality gap of the optimization problem is always zero, regardless of the convexity of the objective function. Further, we show that the time-sharing condition is satisfied for practical multiuser spectrum optimization problems in multicarrier systems in the limit as the number of carriers goes to infinity. This result leads to efficient numerical algorithms that solve the nonconvex problem in the dual domain. We show that the recently proposed optimal spectrum balancing algorithm for digital subscriber lines can be interpreted as a dual algorithm. This new interpretation gives rise to more efficient dual update methods. It also suggests ways in which the dual objective may be evaluated approximately, further improving the numerical efficiency of the algorithm. We propose a low-complexity iterative spectrum balancing algorithm based on these ideas, and show that the new algorithm achieves near-optimal performance in many practical situations.