Ferkans — Interactive Telecom Tutor

When the Weakest Link Matters

Sum rate is utilitarian; max-min rate is egalitarian. Maximize the rate of the worst-served user, let stronger users share whatever's left. In deployments where every user must meet a quality-of-service threshold — fixed-wireless access, emergency networks, IoT heartbeat — max-min is the right objective. The RIS-aided max-min problem has beautiful structure: via bisection, it becomes a sequence of second-order-cone programs (SOCPs), each solvable to global optimality in polynomial time. This is one of the cleanest RIS optimization results, and it contrasts instructively with sum-rate's non-convex WMMSE.

Definition:
RIS-Aided Max-Min Problem

The max-min rate problem under RIS is

$\boxed{\;\max_{\mathbf{W}, \boldsymbol{\Phi}}\; \min_{k = 1, \ldots, K}\; R_k(\mathbf{W}, \boldsymbol{\Phi})\;}$

subject to $\text{tr}(\mathbf{W}^{H} \mathbf{W}) \leq P_t$ and $|\phi_n| = 1$ . Equivalently (since $\log_2$ is monotone), maximize $\min_k \text{SINR}_k$ .

With $\boldsymbol{\Phi}$ fixed, the inner problem $\max_{\mathbf{W}} \min_k \text{SINR}_k$ is a classical MU-MIMO max-min SINR problem — feasible QoS when reformulated.

Theorem: Bisection Reduces Max-Min to Feasibility

For fixed $\boldsymbol{\Phi}$ , the max-min SINR problem

$\max_{\mathbf{W}}\;\min_k\;\text{SINR}_k \quad \text{s.t.}\quad \text{tr}(\mathbf{W}^{H} \mathbf{W}) \leq P_t$

is equivalent to the minimum-power QoS feasibility problem

$(\text{QoS-}\gamma):\quad \min_{\mathbf{W}}\; \text{tr}(\mathbf{W}^{H} \mathbf{W})\quad \text{s.t.}\; \text{SINR}_k \geq \gamma\;\forall k$

whose feasibility can be checked as an SOCP in polynomial time. Bisecting on $\gamma$ and calling the SOCP as oracle produces the max-min SINR to any desired precision in $O(\log(1/\epsilon))$ SOCP solves.

Ask: "Can we serve all $K$ users at SINR $\geq \gamma$ ?" If yes, try a higher $\gamma$ ; if no, lower. Binary search over $\gamma$ converges to the max-min SINR in $\log$ -factor iterations. Each feasibility check is a single SOCP — convex, global, polynomial time.

Proof

QoS formulation

For fixed $\gamma$ , $\text{SINR}_k \geq \gamma$ becomes $|\mathbf{h}_{k,\text{eff}}^H \mathbf{v}_{k}|^2 \geq \gamma (\sum_{j \neq k} |\mathbf{h}_{k,\text{eff}}^H \mathbf{v}_{j}|^2 + \sigma^2)$ , which (after rotating $\mathbf{v}_{k} \to e^{j\delta} \mathbf{v}_{k}$ to make $\mathbf{h}_{k,\text{eff}}^H \mathbf{v}_{k}$ real and positive) becomes a second-order cone constraint in $(\mathbf{W})$ .

SOCP

Collecting all $K$ SOC constraints and minimizing the convex power objective gives a standard SOCP. Feasibility and solution are polynomial-time.

Bisection

Set lower bound $\gamma_{\text{lo}} = 0$ (always feasible) and upper bound $\gamma_{\text{hi}}$ from single-user bound (e.g., $P_t \|\mathbf{h}_{k,\text{eff}}\|^2 / \sigma^2$ ). At midpoint $\gamma_{\text{mid}}$ , solve $(\text{QoS-}\gamma_{\text{mid}})$ . If feasible at power $\leq P_t$ : $\gamma_{\text{lo}} = \gamma_{\text{mid}}$ ; else $\gamma_{\text{hi}} = \gamma_{\text{mid}}$ . Repeat until $\gamma_{\text{hi}} - \gamma_{\text{lo}} < \epsilon$ .

Full AO

Outer loop over $\boldsymbol{\Phi}$ uses Chapter 6 algorithms to update RIS phases for the max-min objective; the bisection+SOCP is the inner loop. $\blacksquare$

,

Key Takeaway

Fix $\boldsymbol{\Phi}$ → max-min becomes polynomial-time via SOCP + bisection. The active subproblem is genuinely tractable in multi-user fairness, unlike sum-rate which needs WMMSE. This makes max-min MU-RIS algorithmically easier than sum-rate MU-RIS in a well-defined sense: the outer AO iterations are the same, but each inner solve is convex and global instead of non-convex local.

AO for MU-RIS Max-Min Rate

Complexity:

O(T \cdot [\log(1/\epsilon_{\text{bisect}}) \cdot C_{\text{SOCP}} + C_{\text{passive}}])

Input: channels, power

P_t

, tolerances

\epsilon_{\text{outer}}, \epsilon_{\text{bisect}}

.

Output:

(\mathbf{W}^\star, \boldsymbol{\Phi}^\star)

with max-min SINR.

1. Initialize

\boldsymbol{\Phi}^{(0)}

.

2. Repeat

t = 0, 1, 2, \ldots

:

3.

\quad

Compute

\mathbf{h}_{k,\text{eff}}^{(t)}

.

4.

\quad

Active update via bisection:

5.

\quad\quad

Set

\gamma_{\text{lo}} = 0

;

\gamma_{\text{hi}} =

single-user upper bound.

6.

\quad\quad

While

\gamma_{\text{hi}} - \gamma_{\text{lo}} > \epsilon_{\text{bisect}}

:

7.

\quad\quad\quad

\gamma = (\gamma_{\text{lo}} + \gamma_{\text{hi}})/2

. Solve SOCP

(\text{QoS-}\gamma)

.

8.

\quad\quad\quad

If feasible:

\gamma_{\text{lo}} \leftarrow \gamma

; else

\gamma_{\text{hi}} \leftarrow \gamma

.

9.

\quad\quad

Set

\mathbf{W}^{(t+1)} =

SOCP solution at

\gamma_{\text{lo}}

.

10.

\quad

Passive update: optimize

\boldsymbol{\Phi}

for max-min SINR

using Chapter 6 methods (SDR for best quality, element-wise for speed).

11.

\quad

Check

|\min_k R_k^{(t+1)} - \min_k R_k^{(t)}| < \epsilon_{\text{outer}}

.

12. return

(\mathbf{W}, \boldsymbol{\Phi})

.

Each SOCP has $N_t K + K$ variables and $2K$ SOC constraints; interior-point complexity is $O((N_t K)^{3.5})$ , manageable for moderate $N_t, K$ . Bisection adds $\log(1/\epsilon_{\text{bisect}}) \sim 20$ factor. Total inner cost per AO iteration: $\sim 20 \times$ SOCP time.

Example: Max-Min SINR for a 2-User MISO

Two users with effective channels $\mathbf{h}_{1,\text{eff}} = [1; 0]$ , $\mathbf{h}_{2,\text{eff}} = [0; 1]$ (orthogonal), $P_t = 10$ , $\sigma^2 = 1$ . Compute the max-min SINR.

Solution

Orthogonal case: ZF is optimal

With orthogonal channels, no inter-user interference occurs when we ZF: $\mathbf{v}_{1} = [a, 0]^T$ , $\mathbf{v}_{2} = [0, b]^T$ . SINR $_1 = a^2$ , SINR $_2 = b^2$ . Power constraint: $a^2 + b^2 \leq 10$ .

Max-min

$\min(a^2, b^2)$ is maximized at $a^2 = b^2 = 5$ , giving max-min SINR $= 5 = 7\text{ dB}$ and max-min rate $\log_2(1 + 5) = 2.58$ bits/s/Hz per user.

What the RIS adds

If the direct channels are not orthogonal, the RIS can rotate $\mathbf{h}_{k,\text{eff}}$ to make them more orthogonal, recovering the ZF-optimal regime. In general, this is a non-trivial joint optimization; the algorithm above computes it. $\blacksquare$

Sum Rate vs. Max-Min Rate Tradeoff

Plot the achievable boundary between sum rate and max-min rate as the objective is varied (e.g., via a weighted combination or a proportional-fair parameter). The RIS expands the boundary outward. Change $K$ to see how more users increase fairness pressure.

Parameters

RIS elements

N

64

BS antennas

N_t

8

Users

K

4

Transmit SNR (dB)10

Bisection + SOCP: The Max-Min Ladder

Animation of the bisection search: the SINR target

\gamma

rises or falls based on SOCP feasibility, converging to the max-min value. Each SOCP solve finds a feasible

\mathbf{W}

at power

\leq P_t

— or shows infeasibility, triggering a lower

\gamma

.

A Tradeoff, Not a Choice

Sum rate vs. max-min is the efficiency-vs-fairness tradeoff in multi-user systems. Sum-rate maximization can leave some users at zero rate; max-min maximizes the floor but caps the ceiling. The proportional-fair objective $\sum_k \log R_k$ sits between them: it grows with per-user rate (like sum rate) but penalizes unevenness (like max-min). In practice, production schedulers combine all three across time: sum rate for aggregate throughput, max-min or proportional-fair over short windows to maintain fairness. The RIS optimization framework is agnostic to the objective — plug in whichever utility function matches the operator's policy.

⚠️Engineering Note

Deploying Fairness with RIS

Production considerations for max-min MU-RIS:

SOCP solver choice: ECOS or MOSEK for quality; interior-point from scratch for deterministic timing. Per-solve $< 1$ ms at $N_t K = 64$ .
Bisection tolerance: $\epsilon_{\text{bisect}} = 10^{-2}$ on SINR (linear scale) suffices; finer costs more solves without visible rate change.
Outer AO warm-start: reuse previous $\boldsymbol{\Phi}$ and $\gamma_{\text{opt}}$ across coherence blocks; typical AO convergence in 3-5 outer iterations.
Infeasibility handling: if the power budget cannot serve all $K$ users at any $\gamma > 0$ , drop one user (the worst) and retry. Admission control is the outer envelope around the max-min scheduler.

Practical Constraints

•
Typical total optimization time: $\sim 20$ - $50$ ms per coherence block.
•
With infeasibility admission control, $K_{\text{admitted}} \leq \min(N_t, 1/\gamma_{\text{min}})$ roughly.
•
Bisection precision of $10^{-2}$ yields rate precision of $\sim 0.01$ bit/s/Hz.

Common Mistake: Initialize the Bisection Properly

Mistake:

"Start bisection with $\gamma_{\text{hi}} = 10^{10}$ — a big number, so we're sure to bracket the optimum."

Correction:

Overly loose bounds waste bisection iterations (and potentially trigger numerical instability in the SOCP solver). Use the single-user upper bound $\gamma_{\text{hi}} = P_t \cdot \max_k \|\mathbf{h}_{k,\text{eff}}\|^2 / \sigma^2$ — tight and cheap to compute. Start $\gamma_{\text{lo}} =$ a known feasible SINR (e.g., from equal-power MRT). Save $5$ - $10$ bisection iterations.

Max-Min Fairness and the SOCP Formulation