Ferkans — Interactive Telecom Tutor

The Hardest Fairness Criterion

Sum-rate maximization — choosing powers to maximize $\sum_k R_k$ — is the most natural objective from a throughput perspective but also the most challenging to optimize. Unlike max-min fairness (quasi-concave) and proportional fairness (GP-amenable), the sum-rate objective is non-concave in the power vector due to the interference coupling. This section develops two powerful algorithmic frameworks: successive convex approximation (SCA) and the weighted minimum mean-square error (WMMSE) algorithm.

Definition:
Weighted Sum-Rate Maximization

The weighted sum-rate maximization (WSRMax) problem is

$\max_{\mathbf{p} \geq \mathbf{0}} \; \sum_{k=1}^{K} w_k \log_2\!\left(1 + \text{SINR}_k(\mathbf{p})\right) \quad \text{s.t.} \quad \sum_{k=1}^{K} p_k \leq P_t$

where $w_k > 0$ are user-specific weights. When $w_k = 1$ for all $k$ , this is the unweighted sum-rate problem. By varying the weights, one can trace the boundary of the achievable rate region.

The weights $w_k$ can encode priority (premium users get higher weight), queue state (users with more buffered data get higher weight), or fairness constraints (setting $w_k \propto 1/\bar{R}_k$ approximates proportional fairness).

Theorem: NP-Hardness of Sum-Rate Maximization

The weighted sum-rate maximization problem with interference is NP-hard in general. Specifically, even for the two-user interference channel with single-antenna nodes, the problem of finding the power allocation maximizing $w_1 R_1 + w_2 R_2$ is NP-hard when both users have non-zero interference coupling.

The difficulty arises from the non-concavity of the sum-rate function. Increasing $p_k$ improves $R_k$ (more signal) but hurts $R_l$ for $l \neq k$ (more interference). This creates a landscape with potentially many local maxima, and no polynomial-time algorithm is known to find the global optimum.

Proof

Reduction from MAX-CUT

Luo and Zhang (2008) showed that the sum-rate maximization problem for a $K$ -user interference channel can encode an instance of MAX-CUT on a weighted graph. Since MAX-CUT is NP-hard, the reduction establishes NP-hardness of the power control problem.

Implication for massive MIMO

In massive MIMO, the effective interference coupling $\gamma_{kl}$ is typically much smaller than the desired signal $a_k$ (favorable propagation). This makes the problem "closer to concave" in practice, and local methods often find near-optimal solutions. However, no polynomial-time algorithm guarantees global optimality. $\blacksquare$

Successive Convex Approximation (SCA)

An iterative optimization technique that replaces a non-convex problem with a sequence of convex subproblems. Each subproblem is constructed by approximating the non-convex parts with concave lower bounds, and the iterates provably converge to a stationary point of the original problem.

Related: WMMSE Algorithm

Definition:
Successive Convex Approximation for Sum-Rate

The SCA approach to WSRMax works by lower-bounding the concave part of $R_k$ and linearizing the interference term. At iteration $n$ , given the current powers $\mathbf{p}^{(n)}$ , we solve

$\max_{\mathbf{p} \geq \mathbf{0}} \; \sum_{k=1}^{K} w_k \tilde{R}_k^{(n)}(\mathbf{p}) \quad \text{s.t.} \quad \sum_k p_k \leq P_t$

where $\tilde{R}_k^{(n)}$ is a concave surrogate of $R_k$ satisfying: (i) $\tilde{R}_k^{(n)}(\mathbf{p}^{(n)}) = R_k(\mathbf{p}^{(n)})$ (tight at current point), (ii) $\nabla \tilde{R}_k^{(n)}(\mathbf{p}^{(n)}) = \nabla R_k(\mathbf{p}^{(n)})$ (matching gradient), and (iii) $\tilde{R}_k^{(n)}(\mathbf{p}) \leq R_k(\mathbf{p})$ for all $\mathbf{p}$ (lower bound). Properties (i)–(iii) guarantee that the sequence $\{\mathbf{p}^{(n)}\}$ converges to a stationary point.

Theorem: Convergence of SCA

Let $\{\mathbf{p}^{(n)}\}_{n \geq 0}$ be the sequence of iterates produced by the SCA algorithm. If the surrogate functions $\tilde{R}_k^{(n)}$ satisfy properties (i)–(iii) above, then:

The objective is non-decreasing: $\sum_k w_k R_k(\mathbf{p}^{(n+1)}) \geq \sum_k w_k R_k(\mathbf{p}^{(n)})$ .
Every limit point of $\{\mathbf{p}^{(n)}\}$ satisfies the KKT conditions of the original WSRMax problem.

The key idea is that each SCA iteration maximizes a lower bound that is tight at the current point. Because the bound is tight, the new iterate achieves at least the same objective value. Because the gradient matches, the stationary points of the surrogates coincide with those of the original problem.

Proof

Monotonicity

By property (iii), $\sum_k w_k R_k(\mathbf{p}^{(n+1)}) \geq \sum_k w_k \tilde{R}_k^{(n)}(\mathbf{p}^{(n+1)})$ . Since $\mathbf{p}^{(n+1)}$ maximizes $\sum_k w_k \tilde{R}_k^{(n)}(\mathbf{p})$ , $\sum_k w_k \tilde{R}_k^{(n)}(\mathbf{p}^{(n+1)}) \geq \sum_k w_k \tilde{R}_k^{(n)}(\mathbf{p}^{(n)})$ . By property (i), the right side equals $\sum_k w_k R_k(\mathbf{p}^{(n)})$ .

Stationarity

At a limit point $\mathbf{p}^\star$ , we have $\mathbf{p}^{(n+1)} = \mathbf{p}^{(n)} = \mathbf{p}^\star$ . The KKT conditions of the surrogate subproblem at $\mathbf{p}^\star$ involve $\nabla \tilde{R}_k^{(\star)}(\mathbf{p}^\star) = \nabla R_k(\mathbf{p}^\star)$ by property (ii), which are exactly the KKT conditions of the original problem. $\blacksquare$

,

Definition:
The WMMSE Algorithm

The Weighted Minimum Mean-Square Error (WMMSE) algorithm is a particular instance of SCA that exploits the SINR–MSE relationship. For user $k$ with receive filter $g_k$ and weight $\mu_k$ , define the MSE

$e_k = \mathbb{E}\left[|g_k y_k - s_k|^2\right] = |g_k|^2 \left(\sum_{l=1}^{K} p_l |\mathbf{v}_k^H \mathbf{H}_{l}|^2 + \sigma^2\right) - 2\text{Re}(g_k \sqrt{p_k} \mathbf{v}_k^H \mathbf{H}_{k}) + 1.$

The WMMSE algorithm alternates between:

Fix $\mathbf{p}$ , update $g_k$ : MMSE receiver $g_k^\star = \frac{\sqrt{p_k}\mathbf{v}_k^H\mathbf{H}_{k}}{\sum_l p_l |\mathbf{v}_k^H\mathbf{H}_{l}|^2 + \sigma^2}$
Fix $g_k$ , update $\mu_k$ : Weight $\mu_k^\star = 1/e_k^\star$ (inverse MSE)
Fix $g_k, \mu_k$ , update $\mathbf{p}$ : Solve a convex quadratic program

This alternating optimization provably converges to a stationary point of the WSRMax problem.

WMMSE Algorithm

The Weighted Minimum Mean-Square Error algorithm for sum-rate maximization. It alternates between updating MMSE receivers, MSE weights, and transmit powers, converging to a KKT point of the weighted sum-rate problem.

WMMSE Algorithm for Weighted Sum-Rate Maximization

Complexity:

O(I \cdot K^{2})

per iteration; typically

I = 10

–

50

iterations to converge

Input: Channel vectors

\{\mathbf{H}_{k}\}

, combining vectors

\{\mathbf{v}_k\}

,

weights

\{w_k\}

, power budget

P_t

, tolerance

\epsilon

Output: Power vector

\mathbf{p}^\star

(stationary point of WSRMax)

1. Initialize

\mathbf{p}^{(0)}

(e.g., equal power)

2. repeat

3.

\quad

for

k = 1, \ldots, K

do

4.

\quad\quad g_k \leftarrow \frac{\sqrt{p_k} \mathbf{v}_k^H \mathbf{H}_{k}}{\sum_l p_l |\mathbf{v}_k^H \mathbf{H}_{l}|^2 + \sigma^2}

(MMSE receiver)

5.

\quad\quad e_k \leftarrow 1 - |g_k|^2 p_k |\mathbf{v}_k^H \mathbf{H}_{k}|^2 / (\sum_l p_l |\mathbf{v}_k^H \mathbf{H}_{l}|^2 + \sigma^2)

6.

\quad\quad \mu_k \leftarrow w_k / e_k

(MSE weight)

7.

\quad

end for

8.

\quad

Solve for

\mathbf{p}

:

\min_{\mathbf{p} \geq 0, \, \mathbf{1}^T\mathbf{p} \leq P_t} \sum_k \mu_k e_k(\mathbf{p}) - w_k \log(\mu_k e_k(\mathbf{p}))

9. until

|\Delta \text{WSR}| < \epsilon

The key insight of WMMSE is the identity $\max_{\mu_k > 0}(w_k \log \mu_k - w_k \mu_k e_k + w_k) = w_k \log(1/e_k^{\min})$ which connects the MSE to the rate. This allows the non-convex rate maximization to be decomposed into alternating convex steps.

Example: WMMSE Convergence for a 4-User System

Consider $N_t = 64$ antennas, $K = 4$ users with random i.i.d. Rayleigh channels, ZF combining, and $\text{SNR} = 10$ dB. Run the WMMSE algorithm from equal-power initialization and compare the converged sum rate to the equal-power baseline.

Solution

Equal-power baseline

With equal power $p_k = P_t/K$ for all $k$ , the sum rate depends on the channel realization. For a typical realization with path losses ranging over 10 dB: $R_{\text{sum}}^{\text{eq}} \approx 18.2$ bits/s/Hz.

WMMSE iterations

After 15 iterations, the WMMSE algorithm converges to $R_{\text{sum}}^{\text{WMMSE}} \approx 21.5$ bits/s/Hz — an 18% improvement. The algorithm shifts power from users with weak effective channels (after ZF processing) to users with strong effective channels.

Convergence behavior

The sum rate increases monotonically at each iteration (guaranteed by the SCA framework). Most of the improvement occurs in the first 5 iterations; the remaining iterations refine the solution by less than 0.1 bits/s/Hz per step.

Common Mistake: WMMSE Finds Local Optima, Not Global

Mistake:

A common error is to trust that the WMMSE algorithm finds the global optimum of the sum-rate problem because it is based on alternating optimization with closed-form updates.

Correction:

WMMSE converges to a stationary point (KKT point) of the sum-rate problem, which is a local optimum or saddle point — not necessarily the global optimum. In practice, running WMMSE from multiple random initializations and taking the best result improves the chance of finding a good solution. For massive MIMO with favorable propagation, the interference coupling is weak and the landscape has few local optima, so a single run usually suffices.

WMMSE Algorithm Convergence

Observe how the weighted sum rate evolves over WMMSE iterations. Compare convergence speed for different numbers of users and antenna counts.

Parameters

K

(users)4

M

(antennas)64

SNR (dB)10

Max iterations30

⚠️Engineering Note

Computational Cost of WMMSE in Real-Time Systems

The WMMSE algorithm requires 10–50 iterations, each involving matrix inversions of size $K \times K$ and a convex power allocation step. For massive MIMO with $K = 16$ users and 1 ms scheduling granularity (5G NR), the algorithm must complete within approximately 100 microseconds on the baseband processor. This is achievable for small $K$ but becomes challenging for dense deployments with 64+ users.

Practical Constraints

•
5G NR scheduling period: 1 ms (2 slots at 30 kHz SCS)
•
Baseband processing budget: typically 100-200 microseconds for power allocation
•
WMMSE with $K = 16$ and 30 iterations: ~50 microseconds on a modern DSP
•
For $K > 32$ , heuristic methods from Section 5.4 are preferred

Quick Check

What is the key mathematical identity that enables the WMMSE algorithm?

The rate $R_k = \log(1 + \text{SINR}_k)$ equals $-\log(e_k^{\min})$ where $e_k^{\min}$ is the MMSE

The sum rate is concave in the power vector under favorable propagation

The interference term can be linearized without loss of optimality

Water-filling is optimal when treating interference as noise

Correction:

The rate

R_k = \log(1 + \text{SINR}_k)

equals

-\log(e_k^{\min})

where

e_k^{\min}

is the MMSE

This identity connects rate maximization to MSE minimization. The WMMSE algorithm exploits this by introducing auxiliary weights $\mu_k$ that decouple the problem into alternating convex steps, each with a closed-form solution.

Key Takeaway

Weighted sum-rate maximization is NP-hard in general but yields to iterative methods. The WMMSE algorithm — which alternates between MMSE receiver updates, weight updates, and convex power allocation — converges to a KKT point and is the standard workhorse for sum-rate optimization in massive MIMO systems.

Sum-Rate Maximization