Wireless systems that pair a multi-antenna base station with a reconfigurable intelligent surface (a panel of hundreds of cheap elements that each re-radiate the signal with an adjustable phase) are almost always tuned by alternating optimization. The method fixes the surface and solves for the transmitter's beam, then fixes the beam and solves for the surface, and repeats. It is fast and converges in a handful of iterations. It also gives no indication of how much performance is left on the table. The only certifiable alternative in current use, semidefinite relaxation, costs on the order of $N^6$ in the number of surface elements $N$. That makes it unusable exactly where surfaces become interesting, at hundreds of elements. Nobody currently knows whether alternating optimization on realistic multi-user surfaces is near-optimal or badly trapped.
The proposal rests on one observation. However many elements the surface has, the users' signals depend on the phase vector only through a few linear measurements: one complex number per base-station antenna per user. The search can therefore branch in a space whose dimension is $2MK$, with $M$ antennas and $K$ users, rather than $N$. The nonconvexity of the unit-modulus phase constraint mostly washes out as $N$ grows, by the Shapley–Folkman lemma (a classical result that a sum of many nonconvex sets is nearly convex). Together these give a branch-and-bound certifier. It is linear in $N$ per node, uses alternating optimization as its source of good candidate solutions, and has an a priori prediction that its gap shrinks like $2MK/N$. We will use it both to certify alternating optimization's output and to measure, for the first time, how suboptimal that output really is.
Core Claim
Write the surface as a phase vector $\theta\in\mathbb{C}^N$ with $\theta_n\in\Phi$. Here $\Phi$ is either the unit circle or a set of $2^B$ discrete phases. User $k$'s effective channel is $h_k(\theta)=h_{d,k}+G_k\theta$, where $h_{d,k}$ is the direct base-station-to-user channel and $G_k$ is the $M\times N$ cascaded base-station–surface–user channel. Stacking all $G_k$ gives a real linear map $A$ into dimension $d=2MK$. Every objective in this literature (minimum transmit power under per-user signal-quality targets, max-min signal quality, sum rate) depends on $\theta$ only through the image $z=A\theta$. That image lives in
$$ S=\sum_{n=1}^{N} S_n,\qquad S_n=\{a_n\phi:\ \phi\in\Phi\}, $$
where $a_n$ is the $n$-th column of $A$. This is a Minkowski sum of $N$ small circles or polygons in $\mathbb{R}^d$. Two facts make this useful.
The first fact is that the convex hull of $S$ is cheap to query. Its support function in direction $u$ separates across elements,
$$ \sigma_{\mathrm{conv}\,S}(u)=\sum_{n=1}^{N}\max_{\phi\in\Phi}\mathrm{Re}\big(u^{\mathsf H}a_n\phi\big), $$
which is $\sum_n |u^{\mathsf H}a_n|$ for continuous phases. It costs $O(Nd)$ to evaluate. Linear bounds over the hull, and hence outer approximations of any region of $z$-space, never require an $N\times N$ matrix.
The second fact is that the hull is nearly the set itself. By Shapley–Folkman, any point of $\mathrm{conv}\,S$ can be written as a sum in which all but at most $d$ elements sit at genuine feasible phases. Starr's corollary bounds the distance from $\mathrm{conv}\,S$ to $S$ by roughly $\sqrt{d}$ times the largest single-element radius $\max_n\|a_n\|$, independent of $N$. The received signal grows with $N$, so the relative price of convexifying the phase constraint falls like $d/N$. The same lemma also gives a constructive rounding step: at most $d$ phases ever need to be chosen jointly, and for small $d$ they can be enumerated.
The certifier is a spatial branch-and-bound over boxes in $z$-space. Each box is tested for intersection with $\mathrm{conv}\,S$ using the support-function oracle. Each box receives a convex bound on the active-beamforming problem that holds for all channel images in the box. For power minimization this bound is a robust version of the uplink–downlink dual. Incumbent solutions come from fractional-programming alternating optimization warm-started inside the box, followed by Shapley–Folkman rounding. Cost is exponential only in $d$ and linear in $N$. That is the opposite scaling to semidefinite relaxation, and it matches the regime of interest: few users and antennas, very large surfaces.
Relation to Prior Work
Two papers supply methods we reuse. Joint Beamforming and Reflecting Design in Reconfigurable Intelligent Surface-Aided Multi-User Communication Systems gives closed-form fractional-programming alternating updates at 0.0695 s per iteration versus 438 s for semidefinite relaxation. It provides no certificate, and we use it as the incumbent generator. Beamforming Design for Multiuser Transmission Through Reconfigurable Intelligent Surface takes a Lagrangian dual of power minimization. Its phase recovery needs randomization when the relaxation is not rank-one, which forfeits the guarantee. We keep the dual as the per-box active bound but make it robust over a box of channels, instead of lifting the phases into a matrix.
The closest work, Configuring Intelligent Reflecting Surface With Performance Guarantees: Optimal Beamforming, motivates our dimension-reduction view. It notices that in its single-user setting the problem lives in a two-dimensional complex plane, and it solves binary phases exactly in $O(N)$ with an 85.3% ratio for quaternary phases. Our construction generalizes that low-rank geometric picture from rank two to rank $2MK$, and from a fixed active beam to a jointly optimized one. This is precisely the multi-user case that paper leaves open. We give up its closed-form exactness in exchange for a branch-and-bound whose depth depends on $d$.
The generic certificate pattern of a primal candidate sandwiched against a dual bound comes from Lagrangian certification in Optimal Beam Search for Machine Translation. That paper certifies 99% of sentences where plain beam search finds the exact optimum only 23–37% of the time. We borrow the lesson that heuristic incumbents plus cheap bounds can certify most instances.
Two papers constrain the design. Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded shows that structure-aware branching and bounding proves optimality where Gurobi and CPLEX cannot, which argues against simply handing the problem to a commercial solver. Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering obtains exact certificates from full semidefinite programs, and it concedes that these are prohibitive at scale. We avoid the lifted matrix entirely.
Finally, Global optimization of factor models using alternating minimization proves that in sufficiently overcomplete factor models, alternating minimization's full-rank stationary points are global. Our Shapley–Folkman argument predicts an analogous effect for surfaces: as $N/d$ grows, the problem looks increasingly convex in $z$ and alternating optimization should get closer to optimal. Unlike that paper, we do not assume the benign landscape. We measure it with certificates, under unit-modulus and discrete constraints that its smooth theory excludes.
Research Program
The theory work states and proves the $d/N$ relative-gap bound for the convexified problem. The proof combines Starr's distance bound with a Lipschitz constant of each objective in $z$, so that each objective inherits the geometric gap. It then derives the robust per-box dual bound for power minimization and for max-min signal quality, using standard robust semidefinite constraints on $M\times M$ matrices, so each bound costs on the order of $M^3$ times the number of users. Sum rate is harder because the per-box bound is itself nonconvex. There we will use the known quadratic-transform upper bound and report sum-rate certificates as a secondary, looser result.
The system work implements the certifier in three pieces: the support-function oracle, the box bounds, and a best-first search seeded by multi-start fractional-programming alternating optimization. It also provides a zero-branching "root certificate". This is the bound at the root box with no splitting, which a base station could compute right after alternating optimization converges to report an optimality gap at near-zero extra cost.
The empirical work uses the certifier as an instrument. It maps alternating optimization's certified gap across $N$, $M$, $K$, phase resolution $B$ and channel conditions, and tests whether that gap tracks the predicted $d/N$ law.
Baselines
The naive reference point is alternating optimization run once from a random surface, using fractional programming as in Joint Beamforming and Reflecting Design in Reconfigurable Intelligent Surface-Aided Multi-User Communication Systems for rate objectives and the dual method of Beamforming Design for Multiuser Transmission Through Reconfigurable Intelligent Surface for power. These are the reported practice: roughly ten and six iterations respectively. The dual method reports up to 94% power reduction over maximum-ratio transmission and 27% over zero-forcing. Neither paper reports any gap to the global optimum. We found no reported result on Lacuna for the global-optimality gap of alternating optimization in multi-user surface beamforming.
The strongest competitor for the primal is multi-start alternating optimization. It gets the same wall-clock budget as our certifier, with restart counts chosen so total time matches. For the bound, the strongest competitor is the semidefinite-relaxation value itself: the relaxation's optimum is a valid bound even though its randomized rounding is heuristic. We will solve it with the same generic solver on the same instances, capped at $N=60$ where per-iteration cost is already 438 s. We add Gurobi's nonconvex quadratic mode on the discrete-phase version under the same time limit. For single-user instances, the exact binary and 85.3%-ratio quaternary method of Configuring Intelligent Reflecting Surface With Performance Guarantees: Optimal Beamforming serves as a ground-truth sanity check that our certifier must match.
Two ablations isolate the key ingredient. The first runs branch-and-bound over the $N$ phases directly instead of over $z$, which tests whether dimension reduction is what buys scalability. The second replaces Shapley–Folkman rounding with closest-point projection, which tests whether the constructive rounding matters for incumbents.
Beating the baselines means specific things. On bounds, we need strictly tighter certified gaps than the semidefinite bound at equal time, or any certificate at all at $N\ge 100$, where semidefinite relaxation and Gurobi return none. On primal quality, we need to find solutions better than time-matched multi-start on a measurable fraction of instances, or prove multi-start already optimal. The second outcome is a publishable finding in its own right.
Why not just…?
Why not just run alternating optimization from many random starts? With 0.0695 s per iteration this is cheap, and it may well find the optimum. What it cannot do is say so. The machine-translation evidence in Optimal Beam Search for Machine Translation is a reminder that heuristic search can look converged while missing the optimum in most instances. We treat this alternative as a serious threat on primal quality. If certificates show multi-start is always within 1%, we will report that the heuristic is vindicated. The contribution then becomes the certificate and the scaling law, not a better beam.
Why not just take the semidefinite relaxation bound and compare it to the alternating solution? This is a legitimate certificate and the most honest competitor. Its cost scales like $N^6$ and is already reported at 438 s per iteration for $N\le 60$. Its bound also carries the relaxation's own gap, which it has no mechanism to close. Our tightness-versus-$N$ experiment will show directly whether our root bound is tighter, looser or equal at the sizes where the relaxation still runs. It will also show whether the relaxation can run at all at 256 elements.
Why not just hand the problem to Gurobi? The gradient-boosted-tree study Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded found that commercial solvers failed to prove optimality where structure-aware branching succeeded. A generic solver would branch over $N$ phase variables, whereas we branch over $d=2MK$. The ablation that branches over phases directly is exactly this comparison, and we will run Gurobi alongside it.
Why not just round a continuous solution to the nearest discrete phase? Configuring Intelligent Reflecting Surface With Performance Guarantees: Optimal Beamforming shows this closest-point projection has no worst-case guarantee. Hybrid Digital and Analog Beamforming Design for Large-Scale Antenna Arrays reports about 5 dB loss at one to two bits. Shapley–Folkman rounding confines the hard choices to at most $d$ elements, and the rounding ablation measures what that buys.
Proposed Experiments
The primary benchmark is the simulated multi-user surface setup of Joint Beamforming and Reflecting Design in Reconfigurable Intelligent Surface-Aided Multi-User Communication Systems: $M=3$, $K=2$, $N$ from 20 to 60. We extend it to $N=256$, the size of the prototype in Configuring Intelligent Reflecting Surface with Performance Guarantees: Blind Beamforming. We use continuous phases and $B\in\{1,2\}$ bits, with power minimization as the headline objective and max-min signal quality and sum rate as secondary objectives. As a realism check, the base-station, surface and user geometry will be drawn from DeepMIMO outdoor scenario O1. This check is only partial, because DeepMIMO as used in Normalization-Free Knowledge Distillation for Variable-Bit CSI Feedback in Massive MIMO models base-station–user links rather than surfaces, so the cascaded links must be composed by us.
The metrics are four. We report certified relative gap, meaning incumbent versus bound divided by the bound. We report the fraction of instances certified within 1% and within 0.1%, time to certificate, and the distribution of single-start and multi-start alternating optimization's true gap once certified optima are known.
Three checks are decisive. The first is that the root-box relative gap, plotted against $N/d$, should fall roughly as $d/N$. A flat curve would falsify the Shapley–Folkman mechanism as the explanation. The second is that at $N\ge 128$ the certifier should certify most instances within minutes while semidefinite relaxation and Gurobi return nothing. The third is that on single-user binary instances it must reproduce the exact optimum of the geometric method. Beyond these, the substantive scientific result is whatever the certified gap of alternating optimization turns out to be, reported per regime. If the gap is small, practitioners gain a license to trust alternating optimization. If it is large, the certifier's incumbents are the improvement.
References
- Joint Beamforming and Reflecting Design in Reconfigurable Intelligent Surface-Aided Multi-User Communication Systems
- Beamforming Design for Multiuser Transmission Through Reconfigurable Intelligent Surface
- Configuring Intelligent Reflecting Surface With Performance Guarantees: Optimal Beamforming
- Optimal Beam Search for Machine Translation
- Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded
- Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering
- Global optimization of factor models using alternating minimization
- Hybrid Digital and Analog Beamforming Design for Large-Scale Antenna Arrays
- Configuring Intelligent Reflecting Surface With Performance Guarantees: Blind Beamforming
- Normalization-Free Knowledge Distillation for Variable-Bit CSI Feedback in Massive MIMO