Ferkans — Interactive Telecom Tutor

Why Worry About Local Minima?

We proved in Section 5.2 that AO converges to a stationary point. But the unit-modulus constraint makes the feasible set non-convex, and non-convex problems generically have multiple stationary points. This section quantifies the local-minimum question: how bad can an AO local optimum be compared with the global, and what does that tell us about the initialization strategy?

Theorem: Worst-Case Gap to Global Optimum

Let $R^\star$ denote the global optimum sum rate, $R_{\text{AO}}$ the AO converged rate (from any feasible initial point), and $R_{\text{SDR}}$ the SDR-relaxed upper bound (Chapter 6). Then

$R_{\text{AO}} \leq R^\star \leq R_{\text{SDR}}.$

Empirical evidence over random channel realizations shows the AO-to-SDR gap is typically $< 5\%$ in sum rate for single-user and $< 10\%$ for $K \leq 4$ users. With 5 random AO initializations and taking the best, the worst-case optimality gap falls to $< 2\%$ in most scenarios.

The SDR relaxation gives an upper bound $R_{\text{SDR}}$ on the global optimum: any relaxed solution is at least as good as the best feasible solution. Together with the AO lower bound $R_{\text{AO}}$ , this sandwiches the global optimum $R^\star$ : $R_{\text{AO}} \leq R^\star \leq R_{\text{SDR}}$ . Empirically, the gap is small — usually $< 1$ dB.

Initialization Strategies That Work

Empirical best practices for AO initialization:

Identity: $\boldsymbol{\Phi}^{(0)} = \mathbf{I}$ . Cheap; works for single-user, mediocre for multi-user.
Random unit-modulus: $\theta_n^{(0)} \sim \text{Unif}[0, 2\pi)$ . Best single-trial performance among cheap initializations.
Strongest-user matched filter: Initialize $\boldsymbol{\phi}^{(0)}$ as matched filter for the single-strongest user. Then the RIS helps that user first; the subsequent iterations fold in the weaker users. Especially effective when user strengths are unbalanced.
Multi-start with best: Run AO from 5-20 random starts, keep the best. Adds a $5$ - $20\times$ compute cost but almost closes the gap to the global optimum.

Strategy (4) is the recommendation for simulation studies and benchmarks; (3) or (2) is the recommendation for real-time operation.

Theorem: Linear Convergence Rate of AO

Suppose $(\mathbf{W}^\star, \boldsymbol{\Phi}^\star)$ is an isolated stationary point with positive-definite block Hessians. Then in a neighborhood of the stationary point,

$\|(\mathbf{W}^{(i+1)}, \boldsymbol{\Phi}^{(i+1)}) - (\mathbf{W}^\star, \boldsymbol{\Phi}^\star)\| \leq \rho\, \|(\mathbf{W}^{(i)}, \boldsymbol{\Phi}^{(i)}) - (\mathbf{W}^\star, \boldsymbol{\Phi}^\star)\|,$

where $0 < \rho < 1$ depends on the off-block-diagonal terms of the Hessian. For well-conditioned RIS problems, $\rho \sim 0.1$ - $0.3$ , i.e., each AO iteration roughly halves the distance to the optimum.

Near a non-degenerate local minimum, each AO iteration reduces the optimality gap by a constant factor less than 1. The rate depends on the "coupling strength" between blocks; weakly coupled problems converge fast.

AO Starting From Multiple Initializations

Run AO from 10 random initializations on the same channel realization and show each convergence trajectory. Most converge to the same local optimum; a few converge to strictly worse local optima. Best-of-10 typically achieves the global optimum within $< 1$ % gap.

Parameters

RIS elements

N

32

BS antennas

N_t

4

Users

K

2

Transmit SNR (dB)15

Number of random initializations10

Example: Characterizing an AO Fixed Point

At an AO fixed point $(\mathbf{W}^\star, \boldsymbol{\Phi}^\star)$ , what are the first-order optimality conditions that both blocks simultaneously satisfy?

Solution

Active-block condition

$\mathbf{W}^\star$ is optimal for $f(\cdot, \boldsymbol{\Phi}^\star)$ subject to power constraint. KKT: there is $\mu^\star \geq 0$ with $\nabla_{\mathbf{W}} f - 2\mu^\star \mathbf{W}^\star = 0$ and $\mu^\star (\text{tr}(\mathbf{W}^{\star H}\mathbf{W}^\star) - P_t) = 0$ .

Passive-block condition

$\boldsymbol{\phi}^\star$ is optimal for $f(\mathbf{W}^\star, \cdot)$ on the unit-modulus torus. The Riemannian gradient $\nabla_{\boldsymbol{\phi}}^{\text{Riem}} f = 0$ , i.e., the Euclidean gradient projected onto the tangent space of the torus is zero. Equivalently, for each $n$ : $\text{Im}\{\phi_n^{\star*} [\nabla_{\boldsymbol{\phi}} f]_n\} = 0$ .

Interpretation

The active-block condition is standard (water-filling / KKT). The passive-block condition is a phase matching: each $\phi_n^\star$ is aligned with the Euclidean gradient component on that element, modulo sign. Jointly these describe a saddle-free coordinate-wise stationary point.

Common Mistake: Monotone Rate Is Not a Substitute for Good Rate

Mistake:

"My AO converged monotonically, so the result is trustworthy."

Correction:

Monotone convergence only tells you AO reached a stationary point, not a good one. Check the gap to an upper bound: SDR-relaxed sum rate, or the single-user coherent-optimum bound $\log_2(1 + P_t N^2 / K / \sigma^2)$ . If the AO output is $> 3\text{ dB}$ below these bounds, try more initializations or a better passive algorithm.

Key Takeaway

AO is the practical workhorse for RIS joint optimization. Each iteration consists of a WMMSE inner loop (active) and a passive update from Chapter 6. 10–30 outer iterations typically suffice for convergence within $\epsilon = 10^{-3}$ . With multiple random initializations, AO delivers rates within $1$ - $5\%$ of the SDR upper bound across a wide range of scenarios. The combination of monotone convergence, tractable sub-problems, and empirical near-optimality make AO the default algorithm — even when more sophisticated global methods exist.

Quick Check

Which of the following is not guaranteed by AO on the joint RIS beamforming problem?

Monotone non-decreasing sum rate

Convergence to a stationary point

Convergence to the global optimum

Finite-iteration termination at any tolerance

Correction:

Convergence to the global optimum

AO converges only to a local stationary point. The global optimum can be missed due to the non-convex unit-modulus constraint. Multiple random initializations help but do not guarantee the global optimum.

Alternating Optimization (AO)

An iterative algorithm for solving joint optimization problems $\min_{(\mathbf{x}, \mathbf{y})} f(\mathbf{x}, \mathbf{y})$ by alternately minimizing over one block while fixing the other. For RIS, $\mathbf{x} = \mathbf{W}$ (BS precoder) and $\mathbf{y} = \boldsymbol{\Phi}$ (RIS phases). Monotone convergence is guaranteed under mild regularity conditions.

WMMSE Algorithm

The Weighted MMSE reformulation of sum-rate maximization, used as the inner loop of RIS AO for the active-beamforming subproblem. Introduces auxiliary combiner and weight variables; each block has a closed-form coordinate update. Converges to a local optimum of the original sum-rate problem.

Historical Note: Block Coordinate Descent: From Gauss-Seidel to AO

1950s–2020s

Alternating optimization is a descendant of the Gauss–Seidel method (1823, for linear systems). Its generalization to non-convex optimization was studied by Powell in the 1970s, and its convergence theory was matured by Bertsekas and Tsitsiklis in the 1980s–1990s. Modern applications — matrix completion, tensor decomposition, dictionary learning — all rely on the same monotone-descent principle.

The RIS community adopted BCD (under the name "alternating optimization" or "AltOpt") in 2019 with the Wu and Zhang paper, which used it as the natural framework for the newly-formulated joint beamforming problem. Since then, essentially every RIS-optimization paper uses AO in some form — often with innovations in one or the other sub-problem, but keeping the outer alternating structure.

⚠️Engineering Note

AO in a Real-Time Controller

A real-time RIS controller running AO between coherence blocks must make time/quality tradeoffs:

Partial AO: Run 3-5 iterations per coherence block, not full convergence. The sub-optimality is small when warm-starting.
Warm-start: Initialize current block's $\boldsymbol{\Phi}$ and $\mathbf{W}$ from previous block's solution. Block-to-block correlation makes this very effective.
Amortized computation: Pre-compute channel-dependent matrices once per coherence block, reuse across inner AO steps.
Graceful degradation: If AO time budget exceeded, fall back to the current best iterate.

Practical Constraints

•
Typical compute budget in a 5G-like system: $\sim 1$ ms per AO iteration at $N = 256, K = 4$ .
•
Total optimization time per coherence block: $< 20$ ms.
•
Warm-start reduces the needed iteration count by $\sim 3\times$ vs. cold-start.

Convergence and Local-Minimum Analysis