Non-convex utility maximization in Gaussian MISO broadcast and interference channels

Marco Rossi, Antonia M. Tulino, Osvaldo Simeone, Alexander M. HaimovichICASSP 2011 · DOI

TL;DR

This paper tackles the challenge of maximizing network utility in complex wireless systems (MISO broadcast and interference channels) where traditional optimization methods fail due to non-convexity. They introduce a novel branch-and-bound algorithm for finding globally optimal solutions and a practical, real-time suboptimal algorithm that generalizes existing pricing schemes.

What Problem Does This Paper Address?

In wireless communication systems, especially those with multiple antennas at the transmitter (MISO) and multiple users (broadcast and interference channels), optimizing performance is crucial for high spectral efficiency. A common goal is to maximize a "utility" function, which could represent things like the sum of user data rates. However, when trying to find the best way to transmit signals (precoding) and control power, the resulting mathematical problems are often "non-convex." This means that standard optimization techniques, which work well for "convex" problems, can get stuck in suboptimal solutions and cannot guarantee finding the absolute best outcome. While some problems are convex, many practical scenarios, like maximizing sum-rate when interference is treated as noise, are known to be NP-hard, implying no efficient (polynomial-time) algorithm exists for a guaranteed global optimum. This paper aims to bridge this gap by providing methods to find optimal or near-optimal solutions for these challenging non-convex problems.

Methods

The paper proposes two main algorithmic approaches:

  • Global Optimization via Branch-and-Bound (BB): This method leverages a specific structure in the utility functions, termed "Partly Convex-Monotone." This structure allows them to efficiently explore the solution space. Instead of branching on all possible signal configurations, they branch on the "interference levels" at the receivers, which is a lower-dimensional space. The bounding steps involve solving convex optimization problems, making the overall BB algorithm more tractable than a general-purpose one. This approach guarantees finding the global optimum, though it's primarily for offline analysis due to its computational complexity.
  • Suboptimal Algorithm (Generalizing Distributed Pricing): For real-time applications, they introduce a polynomial-complexity algorithm. This algorithm is a generalization of the "distributed pricing" schemes previously used for simpler problems. It reformulates the non-convex problem into a minimax problem involving Lagrange multipliers (which can be interpreted as "prices" for interference). The algorithm iteratively updates these prices and signal configurations until convergence to a local optimum. This method is practical for real-time deployment but, like most non-convex optimization algorithms, its performance can depend on the initial starting point.

Datasets

Not discussed in the paper. The paper focuses on theoretical framework and numerical simulations based on defined channel models.

Key Insights and Ideas

  • Partly Convex-Monotone Structure is Key: The authors identify a specific mathematical property ("Partly Convex-Monotone") that many practical utility functions possess. This property is crucial for developing both their global BB algorithm and their suboptimal pricing-based algorithm, enabling them to handle non-convexity more effectively.
  • Branching on Interference, Not Signals: A clever aspect of their BB algorithm is branching in the space of interference levels rather than the full signal covariance space. This significantly reduces the complexity of the search.
  • Generalizing Distributed Pricing: The suboptimal algorithm extends a known technique for simpler wireless problems to a much broader class of non-convex utility maximization problems, offering a practical solution for real-time systems.
  • Initialization Matters for Suboptimal: The numerical results highlight that the performance of the suboptimal algorithm is sensitive to its initial parameters, underscoring the importance of good initialization strategies.

Key Results

The paper demonstrates through numerical simulations (specifically for the sum-rate maximization in a MISO broadcast channel) that:

  • The proposed Branch-and-Bound (BB) algorithm successfully finds the global optimum, providing a benchmark for performance.
  • The suboptimal Algorithm 1 (generalizing distributed pricing) achieves near-optimal performance across various power levels.
  • However, Algorithm 1's performance can degrade significantly at high power levels or specific points if not initialized properly.
  • The non-linear Dirty Paper Coding (DPC) technique, while not a linear precoder, shows significant gains over linear methods at high power regimes, serving as a reference for ultimate performance limits.

Limitations and Future Work

  • Computational Complexity of BB: The global optimization BB algorithm, while efficient for a non-convex problem, is still too complex for real-time implementation.
  • Initialization Sensitivity of Suboptimal Algorithm: The suboptimal algorithm's performance is dependent on initial conditions, which can lead to suboptimal results if not chosen carefully.
  • Future Work: The authors suggest extending their framework to MIMO (Multiple-Input Multiple-Output) networks, which would involve even more complex optimization problems. Further research into robust initialization strategies for the suboptimal algorithm is also implied.

Summary updated

BibTeX
@inproceedings{rossi2011non,
  author = {Marco Rossi and Antonia M. Tulino and Osvaldo Simeone and Alexander M. Haimovich},
  title = {{Non-convex utility maximization in Gaussian MISO broadcast and interference channels}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2011},
  doi = {10.1109/icassp.2011.5946278},
}
Figure