Parallel and Distributed Methods for Nonconvex Optimization-Part II: Applications

Gesualdo Scutari, Francisco Facchinei, Lorenzo Lampariello, Peiran Song, Stefania SardellittiarXiv 2016 · DOI · OpenReview

TL;DR

This paper presents a novel framework for solving complex, non-convex optimization problems common in wireless communications. It introduces distributed algorithms that outperform existing methods in terms of solution quality and convergence, specifically for rate maximization and multicast beamforming in multi-cell networks.

What Problem Does This Paper Address?

Modern wireless communication systems, especially those with dense deployments like 5G, face significant challenges in resource allocation. Problems like maximizing data rates in interference-heavy environments (MIMO interference broadcast networks) and ensuring fair resource distribution for multicast services (max-min fair multicast multigroup beamforming) are inherently non-convex. This non-convexity makes them notoriously difficult to solve optimally, and existing methods often struggle with convergence guarantees, computational complexity, or the ability to operate in a distributed manner across multiple base stations. This paper aims to bridge this gap by providing a unified algorithmic framework that can handle these complex problems, offering provable convergence to desirable solutions and enabling distributed computation.

Methods

The core of the paper builds upon a framework introduced in Part I, which relies on iteratively solving strongly convex inner approximations of the original non-convex problem. For the specific applications in Part II, the authors develop new convex approximations for the non-convex rate and beamforming constraints.

Key methodological contributions include:

  • Novel Convex Approximations: For the rate profile maximization problem, they introduce a method to approximate the non-convex rate constraints using a combination of concave and convex parts, allowing for linearization of the convex terms. For multicast beamforming, they reformulate the problem by introducing slack variables and then apply convex approximations to the resulting non-convex constraints.
  • Distributed Algorithm Design: A significant innovation is the development of distributed algorithms. By exploiting the structure of the convex subproblems, they show how computations can be decomposed and performed across multiple base stations with limited communication overhead. This is achieved through techniques like dual decomposition.
  • Provable Convergence: Unlike many existing relaxation-based methods (e.g., semidefinite relaxation), the proposed algorithms are proven to converge to "d-stationary" solutions of the original non-convex problems, which are a desirable class of solutions.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical simulations using synthetic network models.

Key Insights and Ideas

  • Unified Framework for Diverse Problems: The paper demonstrates that a single algorithmic framework (NOVA) can effectively tackle two distinct, challenging non-convex optimization problems in wireless communications.
  • Distributed Computation is Achievable and Beneficial: The development of distributed algorithms for these complex problems is a major step forward. It not only aligns with the decentralized nature of modern networks but also shows comparable or better performance than centralized approaches.
  • Beyond Relaxation: Provable Optimality Guarantees: The algorithms guarantee convergence to d-stationary solutions, a stronger guarantee than what many existing relaxation-based methods offer, which may only converge to feasible points or stationary points of related relaxed problems.
  • Flexibility in Constraints and Objectives: The framework is shown to be adaptable to various additional constraints (e.g., per-antenna power limits, null constraints) and objective functions (e.g., weighted sum-rate, geometric mean rates), highlighting its broad applicability.

Key Results

  • Improved Performance: Numerical simulations show that the proposed distributed algorithms achieve higher worst-case rates (for rate profile maximization) and better signal-to-interference-plus-noise ratios (SINRs) compared to state-of-the-art centralized methods and relaxation-based approaches like SDR-G.
  • Comparable Complexity: Despite offering better solutions and distributed capabilities, the computational complexity of the proposed methods is comparable to existing centralized algorithms.
  • Faster Convergence (with Second-Order Methods): While first-order distributed methods show good performance, exploiting second-order information in the dual problem significantly accelerates practical convergence.
  • Significant Gains over SDR-G: For multicast beamforming, the proposed methods achieved SINRs that were, on average, about four times higher than SDR-G, with a much smaller gap to the SDP upper bound.

Limitations and Future Work

  • Assumptions: The framework relies on certain assumptions about the objective and constraint functions (e.g., smooth, Lipschitz gradients), which are standard in optimization but might limit direct application to problems violating these.
  • Distributed Implementation Details: While the framework is distributed, some aspects like updating multipliers might require coordination mechanisms (e.g., a BS header or consensus-like schemes), which could introduce communication overhead.
  • Future Work: The authors suggest that their framework can be readily applied to other unsolved problems, such as distributed minimization of transmit power subject to rate constraints and maximization of multicast capacity in multi-cell systems. They also point to potential applications in signal processing, smart grids, and machine learning.

Summary updated

Abstract

In Part I of this paper, we proposed and analyzed a novel algorithmic framework for the minimization of a nonconvex (smooth) objective function, subject to nonconvex constraints, based on inner convex approximations. This Part II is devoted to the application of the framework to some resource allocation problems in communication networks. In particular, we consider two non-trivial case-study applications, namely: (generalizations of) i) the rate profile maximization in MIMO interference broadcast networks; and the ii) the max-min fair multicast multigroup beamforming problem in a multi-cell environment. We develop a new class of algorithms enjoying the following distinctive features: i) they are \emph{distributed} across the base stations (with limited signaling) and lead to subproblems whose solutions are computable in closed form; and ii) differently from current relaxation-based schemes (e.g., semidefinite relaxation), they are proved to always converge to d-stationary solutions of the aforementioned class of nonconvex problems. Numerical results show that the proposed (distributed) schemes achieve larger worst-case rates (resp. signal-to-noise interference ratios) than state-of-the-art centralized ones while having comparable computational complexity.
BibTeX
@misc{scutari2016parallel,
  author = {Gesualdo Scutari and Francisco Facchinei and Lorenzo Lampariello and Peiran Song and Stefania Sardellitti},
  title = {{Parallel and Distributed Methods for Nonconvex Optimization-Part II: Applications}},
  year = {2016},
  eprint = {1601.04059},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1601.04059},
}
Figure