Network Information Theory via Robust Optimization

In this paper, we provide via robust optimization inner and outer bounds for the capacity region of multi-user channels with interference for finite code length n as well as a code that matches the inner bound. As n →∞, the bounds are tight and lead to an asymptotic characterization of the capacity region as well as matching optimal codes. For Gaussian channels the bounds involve a rank minimization problem subject to semidefinite constraints that can be solved by iterative application of semidefinite optimization methods. For exponential, uniform and binary channels or when we model the noise sequences as satisfying certain asymptotic laws, like the central limit theorem, the bounds involve binary,mixed linear optimization problems that can be solved by commercial solvers. We report computational results that show that the proposed RO approach is computationally tractable for n =140 for single user Gaussian channels and n= 60 for two-user Gaussian interference channels.