Abstract
Optimal design of wireless systems in the presence of fading involves the instantaneous allocation of resources such as power and frequency with the ultimate goal of maximizing long term system properties such as ergodic capacities and average power consumptions. This yields a distinctive problem structure where long term average variables are determined by the expectation of a not necessarily concave functional of the resource allocation functions. Despite their lack of concavity it can be proven that these problems have null duality gap under mild conditions permitting their solution in the dual domain. This affords a significant reduction in complexity due to the simpler structure of the dual function. The article discusses the problem simplifications that arise by working in the dual domain and reviews algorithms that can determine optimal operating points with relatively lightweight computations. Throughout the article concepts are illustrated with the optimal design of a frequency division broadcast channel.
Introduction
Operating variables of a wireless system can be separated in two types. Resource allocation variables p(h) determine instantaneous allocation of resources like frequencies and transmitted powers as a function of the fading coefficient h. Average variables x capture system’s performance over a large period of time and are related to instantaneous resource allocations via ergodic averages. A generic representation of the relationship between instantaneous and average variables is
where f_{1}(h,p(h)) is a vector function that maps channel h and resource allocation p(h) to instantaneous performance f_{1}(h,p(h)). The system’s design goal is to select resource allocations p(h) to maximize ergodic variables x in some sense.
An example of a relationship having the form in (1) is a code division multiple access channel in which case h denotes the vector of channel coefficients, p(h) the instantaneous transmitted power, f_{1}(hp(h)) the instantaneous communication rate determined by the signal to interference plus noise ratio, and x the ergodic rates determined by the expectation of the instantaneous rates. The design goal is to allocate instantaneous power p(h) subject to a power constraint so as to maximize a utility of the ergodic rate vector x. This interplay of instantaneous actions to optimize long term performance is pervasive in wireless systems. A brief list of examples includes optimization of orthogonal frequency division multiplexing [1], beamforming [2,3], cognitive radio [4,5], random access [6,7], communication with imperfect channel state information (CSI) [8,9], and various flavors of wireless network optimization [1018].
In many cases of interest the functions f_{1}(h,p(h)) are nonconcave and as a consequence finding the resource allocation distribution p^{∗}(h) that maximizes x requires solution of a nonconvex optimization problem. This is further complicated by the fact that since fading channels h take on a continuum of values there is an infinite number of p^{∗}(h) variables to be determined. A simple escape to this problem is to allow for time sharing in order to make the range of convex and permit solution in the dual domain without loss of optimality. While the nonconcave function f_{1}(h,p(h)) still complicates matters, working in the dual domain makes solution, if not necessarily simple, at least substantially simpler. However, time sharing is not easy to implement in fading channels.
In this article, we review a general methodology that can be used to solve optimal resource allocation problems in wireless communications and networking without resorting to time sharing [19,20]. The fundamental observation is that the range of is convex if the probability distribution of the channel h contains no points of positive probability (Section “Duality in wireless systems optimization”). This observation can be leveraged to show lack of duality gap of general optimal resource allocation problems (Theorem 1) making primal and dual problems equivalent. The dual problem is simpler to solve and its solution can be used to recover primal variables (Section “Recovery of optimal primal variables”) with reduced computational complexity due to the inherently separable structure of the problem Lagrangians (Section “Separability”). We emphasize that this reduction in complexity, as in the case of time sharing, just means that the problem becomes simpler to solve. In many cases it also becomes simple to solve, but this is not necessarily the case.
We also discuss a stochastic optimization algorithm to determine optimal dual variables that can operate without knowledge of the channel probability distribution (Section “Dual descent algorithms”). This algorithm is known to almost surely converge to optimal operating points in an ergodic sense (Theorem 5). Throughout the article concepts are illustrated with the optimal design of a frequency division broadcast channel (Section “Frequency division broadcast channel” in “Optimal wireless system design”, Section “Frequency division broadcast channel” in “Recovery of optimal primal variables”, and Section “Frequency division broadcast channel” in “Dual descent algorithms”).
One of the best known resource allocation problems in wireless communications concerns the distribution of power on a block fading channel using capacityachieving codes. The solution to this problem is easy to derive and is well known to reduce to waterfilling across the fading gain, e.g., [21, p. 245]. Since this article can be considered as an attempt to generalize this solution methodology to general wireless communication and networking problems it is instructive to close this introduction by reviewing the derivation of the waterfilling solution. This is pursued in the following section.
Power allocation in a pointtopoint channel
Consider a transmitter having access to perfect CSI h that it uses to select a transmitted power p(h) to convey information to a receiver. Using a capacity achieving code the instantaneous channel rate for fading realization h is where N_{0}denotes the noise power at the receiver end. A common goal is to maximize the average rate with respect to the probability distribution m_{h}(h) of the channel gain h—which is an accurate approximation of the long term average rate—subject to an average power constraint P_{0}. We can formulate this problem as the optimization program
In most cases the fading channel h takes on a continuum of values. Therefore, solving (2) requires the determination of a power allocation function that maps nonnegative fading coefficients to nonnegative power allocations. This means that (2) is an infinite dimensional optimization problem which in principle could be difficult to solve. Nevertheless, the solution to this program is easy to derive and given by waterfilling as we already mentioned. The widespread knowledge of the waterfilling solution masks the fact that is is rather remarkable that (2) is easy to solve and begs the question of what are the properties that make it so. Let us then review the derivation of the waterfilling solution in order to pinpoint these properties.
To solve (2) we work in the dual domain. To work in the dual domain we need to introduce the Lagrangian, the dual function, and the dual problem. Introduce then the nonnegative dual variable and define the Lagrangian associated with the optimization problem in (2) as
The dual function is defined as the maximum value of the Lagrangian across all functions , which upon defining as the set of nonnegative functions can be defined as
The dual problem corresponds to the minimization of the dual function with respect to all nonnegative multipliers λ,
Since the objective in (2) is concave with respect to variables p(h) and the constraint is linear in p(h) the optimization problem in (2) is convex and as such it has null duality gap in the sense that P=D.
An entity that is important for the upcoming discussion is the primal Lagrangian maximizer function whose values for given h are denoted as p(h,λ). This function is defined as the one that maximizes the Lagrangian for given dual variable λ
Using the definition of the Lagrangian maximizer function we can write the dual function as .
Computing values p(h,λ) of the Lagrangian maximizer function p(λ) is easy. To see that this is true rewrite the Lagrangian in (3) so that there is only one expectation
With the Lagrangian written in this form we can see that the maximization of required by (6) can be decomposed in maximizations for each individual channel realization,
That the equality in (8) is true is a consequence of the fact that the expectation operator is linear and that there are no constraints coupling the selection of values p(h_{1}) and p(h_{2}) for different channel realizations h_{1}≠h_{2}. Functional values p(h) in both sides of (8) are required to be nonnegative but other than that we can select p(h_{1}) and p(h_{2}) independently of each other as indicated in the right hand side of (8).
Since the right hand side of (8) states that to maximize the Lagrangian we can select functional values p(h) independently of each other, values p(h,λ) of the Lagrangian maximizer function p(λ) defined in (6) are given by
The similarity between (6) and (9) is deceiving as the latter is a much easier problem to solve that involves a single variable. To find the Lagrangian maximizer value p(h,λ) operating from (9) it suffices to solve for the null of the derivative with respect to p(h). Doing this yields the Lagrangian maximizer
where the operator [x]^{ + }:=max(x,0) denotes projection onto nonnegative reals, which is needed because of the constraint p(h)≥0.
Of particular interest is the Lagrangian maximizer function p(λ^{∗}) corresponding to the optimal Lagrange multiplier . Returning to the definition of the dual function in (4) we can bound D=g(λ^{∗}) as
Indeed, since D is given by a Lagrangian maximization it must equal or exceed the values of the Lagrangian for any function p, and for the optimal function p^{∗}in particular. Considering the explicit Lagrangian expression in (3) we can write as
Observe that since p^{∗}is the optimal power allocation function it must satisfy the power constraint implying that it must be . Since the optimal dual variable satisfies λ^{∗}≥0 their product is also nonnegative allowing us to transform (12) into the bound
where the equality is true because P and p^{∗}are the otpimal value and arguments of the primal optimization problem (2). Combining the bounds in (11) and (13) yields
Using the equivalence P=Dof primal and dual optimum values it follows that the inequalities in (13) must hold as equalities. The equality , in particular, implies that the function p^{∗} is the Lagrangian maximizing function corresponding to λ=λ^{∗}, i.e.,
The important consequence of (15) follows from the fact that the Lagrangian maximizer function p(λ^{∗}) is easy to compute using the decomposition in (9). By extension, if the optimal multiplier λ^{∗} is available, computation of the optimal power allocation function p^{∗}also becomes easy. Indeed, making λ=λ^{∗}in (9) we can determine values p^{∗}(h) of p^{∗} as
which are explicitly given by (10) with λ=λ^{∗}.
To complete the problem solution we still need to determine the optimal multiplier λ^{∗}. We show a method for doing so in Section “Dual descent algorithms”, but it is important to recognize that this cannot be a difficult problem because the dual function is singledimensional and convex—dual functions of maximization problems are always convex. This has to be contrasted with the infinite dimensionality of the primal problem. By working in the dual domain we reduce the problem of determining the infinite dimensional optimal power allocation function to the determination of the one dimensional optimal Lagrange multiplier λ^{∗}.
Recapping the derivation of the optimal power allocation p^{∗}, we see that there are three conditions that make (18) simple:
(C1) Since the optimization problem is convex it is equivalent to its Lagrangian dual implying that optimal primal variables can be determined as Lagrangian maximizers associated with the optimal multiplier λ^{∗}[cf. (11)–(15)].
(C2) Due to the separable structure of the Lagrangian, determination of the optimal power allocation function is carried out through the solution of perfading state subproblems [cf. (6)–(9)].
(C3) Because there is a finite number of constraints the dual function is finite dimensional even though there is an infinite number of primal variables.
Most optimization problems in wireless systems are separable in the sense of (C2) and have a finite number of constraints as [cf. (C3)] but are typically not convex [cf. (C1)].
To illustrate this latter point consider a simple variation of (2) where instead of using capacity achieving codes we use adaptive modulation and coding (AMC) relying on a set of L communication modes. The lth mode supports a rate α_{l}and is used when the signal to noise ratio (SNR) at the receiver end is between β_{l−1} and β_{l}. Letting γ be the received SNR and denote the indicator function of the event , the communication rate function C(γ) for AMC can be written as
The corresponding optimal power allocation problem subject to average power constraint q_{0} can now be formulated as
Similar to (2) the dual function of the optimization problem in (18) is one dimensional and its Lagrangian is separable in the sense that we can find Lagrangian maximizers by performing perfading state maximizations. Alas, the problem is not convex because the AMC rate function C(γ) is not concave, in fact, it is not even continuous.
Since it does not satisfy (C1), solving (18) in the dual domain is not possible in principle. Nevertheless the condition that allows determination of p^{∗}(h) as the Lagrangian maximizer p(h,λ^{∗}) [cf. (16)] is not the convexity of the primal problem but the lack of duality gap. We’ll see in Section “Duality in wireless systems optimization” that this problem does have null duality gap as long as the probability distribution of the channel h contains no points of strictly positive probability. Thus, the solution methodology in (3)(16) can be applied to solve (18) despite the discontinuous AMC rate function C(γ). This is actually a quite generic property that holds true for optimization problems where nonconcave functions appear inside expectations. We introduce this generic problem formulation in the next section.
Optimal wireless system design
Let us return to the relationship in (1) where h denotes the random fading state that ranges on a continuous space , p(h) the instantaneous resource allocation, f_{1}(h,p(h)) a vector function mapping h and p(h) to instantaneous system performance, and x an ergodic average. The expectation in (1) is with respect to the joint probability distribution m_{h}(h) of the vector channel h.
It is convenient to think of f_{1}(h,p(h)) as a family of functions indexed by the parameter h with p(h) denoting the corresponding variables. Notice that there is one vector p(h) per fading state h, which translates into an infinite number of resource allocation variables if h takes on an infinite number of values. Consequently, it is adequate to refer to the set of all resource allocations as the resource allocation function. The number of ergodic limits x of interest, on the other hand, is assumed finite.
Instantaneous resource allocations p(h) are further constrained to a given bounded set . These restrictions define a set of admissible resource allocation functions that we denote as
Variables p(h) determine system performance over short periods of times. As such, they are of interest to the system designer but transparent to the end user except to the extent that they determine the value of ergodic variables x. Therefore, we adopt as our design objective the maximization of a concave utility function f_{0}(x) of the ergodic average x. Putting these preliminaries together we write the following program as an abstract formulation of optimal resource allocation problems in wireless systems
where we added further constraints on the set of ergodic averages x. These constraints are in the form of a bounded convex set inclusion and a concave function inequality f_{2}(x)≥0. In the problem formulation in (20) the set is convex and the functions f_{0}(x) and f_{2}(x) are concave. The family of functions f_{1}(h,p(h)) is not necessarily concave with respect to p(h) and the set is not necessarily convex. The sets and are assumed compact to guarantee that x and p(h) are finite. For the expectation in (20) to exist we need to have f_{1}(h,p(h)) integrable with respect to the probability distribution m_{h}(h) of the vector channel h. This imposes a (mild) restriction on the functions f_{1}(h,p(h)) and the power allocation function p. Integrability is weaker than continuity.
For future reference define x^{∗}and p^{∗} as the arguments that solve (20)
The configuration pair (x^{∗},p^{∗}) attains the optimum value P=f_{0}(x^{∗}) and satisfies the constraints and as well as the set constraints , and . Observe that the pair (x^{∗},p^{∗}) need not be unique. It may be, and it is actually a common occurrence in practice, that more than one configuration is optimal. Thus, (21) does not define a pair of variables but a set of pairs of optimal configurations. As it does not lead to confusion we use (x^{∗},p^{∗}) to represent both, the set of optimal configurations and an arbitrary element of this set.
To write the Lagrangian we introduce a nonnegative Lagrange multiplier where λ_{1}≥0 is associated with the constraint and λ_{2}≥0 with the constraint f_{2}(x). The Lagrangian of the primal optimization problem in (20) is then defined as
The corresponding dual function is the maximum of the Lagrangian with respect to primal variables and
The dual problem is defined as the minimum value of the dual function over all nonnegative dual variables
and the optimal dual variables are defined as the arguments that achieve the minimum in (24)
Notice that the optimal dual argument Λ^{∗}is a set as in the case of the primal optimal arguments because there may be more than one vector that achieves the minimum in (24). As we do with the optimal primal variables (x^{∗},p^{∗}), we use Λ^{∗} to denote the set of optimal dual variables and an arbitrary element of this set. A particular example of this generic problem formulation is presented next.
Frequency division broadcast channel
A common access point (AP) administers a power budget q_{0}to communicate with a group of J nodes. The physical layer uses frequency division so that at most one terminal can be active at any given point in time. The goal is to design an algorithm that allocates power and frequency to maximize a given ergodic rate utility metric while ensuring that rates are at least r_{min} and not more than r_{max}.
Denote as h_{i} the channel to terminal i and define the vector h:=[h_{1}…,h_{J}]^{T}grouping all channel realizations. In any time slot the AP observes the realization h of the fading channel and decides on suitable power allocations p_{i}(h) and frequency assignments α_{i}(h). Frequency assignments α_{i}(h) are indicator variables α_{i}(h)∈{0,1} that take value α_{i}(h)=1 when information is transmitted to node i and α_{i}(h)=0 otherwise. If α_{i}(h)=1 communication towards i ensues at power p_{i}(h) resulting in a communication rate C(h_{i}p_{i}(h)/N_{0}) determined by the SNR h_{i}p_{i}(h)/N_{0}. The specific form of the function C(h_{i}p_{i}(h)/N_{0}) mapping channels and powers to transmission rates depends on the type of modulation and codes used. One possibility is to select capacity achieving codes leading to . A more practical choice is to use AMC in which case C(h_{i}p_{i}(h)/N_{0})=C_{AMC}(h_{i}p_{i}(h)/N_{0}) with C_{AMC}(h_{i}p_{i}(h)/N_{0}) as given in (17).
Regardless of the specific form of C(h_{i}p_{i}(h)/N_{0}) we can write the ergodic rate of terminal i as
The factor C(h_{i}p_{i}(h)/N_{0}) is the instantaneous rate achieved if information is conveyed. The factor α_{i}(h) indicates wether this information is indeed conveyed or not. The expectation weights the instantaneous capacity across fading states and is equivalent to the consideration of an infinite horizon time average.
Similarly, p_{i}(h) denotes the power allocated for communication with node i, but this communication is attempted only if α_{i}(h)=1. Thus, the instantaneous power utilized to communicate with i for channel realization h is α_{i}(h)p_{i}(h). The total instantaneous power is the sum of these products for all i and the long term average power consumption can be approximated as the expectation
that according to the problem statement cannot exceed the budget q_{0}.
To avoid collisions between communication attempts the indicator variables α_{i}(h) are restricted so that at most one of them is 1. Define the vector α(h):=[α_{1}(h),…,α_{J}(h)]^{T} corresponding to values of the function and introduce the set of vector functions
We can now express the frequency exclusion constraints as .
We still need to model the restriction that the achieved capacity r_{i} needs to be between r_{min} and r_{max} but this is easily modeled as the constraint r_{min}≤r_{i}≤r_{max}. Defining the vector r=[r_{1},…,r_{J}]^{T} this constraint can be written as with the set defined as
We finally introduce a monotonic nondecreasing utility function U(r_{i}) to measure the value of rate r_{i}and formally state our design goal as the maximization of the aggregate utility . Using the definitions in (26)–(29) the operating point that maximizes this aggregate utility for a frequency division broadcast channel follows from the solution of the optimization problem
where we relaxed the rate expression in (26) to an inequality constraint, which we can do without loss of optimality because the utility U(r_{i}) is monotonic nondecreasing.
The problem formulation in (30) is of the form in (20). The ergodic rates r in (30) are represented by the ergodic variables x in (20) whereas the power and frequency allocation functions p and α of (30) correspond to the resource allocation function pof (20). The set maps to the set and the set to the set . There are no functions in (30) taking the place of the function f_{2}(x) of (20). The function f_{1}(h,p(h)) in (20) is a placeholder for the stacking of the functions α_{i}(h)C(h_{i}p_{i}(h)/N_{0}) for different i and the negative of the power consumptions in (30). The power constraint is not exactly of the form in (1) because q_{0}is a constant not a variable but this doesn’t alter the fundamentals of the problem. The functions α_{i}(h)C(h_{i}p_{i}(h)/N_{0}) are not concave and the set is not convex. This makes the program in (30) nonconvex but is consistent with the restrictions imposed in (20).
To write the Lagrangian corresponding to this optimization problem introduce multipliers λ:=[λ_{1},…,λ_{J}]^{T} associated with the capacity constraints and μassociated with the power constraint. The Lagrangian is then given by
The dual function, dual problem, and optimal dual arguments are defined as in (22)–(25) by replacing for . Since (30) is a nonconvex program we do not know if the dual problem is equivalent to the primal problem. We explore this issue in the following section.
Duality in wireless systems optimization
For any optimization problem the dual minimum D provides an upper bound for the primal optimum value P. This is easy to see by combining the definitions of the dual function in (23) and the Lagrangian in (22) to write
Because the dual function value g(Λ) is obtained by maximizing the right hand side of (32), evaluating this expression for arbitrary primal variables yields an upper bound on g(Λ). Using a pair (x^{∗},p^{∗}) of optimal primal arguments as this arbitrary selection yields the inequality
Since the pair x^{∗},p^{∗} is optimal, it is feasible, which means that we must have and . Lagrange multipliers are also nonnegative according to definition. Therefore, the last two summands in the right hand side of (33) are nonnegative from which it follows that
The inequality in (34) is true for any Λand therefore true for Λ=Λ^{∗}in particular. It then follows that the dual optimum D upper bounds the primal optimum P,
as we had claimed. The difference DP is called the duality gap and provides an indication of the loss of optimality incurred by working in the dual domain.
For the problem in (20) the duality gap is null as long as the channel probability distribution m_{h}(h) contains no point of positive probability as we claim in the following theorem which is a simple generalization of a similar result in [20].
Theorem 1
Let P denote the optimum value of the primal problem (20) and D that of its dual in (24) and assume there exists a strictly feasible point (x_{0},p_{0}) that satisfies the constraints in (20) with strict inequality. If the channel probability distribution m_{h}(h) contains no point of positive probability the duality gap is null, i.e.,
The condition on the channel distribution not having points of positive probability is a mild requirement satisfied by practical fading channel models including Rayleigh, Rice, and Nakagami. The existence of a strictly feasible point (x_{0},p_{0}) is a standard constraint qualification requirement which is also not stringent in practice.
In order to prove Theorem 1 we take a detour in Section “Lyapunov’s convexity theorem” to define atomic and nonatomic measures along with the presentation of Lyapunov’s Convexity Theorem. The proof itself is presented in Section “Proof of Theorem 1”. The implications of Theorem 1 are discussed in Sections “Recovery of optimal primal variables” and “Dual descent algorithms”.
Lyapunov’s convexity theorem
The proof of Theorem 1 uses a theorem by Lyapunov concerning the range of nonatomic measures [22]. Measures assign strictly positive values to sets of a Borel field. When all points have zero measure the measure is called nonatomic as we formally define next.
Definition 1 (Nonatomic measure)
Let w be a measure defined on the Borel field of subsets of a space . Measure w is nonatomic if for any measurable set with w(E_{0})>0, there exist a subset E of E_{0}; i.e., , such that w(E_{0})>w(E)>0.
Familiar measures are probability related, e.g., the probability of a set for a given channel distribution. To build intuition on the notion of nonatomic measure consider a random variable X taking values in [0,1] and [2,3]. The probability of landing in each of these intervals is 1/2 and X is uniformly distributed inside each of them; see Figure 1. The space is the real line, and the Borel field comprises all subsets of real numbers. For every subset define the measure of E as twice the integral of x, weighted by the probability distribution of X on the set E, i.e.,
Figure 1. Nonatomic measure. The random variable X is uniformly distributed in . The measure is nonatomic because all sets of nonzero probability include a smaller set of nonzero probability. Lyapunov’s convexity theorem (Theorem 2) states that the measure range is convex. The range of w_{X}is the, indeed convex, interval [0,3].
Note that, except for the factor 2, the value of w_{X}(E) represents the contribution of the set E to the expected value of X and that when E is the whole space , it holds . According to Definition 1, w_{X}(E) is a nonatomic measure of elements of . Every subset E_{0} with w_{X}(E_{0})>0 includes at least an interval (a,b). The measure of the set E:=E_{0}−((a + b)/2,b) formed by removing the upper half of (a,b) from E_{0} is w_{X}(E)=w_{X}(E_{0})−(b−a)/2. The measure of E satisfies w_{X}(E)>0 as required for w_{X}(E) to be nonatomic.
To contrast this with an example of an atomic measure consider a random variable Y landing equiprobably in [0,1] or 5/2; see Figure 2. In this case, the measure is atomic because the set E_{0}={5/2} has positive measure w_{Y}(E)=1. The only set is the empty set whose measure is null.
Figure 2. Atomic measure. The random variable Y lands with equal probability in Y=5/2 and uniformly in the interval [0,1]. The measure is atomic because the set {1} has strictly positive probability and no set other than the empty set is strictly included in {1}. Theorem 2 does not apply. The range of w_{Y}(E) is the nonconvex union of the intervals [0,1/2] and [5/2,3].
Theorem 2 (Lyapunov’s convexity theorem [[22]]).
Consider nonatomic measures w_{1},…,w_{n}on the Borel field of subsets of a space and define the vector measure w(E):=[w_{1}(E),…,w_{n}(E)]^{T}. The range of the measure wis convex. I.e., if w(E_{1})=w_{1}and w(E_{2})=w_{2}, then for any α∈[0,1] there exists such that w(E_{0})=αw_{1} + (1−α)w_{2}.
The difference between the distributions of X and Y is that Y contains a point of strictly positive probability, i.e., an atom. This implies presence of delta functions in the probability density function of Y . Or, in a rather cleaner statement the cumulative distribution function (cdf) of X is continuous whereas the cdf of Y is not.
Lyapunov’s convexity theorem introduced next refers to the range of values taken by (vector) nonatomic measures.
Returning to the probability measures defined in terms of the probability distributions of the random variables X and Y , Theorem 2 asserts that the range of w_{X}(E), i.e., the set of all possible values taken by w_{X} is convex. In fact, it is not difficult to verify that the range of w_{X}is the convex interval [0,3] as shown in Figure 1. Theorem 2 does not claim anything about w_{Y}. In this case, it is easy to see that the range of w_{Y} is the (nonconvex) union of the intervals [0,1/2] and [5/2,3]; see Figure 2.
Proof of Theorem 1
To establish zero duality gap we will consider a perturbed version of (20) obtained by perturbing the constraints used to define the Lagrangian in (22). The perturbation function P(Δ) assigns to each (perturbation) parameter set the solution of the (perturbed) optimization problem
The perturbed problem in (38) can be interpreted as a modified version of (20), where we allow the constraints to be violated by Δamounts. To prove that the duality gap is zero, it suffices to show that P(Δ) is a concave function of Δ; see, e.g., [23].
Let and be an arbitrary given pair of perturbations. Let (x,p) be a pair of ergodic limits and resource allocation variables achieving the optimum value P(Δ) corresponding to perturbation Δ. Likewise, denote as (x′,p′) a pair that achieves the optimum value P(Δ′) corresponding to perturbation Δ′. For arbitrary α∈[0,1], we are interested in the solution of (38) under perturbation Δ_{α}:=αΔ + (1−α)Δ′. In particular, to show that the perturbation function P(Δ) is concave we need to establish that
The roadblock to establish concavity of the perturbation functions is the constraint . More specifically, the difficulty with this constraint is the ergodic limit . Let us then isolate the challenge by defining the ergodic limit span
The set contains all the possible values that the expectation can take as the resource allocation function pvaries over the admissible set . When the channel distribution m_{h}(h) contains no points of positive probability, the set is convex as we claim in the following theorem.
Theorem 3.
Let be ergodic limit span set in (40). If the channel probability distribution m_{h}(h) contains no point of positive probability the set is convex.
Before proving Theorem 3 let us apply it to complete the proof of Theorem 1. For doing that consider two arbitrary points and . If these points belong to there exist respective resource allocation functions and such that
If is a convex set as claimed by Theorem 3, we must have that for any given α the point y_{α}:=αy + (1−α)y′ also belongs to . In turn, this means there exists a resource allocation function for which
Further define the ergodic limit convex combination x_{α}:=αx + (1−α)x′. We first show that the pair (x_{α},p_{α}) is feasible for the problem for perturbation Δ_{α}.
The convex combination satisfies the constraint because the set is convex. We also have f_{2}(x_{α})≥δ_{2,α} because the function f_{2}(x) is concave. To see that this is true simply notice that concavity of f_{2}(x) implies that . But f_{2}(x)≥δ_{2} and f_{2}(x′)≥δ_{2}′ because x and x′ are feasible in (38) with perturbations Δand Δ′. Substituting these latter two inequalities into the previous one yields according to the definition of Δ_{α}.
We are left to show that the pair (x_{α},p_{α}) satisfies the constraint . For doing so recall that since (x,p) is feasible for perturbation Δand (x′,p′) is feasible for perturbation Δ′we must have
Perform a convex combination of the inequalities in (43) and use the definitions of x_{α}:=αx + (1−α)x′ and to write
Combining (42) and (44) it follows that completing the proof that the pair (x_{α},p_{α}) is feasible for the problem for perturbation Δ_{α}.
The utility yield of this feasible pair is f_{0}(x_{δ}) which we can bound as
Since (x,p) is optimal for perturbation Δ we have f_{0}(x)=P(Δ) and, likewise, f_{0}(x′)=P(Δ′). Further noting that the optimal yield P(Δ_{α}) for perturbation Δ_{α} must exceed the yield f_{0}(x_{α}) of feasible point x_{α}we conclude that
The expression in (46) implies that P(Δ) is a concave function of the perturbation vector Δ. The duality gap is therefore null as stated in (36).
We proceed now to the proof of Theorem 3.
Proof.
(Theorem 3) Consider two arbitrary points and . If these points belong tho there exist respective resource allocation functions and such that
To prove that is a convex set we need to show that for any given αthe point y_{α}:=αy + (1−α)y′ also belongs to . In turn, this means we need to find a resource allocation function for which
For this we will use Theorem 2 (Lyapunov’s convexity theorem). Consider the space of all possible channel realizations , and the Borel field of all possible subsets of . For every s et define the vector measure
where the integrals are over the set E with respect to the channel distribution m_{h}(h). A vector of channel realizations is a point in the space . The set E is a collection of vectors h. Each of these sets is assigned vector measure w(E) defined in terms of the power distributions p(h) and p′(h). The entries of w(E) represent the contribution of realizations h∈Eto the ergodic limits in (48). The first group of entries measure such contributions when the resource allocation is p(h). Likewise, the second group of entries of w(E) denote the contributions to the ergodic limits of the resource distribution p′(h).
Two particular sets that are important for this proof are the empty set, E=∅, and the entire space . For , the integrals in (49) coincide with the expected value operators in (47). We write this explicitly as
For E=∅, or any other zeromeasure set for that matter, we have w(∅)=0.
The measure w(E) is nonatomic. This follows from the fact that the channel distribution contains no points of positive probability combined with the requirement that the resource allocation values p(h) belong to the bounded sets . Combining these two properties it is easy to see that that there are no channel realizations with positive measure, i.e., w(h)=0 for all . This is sufficient to ensure that w(E) is a nonatomic measure.
Being w(E) nonatomic it follows from Theorem 2 that the range of wis convex. Hence, the vector
belongs to the range of possible measures. Therefore, there must exist a set E_{0} such that . Focusing on the entries of w(E_{0}) that correspond to the resource allocation function pit follows that
The analogous relation holds for the entries of w(E_{0}) corresponding to p′, i.e., (52) is valid if p(h) is replaced by p′(h) but this fact is inconsequential for this proof.
Consider now the complement set defined as the set for which and . Given this definition and the additivity property of measures, we arrive at . Combining the latter with (51), yields
We mimick the reasoning leading from (51) to (52), but now we restrict the focus of (53) to the second entries of . It therefore follows that
Define now power distributions p_{α}(h) coinciding with p(h) for channel realization h∈E_{0}and with p′(h) when , i.e.,
The resource distribution p_{α}satisfies the set constraint in (19). Indeed, to see that for all note that p(h) and p′(h) are feasible in their respective problems and as such and for all channels . Because for given channel realization h it holds that either p_{α}(h)=p(h) when h∈E_{0} or p_{α}(h)=p′(h) when it follows that for all channel realizations . According to the definition in (19) this implies that .
Let us now ponder the ergodic limit associated with power allocation p_{α}(h).
Using (52) and (54), the average link capacities for power allocation p_{α}(h) can be expressed in terms of p(h), p′(h) as
The first equality in (56) holds becauset the space is divided into E_{0} and its complement . The second equality is true because when restricted to E_{0}, p_{α}(h)=p(h); and when restricted to , p_{α}(h)=p′(h). The third equality follows from (52) and (54).
Comparing (56) with (48) we see that the power allocation p_{α} yields ergodic limit y_{α}. Therefore implying convexity of as we wanted to show. □
Recovery of optimal primal variables
Having null duality gap means that we can work in the dual domain without loss of optimality. In particular, instead of finding the primal maximum P we can find the dual minimum D, which we know are the same according to Theorem 1. A not so simple matter is how to recover an optimal primal pair (x^{∗},p^{∗}) given an optimal dual vector Λ^{∗}. Observe that recovering optimal variables is more important than knowing the maximum yield because optimal variables are needed for system implementation. In this section we study the recovery of optimum primal variables (x^{∗},p^{∗}) from a given optimal multiplier Λ^{∗}.
Start with an arbitrary, not necessarily optimal, multiplier Λ and define the primal Lagrangian maximizer set as
The elements of (x(Λ),p(Λ)) yield the maximum possible Lagrangian value for given dual variable. Comparing the definition of the dual function in (23) and that of the Lagrangian maximizers in (57) it follows that we can write the dual function g(Λ) as
Particular important pairs of Lagrangian maximizers are those associated with a given optimal dual variable Λ^{∗}. As we show in the following theorem, these variables are related with the optimal primal variables (x^{∗},p^{∗}).
Theorem 4.
For an optimization problem of the form in (20) let denote the Lagrangian maximizer set as defined in (57) corresponding to a given optimal multiplier Λ^{∗}. The optimal argument set is included in this set of Lagrangian maximizers, i.e.,
Proof
Reinterpret (x^{∗},p^{∗}) as a particular pair of optimal primal arguments. Start by noting that the value of the dual function g(Λ^{∗}) can be upper bounded by the Lagrangian evaluated at (x,p)=(x^{∗},p^{∗})
Indeed, the inequality would be true for any and because that is what being the maximum means.
Consider now the Lagrangian that according to (22) we can explicitly write as
Since the pair (x^{∗},p^{∗}) is an optimal argument of (20) we must have and f_{2}(x^{∗})≥0. The multipliers also satisfy and because they are required to be nonnegative. Thus, the last two summands in (61) are nonnegative from where it follows that
Combining (60) and (62) and using the definitions g(Λ^{∗}) and P=f_{0}(x^{∗}) yields
But since according to Theorem 1 the duality gap is null D=P and the inequalities must hold hold as equalities. In particular, we have
which according to (58) means the pair (p^{∗},Λ^{∗}) is a Lagrangian maximizer associated with Λ=Λ^{∗}. Since this is true for any pair of optimal variables (p^{∗},Λ^{∗}) it follows that the set (p^{∗},Λ^{∗}) is included in the set of Lagrangian maximizers as stated in (59). □
According to (59) optimal arguments can be recovered from Lagrangian maximizers associated with optimal multipliers. One has to take care to interpret this set inclusion properly. Equation (59) does not mean that we can always compute by finding Lagrangian maximizers and as such it may or may not be a useful result. If the Lagrangian maximizer pair is unique then the set is a singleton and by extension so is the (included) set of optimal primal variables. In this case Lagrangian maximizers can be used as proxies for optimal arguments. When the set is not a singleton this is not possible and recovering optimal primal variables from optimal multipliers Λ^{∗} is somewhat more difficult.
In general, problems in optimal wireless networking are such that the Lagrangian maximizer resource allocation functions p(Λ^{∗}) are unique to within a set of zero measure. The ergodic limit Lagrangian maximizers x(Λ^{∗}), however, are not unique in many cases. This is more a nuisance than a fundamental problem. Algorithms that find primal optimal operating points regardless of the characteristics of the set of Lagrangian maximizers are studied in Section “Dual descent algorithms”.
Separability
To determine the primal Lagrangian maximizers in (57) it is convenient to reorder terms in the definition in (22) to write
We say that in (22) the Lagrangian is grouped by dual variables because each dual variable appears in only one summand. The expression in (65) is grouped by primal variables because each summand contains a single primal variable if we interpret as a single term and the expectation as a weighted sum—which is not true, but close enough for an intuitive interpretation.
Writing the Lagrangian as in (65) simplifies computation of Lagrangian maximizers. Since there are no constraints coupling the selection of optimal x and p in (65) we can separate the determination of the pair (x(Λ),p(Λ)) in (57) into the determination of the ergodic limits
and the resource allocation function
The computation of the resource allocation function in (67) can be further separated. The set as defined in (19) constrains separate values p(h) of the function pbut doesn’t couple the selection of p(h_{1}) and p(h_{2}) for different channel realizations h_{1}≠h_{2}. Further observing that expectation is a linear operation we can separate (67) into perfading state subproblems of the form
The absence of coupling constraints in the Lagrangian maximization, which permits separation into the ergodic limit maximization in (66) and the perfading maximizations in (68), is the fundamental difference between (57) and the primal problem in (20). In the latter, the selection of optimal x^{∗} and p^{∗} as well as the selection of p(h_{1}) and p(h_{2}) for different channel realizations h_{1}≠h_{2} are coupled by the constraint .
The decomposition in (68) is akin to the decomposition in (16) for the particular case of a point to point channel with capacity achieving codes. It implies that to determine the optimal power allocation p^{∗} it is convenient to first determine the optimal multiplier Λ^{∗}. We then proceed to exploit the lack of duality gap and the separable structure of the Lagrangian to compute values p^{∗}(h) of the optimal resource allocation independently of each other. The computation of optimal ergodic averages is also separated as stated in (66). This separation reduces computational complexity because of the reduced dimensionality of (66) and (68) with respect to that of (20).
For the separation in (66) and (68) to be possible we just need to have a nonatomic channel distribution and ensure existence of a strictly feasible point as stated in the hypotheses of Theorem 1. These two properties are true for most optimal wireless communication and networking problems. A particular example is discussed in the following section.
Frequency division broadcast channel
Consider the optimal frequency division broadcast channel problem in (30) whose Lagrangian is given by the expression in (31). Terms in can be rearranged to uncover the separable structure of the Lagrangian
This rearrangement is equivalent to the generic transformation leading from (22) to (65). As we observed after (65) the computation of Lagrangian maximizing ergodic limits and resource allocation functions can be separated as can the computation of resource allocation values corresponding to different fading channel realizations. This is the case in this particular example. In fact, there is more separability to be exploited in (69).
With regards to primal ergodic variables rnotice that each Lagrangian maximizing rate r_{i}(λ,μ) depends only on λ_{i} and that we can compute each r_{i}(λ,μ)=r_{i}(λ_{i}) separately as
This can be easily computed as U(r_{i}) is a one dimensional concave function. As a particular case consider the identity utility U(r_{i})=r_{i}. Since the Lagrangian becomes a linear function of r_{i}, the maximum occurs at either r_{max}or r_{min} depending on the sign of 1−λ_{i}. When λ_{i}=1 the Lagrangian becomes independent of c_{i}. In this case any value in the interval [r_{min},r_{max}] is a Lagrangian maximizer. Putting these observations together we have
Notice that the Lagrangian maximizer r_{i}(λ_{i}) is not unique if λ_{i}=1. Therefore, if it is not possible to recover the optimal rate from the Lagrangian maximizer corresponding to the optimal multiplier. In fact, an optimal multiplier is uninformative with regards to the optimal ergodic rate as it just implies that which we know is true because this is the feasible range of r_{i}. If you think this is an unlikely scenario because it is too much of a coincidence to have , think again. Having is the most likely situation. If the optimal rate is either or . However, the capacity bounds r_{min}and r_{max}are selected independently of the remaining system parameters. It is quite unlikely—indeed, not true in most cases—that the optimal power and frequency allocation yields a rate determined by these arbitrarily selected parameters.
As we observed in going from (67) to (68) determination of the optimal power and frequency allocation functions requires maximization of the terms inside the expectation. These implies solution of the optimization problems
where we opened up the constraint into its perfading state components.
The maximization in (72) can be further simplified. Begin by noting that irrespectively of the value of α(h) the best possible power allocation p_{i}(h,λ,μ) of terminal i is the one that maximizes its potential contribution to the sum in (72), i.e.,
If α_{i}(h)=1 this contribution is added to the sum in (72). If it is multiplied by α_{i}(h)=0 it is not added to the sum in (72). Either way p_{i}(h,λ,μ) as given by (73) is the optimal power allocation for terminal i.
To determine the frequency allocation α(h,λ,μ) define the discriminants
which we can use to rewrite (72) as
Since at most one α_{i}(h)=1 in (75), the best we can do is to select the terminal with the largest discriminant when that discriminant is positive. If all discriminants are negative the best we can do is to make α_{i}(h)=0 for all i.
The Lagrangian maximizers p_{i}(h,λ,μ) and α(h,λ,μ) in (73) and (75) are almost surely unique for all values of Λand μ. In particular, optimal allocations and α^{∗}(h) can be obtained by making Λ=Λ^{∗}and μ=μ^{∗} in (73)–(75).
Dual descent algorithms
Determining optimal dual variables Λ^{∗} is easier than determining optimal primal pairs (p^{∗},x^{∗}) because there are a finite number of multipliers and the dual function is convex. If the dual function is convex descent algorithms are guaranteed to converge towards the optimum value, which implies we just need to determine descent directions for the dual function.
Descent directions for the dual function can be constructed from the constraint slacks associated with the Lagrangian maximizers. To do so, consider a given Λ and use the definition of the Lagrangian maximizer pair (x(Λ),p(Λ)) in (57) to write the dual function as
Further consider the Lagrangian evaluated at an arbitrary multiplier and primal Lagrangian multipliers corresponding to the given Λ. This Lagrangian lower bounds the dual function value which allows us to write
Subtracting (76) from (77) yields
Defining the vector with components
and recalling the multiplier definitions and we can write
If the dual function g(Λ) is differentiable, the expression in (80) implies that is its gradient. If the dual function is nondifferentiable defines a subgradient of the dual function. In either case is a descent direction of the dual function. This can be verified by substituting M=Λ^{∗} in (80) to conclude that for any Λ∉Λ^{∗}it must be
Since the inner product of and (Λ^{∗}−Λ) is negative the vectors and (Λ^{∗}−Λ) form an angle smaller than Π/2. This can be interpreted as meaning that standing at Λ, the vector points in the direction of Λ^{∗}.
Having a descent direction available we can introduce a time index t and a stepsize ε_{t}to define the dual subgradient descent algorithm as the one with iterates λ(t) obtained through recursive application of
This algorithm is known to converge to optimal dual variables if the stepsize vanishes at a nonsummable rate and to approach Λ^{∗} if the stepsize is constant; see e.g., [20], Section 6.
A problem in implementing (82) is that computing the subgradient component in (79) is costly. To compute , we need to evaluate the expectation where each of the resource allocations p(h,Λ) follows from the solution of the optimization problem in (68). Therefore, to approximate the expectation we need to determine p(h,Λ) for a grid of channel values, which gets impractical if h has large dimension. A Montecarlo approximation of could be computed but that is also costly. Furthermore, to compute we need to know the probability distribution m_{h}(h) which needs to be estimated from channel observations. To overcome these difficulties we replace the gradient in (82) by a stochastic subgradient as we discuss in the following section.
Stochastic subgradient descent
Consider a given channel realization h and given multiplier Λ and define the vector
This definition is made such that the expected value of s_{1}(h,Λ) with respect to the channel distribution is the subgradient component in (79). Thus, if we define the vector with s_{1}(h,Λ) as in (83) and we have
Formally, (84) implies that s(h,Λ) is a stochastic subgradient of the dual function. Intutively, (84) implies that s(h,Λ) is an average descent direction of the dual function because its expectation is a descent direction. Thus, if we draw independent channel realizations h(t) and replace for s(h(t),Λ(t)) in (82) we expect to observe some sort of convergence towards optimum multipliers.
The advantage of this substitution is that to compute the stochastic subgradient s(h,Λ), we do not need to evaluate an expectation as in the case of the subgradient . As a consequence, using stochastic subgradients as descent directions results in an algorithm that is computationally lighter. Perhaps more important, we can operate without knowledge of the channel probability distribution if we use the current channel realization h(t) as our channel sample. These observations motivate the introduction of the following dual stochastic subgradient descent algorithm. (S1) Primal iteration. Given multipliers λ(t) observe current channel realization h(t) and determine primal Lagrangian maximizers [cf. (66) and (68)]
(S2) Dual stochastic subgradient. With the Lagrangian maximizers determined by (85) compute the stochastic subgradient of the dual function with components [cf. (83) and (79)]
(S3) Dual iteration. With stochastic subgradients as in (86) and given step size ε descend in the dual domain along the direction −s(t) [cf. (82)]
The core of the dual stochastic subgradient descent algorithm is the dual iteration (S3). The purpose of the primal iteration (S1) is to compute the stochastic subgradients in (S2) that are needed to implement the dual descent update in (S3). We can think of the primal variables x(Λ(t)) and p(h(t),Λ(t)) as a byproduct of the descent implementation.
Convergence properties depend on whether constant or time varying step sizes are used. If the stepsizes ε_{t} form a nonsummable but square summable series, i.e., and , then using a simple supermartingale argument it can be shown that λ(t) converges to Λ^{∗} almost surely [24]. If constant stepsizes ε_{t}=ε for all t are used, λ(t) does not converge to Λ^{∗} but it can be shown that λ(t) visits a neighborhood of the optimal multiplier set Λ^{∗}[19, Appendix]. Excursions away from this set are possible, but the set is visited infinitely often. The suboptimality of this set is controlled by the step size ε.
If λ(t) approaches or converges to Λ^{∗}it follows as a consequence of Theorem 4 that an optimal primal pair (x^{∗},p^{∗}) can be computed from the Lagrangian maximizers if the latter are unique. Observe that this does not require a separate computation because the Lagrangian maximizers are computed in the primal iteration (S1). One may question that at time t we do not compute the Lagrangian maximizer function p(Λ(t)) but just the single value p(h(t),Λ(t)). However, h(t) is the channel realization at time t which means that p(h(t),Λ(t)) is the value we need to compute to adapt to the current channel realization.
This permits reinterpretation of (S1)–(S3) as a policy to determine wireless systems’ operating points. At time t we observe current channel realization h(t) and determine resource allocation p(h(t),Λ(t)) which we proceed to implement in the current time slot. In this case the core of the algorithm is the primal iteration (S1) and the dual variable λ(t) is an internal state that determines the operating point. Steps (S2) and (S3) are implemented to update this internal state so that as time progresses λ(t) approaches Λ^{∗}and the policy becomes optimal because it chooses the best possible resource allocation adapted to the current channel realization h(t).
The reinterpretation of (S1)–(S3) as a policy to determine resource allocations p(t)=p(h(t),Λ(t)) associated with observed channel realizations h(t) motivates a redefinition of the concept of solution to the wireless optimization problem in (20). In principle, solving (20) entails finding the optimal resource allocation p^{∗} and the optimal ergodic average x^{∗} such that the problem constraints are satisfied and [cf. (21)]. Heeding the interpretation of dual stochastic subgradient descent as a policy, we are interested in the optimality of the sequences of power allocations and average variables generated by (S1)–(S3). Further notice that since (S1)–(S3) is a stochastic algorithm the sequences and generated in a particular run are instantiations of respective random processes and . We are therefore interested in the optimality of the processes and .
To be more specific consider the channel stochastic process whose instances are sequences of channel realizations drawn independently from the channel probability distribution m_{h}(h). Suppose we are also given a sequence of variables drawn from a stochastic process and a resource allocation function p(h) that dictates allocation of resources p(h(t)) for channel realization h(t). Assuming that the process is ergodic, the constraint is equivalent to
Indeed, since and are ergodic processes the limit is a constant that we could denote by x and the limit is equivalent to the expectation .
Writing the constraint in the more cumbersome form shown in (88) has the advantage that the latter can be generalized to cases in which we are given stochastic processes and in which is not necessarily ergodic and realizations p(t) of the process are more general than just functions of the channel state h(t). This concept of solution is formally defined next.
Definition 2
Consider the channel stochastic process whose instances are sequences drawn independently from the channel probability distribution m_{h}(h). We say the stochastic processes and with realizations and problem in (20) if (i) Instantaneous feasibility. Sequence values satisfy the set constraints , for all times t. (ii) Almost sure average feasibility. Ergodic limits of sequences and are feasible with probability 1, i.e.,
(iii) Almost sure optimality. The yield of the ergodic limit of is almost surely optimal, i.e,
If the stochastic process is ergodic and the process is such that realizations p^{‡}(t)=p^{‡}(h(t)) are functions of current channel states, Definition 2 is equivalent to (21) with and p^{∗}(h(t))=p^{‡}(h(t)). Definition 2 is more general because it allows correlation between values of and lets p(t) be more complex than just a function of the current channel realization h(t). This added generality is needed because processes and defined as per (S1)–(S3) yield correlated processes and in which p(t) is a function of the current channel realization h(t) and the current Lagrange multiplier λ(t). Processes and are close to optimal in the sense of Definition 2 as we describe in the following theorem.
Theorem 5 (Ergodic stochastic optimization [[19]])
Consider the optimization problem in (20) as well as processes and generated by the stochastic dual descent algorithm (S1)–(S3). Let be a bound on the second moment of the norm of the stochastic subgradients s(h,Λ) and assume the same hypotheses of Theorem 1. Sequences and are such that: (i) Feasibility. Items (i) and (ii) of Definition 2 hold true. (ii) Near optimality. The ergodic average of x(t) almost surely converges to a value with optimality gap smaller than , i.e,
The sequences and satisfy the constraints in (89) and (90) almost surely and the objective function evaluated at the ergodic limit is within of optimal. Since and are compact sets it follows that the bound is finite. Therefore, reducing ε it is possible to make arbitrarily close to P and as a consequence the sequences and arbitrarily close to optimal. It follows that the processes and generated by (S1)–(S3) are arbitrarily close to processes and that are optimal in the sense of Definition 2.
Variables p^{∗} and x^{∗} optimal in the sense of (21) are not computed by (S1)–(S3). Rather, (89) implies that, asymptotically, (S1)–(S3) is drawing resource allocation realizations p(t)=p(h(t),Λ(t)) and variables x(t):=x(Λ(t)) that are close to optimal as per Definition 2. The important point here is that having a procedure to generate stochastic processes close to optimal in the sense of Definition 2 is sufficient for practical implementation.
An example application of the dual stochastic subgradient descent algorithm (S1)–(S3) is discussed in the next section.
Frequency division broadcast channel
To implement dual stochastic descent for the frequency division broadcast channel we need to specify the primal iteration (S1) and the dual iteration (S2). To specify the primal iteration (S1) we need to compute Lagrangian maximizers for which it suffices to recall the expressions in Section “Frequency division broadcast channel” of “Recovery of optimal primal variables”. For the ergodic rate r_{i} we make λ_{i}=λ_{i}(t) in (70) to conclude that the primal iterate r_{i}(t)=r_{i}(λ_{i}(t)) is
For the power allocations p_{i}(t)=p_{i}(h(t),λ(t),μ(t)) and the frequency assignments α(t)=α(h(t),λ(t),μ(t)) we need to set the multipliers to λ=λ(t) and μ=μ(t) and also set the value of the channel to its current state h=h(t). This substitution in (73) yields the power allocation
To determine the frequency assignments α(t) we first substitute λ=λ(t), μ=μ(t), and h=h(t) in (74) to compute the discriminants d_{i}(t)=d_{i}(h(t),λ(t),μ(t))
from where we conclude that the frequency assignment α(t)=α(h(t),λ(t),μ(t)) is given by the solution of [cf. (75)]
Recall that since at most one α_{i}(h)=1 in (96), the optimal frequency allocation is to make α_{i}(h)=1 for the terminal with the largest discriminant when that discriminant is positive. If all discriminants are negative we make α_{i}(h)=0 for all i.
The ESO algorithm for optimal resource allocation in broadcast channels is completed with an iteration in the dual domain [cf. (83) and (87)]
As per Theorem 5 iterative application of (93)–(97) yields sequences r_{i}(t), α_{i}(t) and p_{i}(t) such that: (i) The sum utility for the ergodic limits of r_{i}(t) is almost surely within a small constant of optimal; (ii) The power constraint in (27) and the rate constraints in (26) are almost surely satisfied in an ergodic sense. This result is true despite the presence of the nonconvex integer constraint , the nonconcave function C(h_{i}p_{i}(t)/N_{0}), the lack of access to the channel’s probability distribution, and the infinite dimensionality of the optimization problem.
Numerical results
The dual stochastic subgradient descent algorithm for optimal resource allocation in frequency division broadcast channels defined by (93)–(97) is simulated for a system with J=16 nodes. Three AMC modes corresponding to capacities 1, 2 and 3 bits/s/Hz are used with transitions at SINR 1, 3 and 7. Fading channels are generated as i.i.d. Rayleigh with average powers 1 for the first four nodes, i.e., j=1,…,4, and 2, 3 and 4 for subsequent groups of 4 nodes. Noise power is N_{0}=1 and average power available is q_{0}=3. Rate of packet acceptance is constrained to be 0≤r_{i}(t)≤2 bits/s/Hz. The optimality criteria is proportional fair scheduling, i.e., for all i. Steps size is ε=0.1.
Figure 3 shows evolution of dual variables λ_{i}(t) and corresponding rates r_{i}(t) for representative nodes i=1 with average channels and i=9 with . The time average rate is also shown. Neither multipliers λ_{i}(t) nor rates r_{i}(t) converge, but ergodic rates do converge. Multiplier λ_{1}(t) associated with node 1 is larger than multiplier λ_{9}(t) of node 9. This improves fairness of resource allocation by increasing the chances of allocating user 1 even when the channel h_{1}(t) is smaller than h_{9}(t)—recall that channel h_{9}(t) is stronger on average. Convergence of the algorithm is ratified by Figures 4 and 5. Figure 4 shows evolution of the objective and the dual function value g(t):=g(λ(t),μ(t)). Notice that the objective value is decreasing towards the maximum objective. This is not a contradiction, because variables are infeasible but approach feasibility as t grows. The dual function’s value is an upper bound on the maximum utility and it can be observed to approach the objective as t grows. Eventually, the objective value becomes smaller than the dual value as expected. Figure 5 corroborates satisfaction of the power constraint in (27) and the rate constraints in (26). The amount by which the power constraint (27) is violated is shown in the top. In the bottom we show the corresponding figure for the rate constraint in (26). Since there are J of these constraints we show the minimum and maximum violation. All constraints are satisfied as t grows. Resulting power allocations appear in Figure 6 for a channel with average power and for a channel with . Power allocation is opportunistic in that power is allocated only when channel realizations are above average.
Figure 3. Primal and dual iterates in dual stochastic gradient descent. Evolution of dual variables λ_{i}(t) and rates r_{i}(t) for representative nodes with average channels and for the algorithm in (93)–(97) are shown. Multipliers λ_{i}(t) and capacities c_{i}(t) do not converge, but ergodic rates do.
Figure 4. Optimal frequency division broadcast channel. Objective value and dual function’s value g(t):=g(λ(t),μ(t)) for the algorithm in (93)–(97) are shown along with lines marking optimal utility and 90% of optimal yield. Utility yield becomes optimal as time grows.
Figure 5. Power and capacity constraints. Feasibility as time grows is corroborated for the power constraint in (27) (top) and rate constraints in (26) (bottom). For the rate constraint we show the maximum and minimum value of constraint violation.
Figure 6. Power allocations. Power allocated as a function of channel realization is shown for channels with average power (top) and (bottom). The resulting power allocation is opportunistic in that power is allocated only when channel realizations are above average.
Conclusions
This article reviews recent results which state that problems of the form in (20) in which nonconcave functions appear inside expectations have null duality gap as long as the probability distribution of the fading coefficient h contains no points of strictly positive probability. Lack of duality gap permits solution in the dual domain leading to a substantial reduction in the computational cost of determining optimal operating points of the wireless system. Working in the dual domain leads to a solution methodology that can be interpreted as a generalization of the derivation of the waterfilling power allocation in point to point channels reviewed in Section “Power allocation in a pointtopoint channel”.
Specifically, the problem of determining the optimal resource allocation function p^{∗} in (20) is challenging due to its infinite dimensionality and lack of convexity. However, in the dual domain we need to determine the optimal multiplier Λ^{∗}that minimizes the dual function in (23). This is simpler because the dual function is convex and finite dimensional. Once we have found an optimal dual variable we can determine optimal operating points as Lagrangian maximizers. In doing so we can exploit the separable structure of the Lagrangian to decompose the optimization problem into the per fading state subproblems in (68). We emphasize that solving the optimization programs in (68) is not necessarily easy if the dimensionality of h is large. Nevertheless solving (68) is always simpler than solving (20) and in some cases plain simple. Lack of duality gap and Lagrangian separability are further exploited to propose the dual stochastic subgradient descent algorithm (S1)–(S3) which converges to an optimal operating point with probability 1 in an ergodic sense.
There are three key points that permit the development of the solution methodology outlined in the previous paragraph: Nonatomic fading distribution. A nonatomic fading distribution leads to the lack of duality gap. The fact that P=D, i.e., that primal and dual optimal values are the same, is what allows us to work in the dual domain without loss of optimality. In formal terms, lack of duality gap is the tool that we used to recover the optimal primal variables (x^{∗},p^{∗}) from the optimal dual variable Λ^{∗}by determining the primal Lagrangian maximizers for [cf. Theorem 4]. It is important to distinguish between convexity of the optimization problem and lack of duality gap. Null duality gap may follow from convexity, but convexity is rare in wireless communications systems. Lack of duality gap can also follow from a nonatomic fading distribution, which is a common occurrence in wireless systems. Lagrangian Separability. According to Theorem 4 null duality gap permits computation of the optimal pair (x^{∗},p^{∗}) as the Lagrangian maximizers (x(Λ^{∗}),p(Λ^{∗})). This is not a simplification per se but leads to a simplification because the computation of the Lagrangian maximizer function p(Λ^{∗}) can be separated into per fading state problems whose solution determines values p(h,Λ^{∗}) of this function [cf. (66)–(68)]. The Lagrangian is separable in this sense because neither the constraints nor the objective function involve a nonlinear function coupling the selection of values p(h_{1}) and p(h_{2}) for different channel realizations h_{1}≠h_{2}. Whenever p(h_{1}) and p(h_{2}) appear as part of the same constraint they appear as different terms of an expectation operation. This absence of coupling is what permits exchanging the order of maximization and expectation in going from (67) to (68). Finite number of constraints. Working in the dual domain is simpler than working in the primal domain because the dual function is finite dimensional whereas the primal problem is infinite dimensional. We have a finite dimensional dual function as long as the original optimization problem has a finite number of constraints.
Nonatomic fading distributions, Lagrangian separability, and having a finite number of constraints are properties that appear in many, indeed most, problems in optimal design of wireless systems. In such cases the methodology described in this article can be applied to their solution.
Further reading
The use of dual problems as a shortcut to solve optimization problems in communications has a rich history [2528]; see also [29] for a comprehensive treatment. Lack of duality gap in nonconvex optimization problems has also been observed in the context of asymmetric digital subscriber lines [30,31]. In network optimization lack of duality gap leads to the optimality of layered architectures which renders the complexity of wireless networking essentially identical to the complexity of physical layer optimization [3235]. For the use of techniques discussed here in the solution of specific problems we refer the reader to [3642]. For further details on dual stochastic sub gradient descent, the literature on convergence of subgradient descent algorithms [4345], and stochastic subgradient descent [4649] is of interest.
Competing interests
The author declares that he has no competing interests.
Acknowledgements
Work in this article is supported by the Army Research Office grant W911NF1010388 and the National Science Foundation award CAREER CCF0952867. Part of the results in this article were derived while the author was at the University of Minnesota. The work presented here has benefited from discussions with Yichuan Hu, Dr. Nikolaos Gatsis, and Prof. Georgios B. Giannakis. The Associate Editor, Dr. Deniz Gunduz, provided valuable corrections to a draft version of this article.
References

X Wang, GB Giannakis, Resource allocation for wireless multiuser OFDM networks. IEEE Trans. Inf. Theory 57(7), 4359–4372 (2011)

V Ntranos, N Sidiropoulos, L Tassiulas, On multicast beamforming for minimum outage. IEEE Trans. Wirel. Commun 8(6), 3172–3181 (2009)

ND Sidiropoulos, TN Davidson, ZQ Luo, Transmit beamforming for physicallayer multicasting. IEEE Trans. Signal Process 54(6), 2239–2251 (2006)

JA Bazerque, GB Giannakis, Distributed scheduling and resource allocation for cognitive OFDMA radios. Mobile Nets. Apps 13(5), 452–462 (2008). Publisher Full Text

Z Quan, S Cui, AH Sayed, Optimal linear cooperation for spectrum sensing in cognitive radio networks. IEEE J. Sel. Topics Signal Process 2, 28–40 (2008)

Y Hu, A Ribeiro, Optimal wireless networks based on local channel state information. IEEE Trans. Signal Process 60(9), 4913–4929 (September 2012)

Y Hu, A Ribeiro, Adaptive distributed algorithms for optimal random access channels. IEEE Trans. Wirel. Commun 10(8), 2703–2715 (2011)

Y Hu, A Ribeiro, A Optimal wireless multiuser channels with imperfect channel state information. Proc. Int. Conf. Acoustics Speech Signal Process, vol. 1, ((Kyoto Japan, 2012), pp), . 1–4

Y Hu, A Ribeiro, Optimal transmission over a fading channel with imperfect channel state information. Global Telecommun. Conf., vol. 1, ((Houston, TX, 2011), pp), . 1–5

L Chen, SH Low, M Chiang, JC Doyle, Crosslayer congestion control, routing and scheduling design in ad hoc wireless networks. Proc. IEEE INFOCOM, vol. 1, ((Barcelona, Spain, 23–29 April 2005), pp), . 1–13

M Chiang, SH Low, RA Calderbank, JC Doyle, Layering as optimization decomposition. Proc IEEE 95, 255–312 (2007)

A Eryilmaz, R Srikant, Joint congestion control, routing, and MAC for stability and fairness in wireless networks. IEEE J. Sel. Areas Commun 24(8), 1514–1524 (2006)

L Georgiadis, MJ Neely, Resource allocation and crosslayer control in wireless networks. Found Trends Netw 1, 1–144 (2006)

JW Lee, RR Mazumdar, NB Shroff, Opportunistic power scheduling for dynamic multiserver wireless systems. IEEE Trans. Wirel. Commun 5(6), 1506–1515 (2006)

X Lin, NB Shroff, R Srikant, A tutorial on crosslayer optimization in wireless networks. IEEE J. Sel. Areas Commun 24(8), 1452–1463 (2006)

MJ Neely, E Modiano, CE Rohrs, Dynamic power allocation and routing for timevarying wireless networks, IEEE J. Sel. Areas Commun 23, 89–103 (2005)

X Wang, K Kar, Crosslayer rate optimization for proportional fairness in multihop wireless networks with random access. IEEE J. Sel. Areas Commun 24(8), 1548–1559 (2006)

Y Yi, S Shakkottai, Hopbyhop congestion control over a wireless multihop network. IEEE/ACM Trans. Netw. 15(133–144), 1548–1559 (2007)

A Ribeiro, Ergodic stochastic optimization algorithms for wireless communication and networking. IEEE Trans. Signal Process 58(12), 6369–6386 (2010)

A Ribeiro, G Giannakis, Separation principles in wireless networking. IEEE Trans. Inf. Theory 56(9), 4488–4505 (2010)

S Boyd, L Vandenberghe, in Convex Optimization (Cambridge University Press, Cambridge, 2004)

AA Lyapunov, Complètement, Sur les, Fonctionsvecteur, URSS, Additives. Bull. Acad. Sci. Sèr. Math 4, 465–478 (1940)

RT Rockafellar, in Convex Analysis (Princeton University Press, Princeton, NJ, 1970)

NZ Shor, in Minimization Methods for NonDifferentiable Functions (Springer, Berlin, 1985)

FP Kelly, A Maulloo, D Tan, Rate control for communication networks: shadow prices, proportional fairness and stability. J. Oper. Res. Soc 49(3), 237–252 (1998)

SH Low, DE Lapsley, Optimization flow control, I: basic algorithm and convergence. IEEE/ACM Trans. Netw 7(6), 861–874 (1998)

SH Low, A duality model of TCP and queue management algorithms. IEEE/ACM Trans. Netw 11(4), 525–536 (2003). Publisher Full Text

SH Low, F Paganini, JC Doyle, Internet congestion control. IEEE Control Syst. Mag 22, 28–43 (2002)

R Srikant, in The Mathematics of Internet Congestion Control (Birkhauser, 2004)

ZQ Luo, S Zhang, Dynamic spectrum management: complexity and duality. IEEE J. Sel. Topics Signal Process 1(2), 57–73 (2008)

W Yu, R Lui, Dual methods for nonconvex spectrum optimization of multicarrier systems. IEEE Trans. Commun 54(7), 1310–1322 (2006)

RA Berry, EM Yeh, Crosslayer wireless resource allocation. IEEE Signal Process. Mag 21(5), 59–68 (2004). Publisher Full Text

MJ Neely, Energy optimal control for timevarying wireless networks. IEEE Trans. Inf. Theory 52(7), 2915–2934 (2006)

MJ Neely, E Modiano, CP Li, Fairness and optimal stochastic control for heterogeneous networks. Proc. IEEE INFOCOM, vol 3 ((Miami, FL 13–17, March 2005), pp), . 1723–1734

A Ribeiro, G Giannakis, Layer separability of wireless networks. Proc. Conf. on Info. Sciences and Systems, vol. 1 ((Princeton Univ), . Princeton, NJ, 2008), pp. 821–826

N Gatsis, A Ribeiro, G Giannakis, A class of convergent algorithms for resource allocation in wireless fading networks. IEEE Trans. Wirel. Commun 9(5), 1808–1823 (2010)

N Gatsis, A Ribeiro, G Giannakis, Crosslayer optimization of wireless fading adhoc networks. Proc. Int. Conf. Acoustics Speech Signal Process, vol. 1 ((Taipei, Taiwan, 2009), pp), . 2353–2356

Y Hu, A Ribeiro, Optimal wireless networks based on local channel state information. Proc. Int. Conf. Acoustics Speech Signal Process, vol. 1 ((Prague Czech Republic, 2011), pp), . 3124–3127

Y Hu, A Ribeiro, Adaptive distributed algorithms for optimal random access channels. Proc. Allerton Conf. on Commun. Control Computing, vol. 1 ((Monticello, 2010), pp), . 1474–1481

A Ribeiro, G Giannakis, Optimal FDMA over wireless fading mobile adhoc networks. Proc. Int. Conf. Acoustics Speech Signal Process, vol. 1 ((Las Vegas, NV, 2008), pp), . 2765–2768

A Ribeiro, T Luo, N Sidiropoulos, G Giannakis, Modelling and optimization of stochastic routing for wireless multihop networks. Proc. IEEE Int. Conf. on Computer Commun, vol. 1 ((Anchorage, AK, 2007), pp), . 1748–1756

A Ribeiro, N Sidiropoulos, G Giannakis, Optimal distributed stochastic routing algorithms for wireless multihop networks. IEEE Trans. Wirel. Commun 7(11), 4261–4272 (2008)

A Juditsky, G Lan, A Nemirovski, A Shapiro, Stochastic approximation approach to stochastic programming. SIAM J. Optim 19(4), 1574–1609 (2009). Publisher Full Text

T Larsson, M Patriksson, A Str omberg, Ergodic primal convergence in dual subgradient schemes for convex programming. Math. Progr 86(2), 283–312 (1999). Publisher Full Text

A Nedic, A Ozdaglar, Approximate primal solutions and rate analysis for dual subgradient methods. SIAM J. Optim 19(4), 1757–1780 (2009). Publisher Full Text

BT Polyak, Newstochasticapproximationtypeprocedures Autom, Remote Control 51, 937–946 (1990)

BT Polyak, AB Juditsky, Acceleration of stochastic approximation by averaging. SIAM J. Control Optim 30(4), 838–855 (1992). Publisher Full Text

A Ribeiro, Stochastic learning algorithms for optimal design of wireless fading networks. Proc. IEEE Workshop on Signal Process. Advances in Wireless Commun vol. 1 ((Marakech, Morocco, 2010), pp), . 1–5

A Ribeiro, Ergodic stochastic optimization algorithms for wireless communication and networking. Proc. Int. Conf. Acoustics Speech Signal Process, vol. 1, ((Dallas, TX, 2010), pp), . 3326–3329