PaperlayerView exact revision on arXiv

Source-linked AI summary

Outage Constrained Robust Transmit Optimization for Multiuser MISO Downlinks: Tractable Approximations by Conic Optimization

Kun-Yu Wang, Anthony Man-Cho So, Tsung-Hui Chang, Wing-Kin Ma, Chong-Yung Chi

arXiv:1108.0982v1cs.IT

TL;DR

The paper studies probabilistic SINR-constrained beamforming for multiuser MISO downlinks with imperfect CSI, where outage constraints are difficult to process. It develops RAR approximations combining SDR with conservative probability bounds, yielding convex conic formulations. Simulations report that the RAR methods provide good approximations to the 90% SINR requirement and improve solution quality and computational complexity over existing methods.

  • Problem

    Probabilistic SINR constraints under random CSI errors generally lack closed-form expressions and are difficult to handle exactly in outage-constrained beamforming design.

  • Method

    RAR combines semidefinite relaxation with analytic upper bounds on violation probabilities to construct efficiently computable convex restrictions.

  • Results

    The RAR methods provide good approximations to the 90% SINR requirement and significantly improve solution quality and computational complexity over existing methods.

  • Takeaways & Limitations

    The paper offers several convex RAR alternatives for probabilistic SINR-constrained beamforming, including sphere bounding, Bernstein-type inequality, and decomposition methods.

Abstract

from arXiv · show

In this paper we consider a probabilistic signal-to-interference and-noise ratio (SINR) constrained problem for transmit beamforming design in the presence of imperfect channel state information (CSI), under a multiuser multiple-input single-output (MISO) downlink scenario. In particular, we deal with outage-based quality-of-service constraints, where the probability of each user's SINR not satisfying a service requirement must not fall below a given outage probability specification. The study of solution approaches to the probabilistic SINR constrained problem is important because CSI errors are often present in practical systems and they may cause substantial SINR outages if not handled properly. However, a major technical challenge is how to process the probabilistic SINR constraints. To tackle this, we propose a novel relaxation- restriction (RAR) approach, which consists of two key ingredients-semidefinite relaxation (SDR), and analytic tools for conservatively approximating probabilistic constraints. The underlying goal is to establish approximate probabilistic SINR constrained formulations in the form of convex conic optimization problems, so that they can be readily implemented by available solvers. Using either an intuitive worst-case argument or specialized probabilistic results, we develop various conservative approximation schemes for processing probabilistic constraints with quadratic uncertainties. Consequently, we obtain several RAR alternatives for handling the probabilistic SINR constrained problem. Our techniques apply to both complex Gaussian CSI errors and i.i.d. bounded CSI errors with unknown distribution. Moreover, results obtained from our extensive simulations show that the proposed RAR methods significantly improve upon existing ones, both in terms of solution quality and computational complexity.

I. INTRODUCTION

The paper addresses outage-constrained beamforming under imperfect CSI, where probabilistic SINR constraints are difficult to solve exactly. It proposes RAR-based conservative convex approximations that can be implemented efficiently and support multiple CSI-error models.

  • Problem setting: Transmit beamforming minimizes power while ensuring each user's SINR meets a prescribed QoS requirement.The formulation is a standard multiuser MISO downlink design problem.
  • Problem setting: Imperfect CSI arises from estimation noise, limited training, limited-rate feedback, and outdated channel information.Using corrupt CSI directly can cause severe SINR outages and prevent users from achieving anticipated QoS levels.
  • Problem setting: The probabilistic SINR formulation models CSI errors randomly and requires each user's SINR outage probability to remain below a specified level.Unlike worst-case formulations, its probabilistic constraints generally lack closed-form expressions and are difficult to handle exactly.
  • RAR approach: The proposed relaxation-restriction methodology combines semidefinite relaxation with analytic upper bounds on violation probabilities.SDR linearizes quadratic SINR terms, while restriction supplies sufficient conditions for the resulting probabilistic constraints.
  • RAR approach: These ingredients yield efficiently solvable convex approximations of the original probabilistic SINR-constrained beamforming problem.The restriction step can produce feasible solutions even when violation probabilities lack efficiently computable closed forms.
  • RAR approach: Different violation-probability bounds allow approximation performance to be traded against computational complexity.The paper develops RAR formulations for complex Gaussian and i.i.d. bounded CSI errors, including robust-optimization and probabilistic approaches.

II. PROBLEM FORMULATION

The paper formulates outage-constrained transmit beamforming for a multiuser MISO downlink with imperfect CSI, minimizing transmit power while meeting users’ probabilistic SINR requirements. The resulting chance-constrained problem is difficult because its probability functions lack simple closed forms, so approximation methods are needed.

  • System model: The transmitter serves multiple users with unicast data streams using linear beamforming over a multi-antenna downlink.
  • Imperfect CSI: CSI is modeled as hi = ¯hi + ei, where ¯hi is the presumed channel and ei is a random channel error, mainly modeled as complex Gaussian with known covariance Ci.
  • Optimization objective: The design chooses beamforming vectors to satisfy each user’s QoS while minimizing total transmit power under imperfect CSI.
  • Outage constraints: Each probabilistic SINR constraint requires SINRi ≥ γi with probability at least 1 − ρi, where γi is the SINR target and ρi is the maximum outage probability.
  • Computational challenge: The formulation is a chance-constrained optimization problem whose probability functions do not have simple closed forms for the considered CSI error models.
  • Design trade-off: Decreasing ρi increases service fidelity but makes the design more conservative, potentially producing excessive transmit power or no feasible solution.

III. THE RELAXATION-RESTRICTION APPROACH

The RAR approach combines semidefinite relaxation with convex restrictions of probabilistic constraints. SDR removes rank-one constraints to make the quadratic SINR expressions more manageable, while the restriction step produces tractable conservative approximations.

  • RAR overview: RAR approximates the probabilistic SINR problem using convex optimization techniques that can be implemented with available convex optimization software.
  • Relaxation step: SDR handles the indefinite quadratic SINR inequalities by lifting beamforming vectors into covariance matrices and removing their nonconvex rank-one constraints.
  • Relaxation step: Removing rank-one constraints can yield covariance solutions with rank higher than one, creating a solution-rank issue for recovering beamforming vectors.

B. An Information Theoretic Interpretation of the Relaxation Step

The SDR can be interpreted as outage-constrained rate optimization over general transmit covariances rather than only rank-one beamforming. RAR then replaces each probabilistic constraint with a convex restriction, yielding conic formulations and a procedure for recovering feasible beamforming solutions.

  • Information-theoretic interpretation: The SDR represents a general transmission scheme through user-specific transmit covariance matrices Wi rather than imposing a particular beamforming structure.
  • Information-theoretic interpretation: The equivalent problem minimizes total power while ensuring each user’s rate reaches log2(1 + γi) with outage probability at most ρi.
  • Information-theoretic interpretation: A non-rank-one SDR solution can correspond to alternative physical-layer schemes such as space-time coding, although the paper focuses on transmit beamforming.
  • Limitation: Obtaining a feasible RAR solution does not always guarantee a feasible solution to the original probabilistic problem.
  • Restriction step: RAR replaces each SDR probabilistic constraint with a convex restriction, producing conic problems with linear matrix inequality and/or second-order cone constraints.
  • Solution recovery: RAR solutions may have rank higher than one and therefore require rank-one approximation or Gaussian randomization to generate beamforming vectors.
  • Empirical implication: RAR methods returned rank-one solutions in almost all simulation trials, making simple rank-one decomposition usually sufficient and suggesting beamforming may be optimal in this scenario.

IV. RAR METHOD I: SPHERE BOUNDING

RAR Method I conservatively replaces a Gaussian quadratic chance constraint with a worst-case constraint over a probability-containing sphere. The S-lemma converts the resulting infinitely many constraints into an LMI, producing a convex restriction and a corresponding RAR formulation.

  • Sphere bounding: Sphere bounding approximates the Gaussian quadratic chance constraint by enforcing the quadratic inequality over a bounded uncertainty sphere.
  • Sphere bounding: The sphere radius is selected using the inverse cumulative distribution function of a central Chi-square random variable to satisfy the required probability bound.
  • Convex restriction: The S-lemma transforms the infinitely many worst-case constraints over the sphere into an equivalent linear matrix inequality.
  • RAR formulation: The resulting method is a convex restriction of the chance constraint and therefore yields a tractable RAR formulation after SDR.
  • Performance refinement: A bisection scheme can further improve the performance of the sphere-bounding RAR method.

V. PROBABILITY INEQUALITY APPROACHES

The paper develops convex restrictions for probabilistic quadratic constraints by upper-bounding violation probabilities, extending beyond simple worst-case uncertainty sets. This provides flexibility for constructing tractable approximations while retaining a conservative guarantee.

  • Worst-case robust feasibility controls violation probability through a carefully chosen uncertainty set and yields a convex restriction.The approach is limited by the difficulty of defining and analyzing uncertainty sets with geometry more complex than spherical sets.
  • Analytic upper bounds on violation probability circumvent the uncertainty-set design drawback of the worst-case approach.Different available upper bounds can produce different convex restrictions, enabling more sophisticated uncertainty sets that are difficult to construct directly.
  • An efficiently computable convex function f(Q, r, s, t) upper-bounds the quadratic violation probability and induces a convex restriction.The bound is imposed on Prob{e^HQe + 2Re{e^Hr} + s < 0} through an auxiliary variable t.

A. Method II: Bernstein-Type Inequality

The Bernstein-type inequality method bounds deviations of complex Gaussian quadratic forms and converts the resulting probabilistic condition into efficiently computable convex conic constraints. Compared with sphere bounding, it offers better approximation performance but generally increases constraint complexity.

  • Bernstein-type inequalities bound the probability that a complex Gaussian quadratic form deviates from its mean Tr(Q).The bound applies to e^HQe + 2Re{e^Hr}, whose mean is Tr(Q).
  • The probabilistic sufficient condition is equivalently represented by a system of convex conic inequalities with slack variables t1 and t2.This representation establishes an efficiently computable convex restriction of the chance constraint.
  • Method II applies the Bernstein-type restriction to Challenge 1 and produces the RAR formulation (11).The method is stated as a feasibility problem and then mapped to the beamforming formulation.
  • The Bernstein-type formulation has a more complex constraint set and generally higher computational complexity than sphere bounding.Its reported advantage is improved approximation performance relative to the sphere bounding method.

B. Method III: Decomposition into Independent Parts

Method III decomposes a quadratic uncertainty expression into independent parts, bounds each part’s moment generating function, and combines the bounds into a convex restriction. The resulting formulation can use second-order cone constraints and may be more efficient than sphere-bounding or Bernstein-type alternatives.

  • The decomposition method also provides an efficiently computable convex restriction when the problem size is large.
  • The resulting convex restrictions use second-order cone constraints and can be solved more efficiently than sphere-bounding or Bernstein-type formulations.This computational comparison is stated for the resulting formulation.
  • The decomposition approach splits e^HQe + 2Re{e^Hr} + s into independent random-variable sums and combines their moment-generating-function bounds.For Gaussian errors, spectral decomposition separates the quadratic form into components that support this construction.
  • Method III is formulated as a convex feasibility restriction of Challenge 1 over Q, r, s, and t.A parameter θ̄ < 1 controls the construction, while the feasibility problem seeks Q, r, s, and t.
  • The parameter θ̄ trades off μ and v, so they cannot be minimized independently; simulations favor choosing θ̄ to obtain a smaller μ.For a specified ρ, θ̄ is selected numerically so that v is minimized subject to the stated μ relationship.

C. Variation on a Theme: i.i.d. Bounded CSI Errors with Unknown Distribution via the Decomposition Approach

The decomposition approach extends to elementwise i.i.d. bounded CSI errors with unknown distribution by exploiting independent components and constructing convex restrictions. Simulations evaluate feasibility and implementation against probabilistic SOCP and perfect-CSI baselines.

  • The decomposition method constructs independent quadratic and linear parts, bounds their moment-generating functions, and yields a convex restriction for Challenge 2.The construction uses the sets A1, . . . , An to organize terms into independent sums.
  • The bounded-error model assumes independent real and imaginary CSI-error components with zero mean and support [−ε_i, ε_i].The distribution is otherwise unknown.
  • Method IV is stated as a convex feasibility problem over Q, r, s, and t for Challenge 2.
  • The simulations benchmark RAR methods against probabilistic SOCP methods and a conventional perfect-CSI-based non-robust design.Feasibility includes both solving the RAR problem and generating a feasible beamforming solution.
  • The simulation setting uses common SINR and outage specifications, identical fixed noise powers σ_i^2 = 0.1, and independently generated standard complex Gaussian presumed channels.

A. Simulation Example 1

Simulation Example 1 shows that RAR methods meet the 90% SINR satisfaction target while improving feasibility, power, and runtime trade-offs over competing approaches. RAR Method II is generally the least conservative and best-performing, whereas Method III is fastest.

  • SINR satisfaction: The RAR methods and probabilistic SOCP method adhere to the 90% SINR satisfaction specification.The non-robust method falls below 50% satisfaction for most channel realizations, revealing sensitivity to CSI errors.
  • SINR satisfaction: Probabilistic SOCP satisfaction probabilities concentrate at 100%, whereas RAR methods are less conservative, with RAR Method II appearing most relaxed.The comparison is based on histograms over 500 channel realizations and numerically evaluated CSI-error realizations.
  • Feasibility: RAR methods yield much higher feasibility rates than probabilistic SOCP, with RAR Method II achieving the best feasibility-rate performance.RAR Methods I and III are closely matched, with their relative ordering changing around γ = 9dB.
  • Transmit power: RAR Method II provides the best average transmit power performance, followed by Methods I and III and then probabilistic SOCP.For γ ≤11dB, the transmit-power difference between an RAR method and the non-robust method is about 1.5dB; the gaps widen otherwise.
  • Computation: Runtime ranking from shortest to longest is RAR Method III, RAR Method I, RAR Method II, and probabilistic SOCP.The RAR runtime ranking is exactly opposite to the performance ranking observed in the preceding simulation.
  • Rank-one solutions: Almost all feasible RAR instances produce rank-one solutions, with only one non-rank-one instance observed out of 480 for ρ = 0.01 and γ = 3dB.Rank-one solutions simplify beamforming generation by avoiding Gaussian randomization.

B. Simulation Example 2

Simulation Example 2 evaluates RAR under larger systems and spatially correlated Gaussian CSI errors, finding that RAR Method II remains strongest overall. Bisection improves robust-method performance, but Method II is already competitive without it.

  • Computational scope: The probabilistic SOCP method is not run for large problem sizes because it is computationally very demanding.The limitation is identified from the runtime comparison in Figure 3.
  • Correlated-error performance: With Nt = 8 and K = 6, the same performance trends as the preceding correlated-error experiment are observed.The feasible-realizations pick-up point is γ = 13dB.
  • Bisection: Bisection requires solving the design problem multiple times and validating outage-specification satisfiability, increasing computational work.Validation can use a Monte-Carlo-based procedure.
  • Bisection: Bisection improves the performance of all robust methods, while RAR Method II without bisection is already quite on a par with bisection-aided methods.Bisection repeatedly adjusts design parameters related to the outage requirement and reruns the design problem.

D. Simulation Example 4

Under i.i.d. uniform CSI errors, RAR Method IV substantially outperformed the probabilistic SOCP method, while high-rank RAR solutions were rare. More broadly, the proposed RAR framework combines semidefinite relaxation with efficiently computable convex restrictions for probabilistic SINR constraints.

  • Simulation Example 4: RAR Method IV, tested with elementwise i.i.d. uniform CSI errors, provided much better performance than the probabilistic SOCP method.The simulation used independent uniformly distributed real and imaginary error components.
  • Simulation Example 4: High-rank RAR solutions were rare, as shown by the ratios of rank-one solutions reported in Table IV.The passage states that encountering high-rank RAR solutions is rare.
  • Problem and approach: The probabilistic SINR formulation protects each user's SINR requirement but is difficult to process because of SINR outage probability constraints.The formulation addresses transmit beamforming under user SINR requirements.
  • Problem and approach: The RAR approach uses semidefinite relaxation and analytic probability tools to produce efficiently computable convex approximations of the probabilistic formulation.The approach develops convex approximations for probabilistic SINR constraints with quadratic uncertainties.
  • Problem and approach: Three methods—sphere bounding, Bernstein-type inequality, and decomposition—were developed to process probabilistic SINR constraints.These methods form the paper's principal RAR alternatives.
  • Conclusions: The proposed RAR methods provide good approximations and improve upon existing methods in solution quality and computational complexity.The conclusion also identifies efficiently computable convex restrictions as central technical tools.
Loading 1108.0982v1…