Source-linked AI summary
Fast Converging Algorithm for Weighted Sum Rate Maximization in Multicell MISO Downlink
Le-Nam Tran, Muhammad Fainan Hanif, Antti Tölli, Markku Juntti
TL;DR
Weighted sum rate maximization in multicell MISO downlink is NP-hard. The paper develops an iterative SOCP procedure based on successive convex approximation, obtaining a fast-converging local solution that generally outperforms known approaches in convergence rate, while global optimality remains unestablished.
Problem
WSRM in multicell MISO downlink is NP-hard, making globally optimal designs impractical because their complexity grows exponentially with problem size.
Method
The paper approximates WSRM through an iterative second-order cone program based on successive convex approximation.
Results
The algorithm converges within a few iterations to a locally optimal point and generally performs better than known approaches, particularly in convergence rate.
Takeaways & Limitations
The proposed procedure provides a low-complexity local solution for WSRM with faster convergence than previously studied solutions.
Takeaways & Limitations
The algorithm's convergence can be proved, but its global optimality cannot be established.
Abstract
from arXiv · showhide
The problem of maximizing weighted sum rates in the downlink of a multicell environment is of considerable interest. Unfortunately, this problem is known to be NP-hard. For the case of multi-antenna base stations and single antenna mobile terminals, we devise a low complexity, fast and provably convergent algorithm that locally optimizes the weighted sum rate in the downlink of the system. In particular, we derive an iterative second-order cone program formulation of the weighted sum rate maximization problem. The algorithm converges to a local optimum within a few iterations. Superior performance of the proposed approach is established by numerically comparing it to other known solutions.
I. INTRODUCTION
Weighted sum rate maximization in multicell MISO downlink is NP-hard, motivating computationally conducive suboptimal methods. The paper proposes an SCA-based iterative SOCP algorithm that locally optimizes WSRM and converges quickly.
- Motivation: WSRM with linear transmit precoding in multicell MISO downlink is NP-hard, making globally optimal designs computationally impractical.Optimal-design complexity grows exponentially with problem size.
- Related approaches: Necessary-optimality-based suboptimal designs can perform close to optimal designs, but existing iterative approaches lack provable convergence or converge more slowly.The cited prior methods include KKT-based coordinated beamforming and alternating optimization.
- Proposed method: The proposed algorithm uses successive convex approximation to replace the nonconvex WSRM problem with an efficiently solvable convex program at each iteration.Proper transformations yield a second-order cone program in each SCA step.
- Results: The algorithm converges within a few iterations to a locally optimal WSRM point.The paper reports numerical results showing convergence to a locally optimal point.
- Results: Numerical results show that the proposed algorithm generally outperforms known approaches, particularly in convergence rate.The comparison specifically reports faster convergence than previously studied methods.
II. PROBLEM FORMULATION
The paper formulates WSRM for coordinated multicell MISO downlink with per-base-station power constraints and single-base-station service for each user. Because the resulting problem is NP-hard, it targets a low-complexity local solution satisfying necessary optimality conditions.
- System model: The system contains B coordinated base stations with N transmit antennas each and K single-antenna receivers.Each user is assigned to a serving base station, and users served by the same base station form its user set.
- Signal model: Each user receives a beamformed data signal from one base station over flat-fading channels with complex Gaussian noise.The received signal includes the desired transmission, interference, and noise.
- Signal model: Interference includes both intra-cell and inter-cell contributions from transmissions intended for other users.The interference term aggregates signals from all non-target users.
- Optimization problem: The objective is WSRM under per-base-station power constraints, with positive user weights that can maintain a degree of fairness.The weights are introduced to reflect user priorities or fairness considerations.
- Optimization problem: Because the formulation is NP-hard, global optimality is mainly a theoretical benchmark, so the paper proposes a low-complexity local algorithm satisfying necessary optimality conditions.The proposed design locally solves the optimization problem rather than establishing a global optimum.
III. PROPOSED LOW-COMPLEXITY BEAMFORMER DESIGN
The proposed beamformer design transforms weighted sum-rate maximization into an iterative SOCP by convexly approximating nonconvex constraints and updating auxiliary variables. The resulting algorithm is designed for low complexity and converges to a KKT point of the reformulated problem.
- Problem reformulation: The weighted sum-rate formulation is transformed into an equivalent problem using slack variables and constraints suitable for successive convex approximation.The reformulation introduces β_k and separates nonlinear constraints before constructing the SOCP.
- Successive approximation: A nonconvex constraint is replaced by a convex upper bound parameterized by φ_k, enabling an SOC representation.For fixed φ_k > 0, G(x_k, β_k, φ_k) is a convex overestimate of f(x_k, β_k).
- Successive approximation: The weighted exponents α_k are scaled so the remaining constraint becomes convex or concave as required for linearization.Scaling all α_k by the same positive constant preserves the optimal solution, allowing the algorithm to impose the needed curvature.
- Successive approximation: The concave term is linearized around its value at the current iteration, producing a linear inequality that preserves the required approximation conditions.The approximation uses the current t_k value and replaces the nonlinear constraint with its first-order upper bound.
- Complexity and performance: The successive approximation with α_k > 1 produces identical WSR to the convex alternative while requiring lower computational effort.The lower effort comes from replacing the original nonlinear equality with a linear inequality.
- SOCP formulation: The resulting formulation is an SOCP because the product objective admits an SOC representation based on hyperbolic constraints.The construction collects variables pairwise and adds auxiliary variables when K is not a power of two.
- Algorithm: Algorithm 1 iteratively solves the SOCP while updating approximation variables, yielding a locally optimized beamformer design.The procedure is presented as a proposed beamformer design for the multicell MISO downlink WSRM problem.
P (dBW)
The algorithm generates a nondecreasing sequence of objective values bounded above by the power constraints, and therefore converges to a local optimum satisfying the KKT conditions. Numerical results further report performance very close to optimal linear design.
- Convergence: Each new SOCP iterate remains feasible for the next iteration, so the objective value is nondecreasing.The nth-iteration solution is feasible for the n + 1st problem.
- Convergence: Power constraints provide an upper bound, implying convergence of Algorithm 1 to a local optimum.The converged solution also satisfies the KKT conditions of the reformulated problem.
- Numerical comparison: Algorithm 1 performs very close to optimal linear design in the reported numerical comparison.The comparison concerns average sum rate in the single-cell scenario with N = 4 and K = 4.
IV. NUMERICAL RESULTS
The numerical evaluation compares Algorithm 1 with iterative suboptimal methods, WMMSE, SIN, zero-forcing, and an optimal linear design across weighted-sum-rate and convergence experiments. Algorithm 1 reaches comparable converged sum rates while generally converging faster and requiring less per-iteration time than SIN.
- Algorithm 1 and other iterative beamformer designs achieve the same average sum rate at convergence, close to the optimal linear approach.
- WMMSE, the SIN scheme, and the optimal design exhibit slower convergence rates than the proposed algorithm in the convergence comparison.
- Algorithm 1 converges after only a few iterations, whereas WMMSE may require hundreds of runs to reach the local optimum.For one random channel realization, WMMSE remained below midway to convergence while Algorithm 1 had already converged.
- The scaled and unscaled formulations have slightly different convergence rates but achieve the same optimal value, supporting the approximation’s lack of impact on sum rate.
- Algorithm 1’s average per-iteration running time is approximately four times lower than SIN’s, although SIN can show similar convergence behavior for some channel realizations.
- Algorithm 1’s faster convergence is attributed to solving an explicit SOCP at each iteration.
V. CONCLUSION
The paper addresses NP-hard weighted sum-rate maximization in multicell MISO downlinks with a low-complexity iterative SOCP approximation. The algorithm has provable convergence and outperforms previously studied solutions, but global optimality is not established.
- The paper proposes a low-complexity approximation for the NP-hard weighted sum-rate maximization problem.
- The approximation is implemented as an iterative second-order cone programming procedure.
- The algorithm’s convergence can be proved, but its global optimality cannot be established.
- Numerically, the algorithm outperforms previously studied weighted-sum-rate solutions, particularly in convergence-related performance.