The fundamentally fluctuating nature of the strength of a wireless link poses a significant challenge when seeking to achieve reliable communication at high data rates. Common sense, supported by information theory, tells us that one can move closer towards achieving higher data rates if the transmitter is provided with a priori knowledge of the channel. Such channel knowledge is typically provided to the transmitter by a feedback channel that is present between the receiver and the transmitter. The quality of information provided to the transmitter is proportional to the bandwidth of this feedback channel. Thus, the design of feedback channels is a key aspect in enabling high data rates. In the past, these feedback channels have been designed locally, on a link-by-link basis. While such an approach can be globally optimal in some cases, in many other cases, this is not true. In this thesis, we identify various settings in wireless networks, some already a part of existing standards, others under discussion in future standards, where the design of feedback channels is a problem that requires global, network-wide optimization. In general, we propose the treatment of feedback bandwidth as a network-wide resource, as the next step en route to achieving Gigabit wireless. Not surprisingly, such a global optimization initiative naturally leads us to the important issue of computational efficiency. Computational efficiency is critical from the point-of-view of a network provider. A variety of optimization techniques are employed in this thesis to solve the large combinatorial problems that arise in the context of feedback allocation. These include dynamic programming, sub-modular function maximization, convex relaxations and compressed sensing. A naive algorithm to solve these large combinatorial problems would typically involve searching over a exponential number of possibilities to find the optimal feedback allocation. As a general theme, we identify and exploit special application-specific structure to solve these problems optimally with reduced complexity. Continuing this endeavour, we search for more intricate structure that enables us to propose approximate solutions with significantly-reduced complexity. The accompanying analysis of these algorithms studies the inherent trade-offs between accuracy, efficiency and the required structure of the problem. / text

<p>Efficient global dynamic optimization (GDO) using spatial branch-and-bound (SBB) requires the ability to construct tight bounds for the dynamic model. This thesis works toward efficient GDO by developing effective convex relaxation techniques for models with ordinary differential equations (ODEs). In particular, a novel algorithm, based upon a verified interval ODE method and the McCormick relaxation technique, is developed for constructing convex and concave relaxations of solutions of nonlinear parametric ODEs. In addition to better convergence properties, the relaxations so obtained are guaranteed to be no looser than their underlying interval bounds, and are typically tighter in practice. Moreover, they are rigorous in the sense of accounting for truncation errors. Nonetheless, the tightness of the relaxations is affected by the overestimation from the dependency problem of interval arithmetic that is not addressed systematically in the underlying interval ODE method. To handle this issue, the relaxation algorithm is extended to a Taylor model ODE method, which can provide generally tighter enclosures with better convergence properties than the interval ODE method. This way, an improved version of the algorithm is achieved where the relaxations are generally tighter than those computed with the interval ODE method, and offer better convergence. Moreover, they are guaranteed to be no looser than the interval bounds obtained from Taylor models, and are usually tighter in practice. However, the nonlinearity and (potentially) nonsmoothness of the relaxations impedes their fast and reliable solution. Therefore, the algorithm is finally modified by incorporating polyhedral relaxations in order to generate relatively tight and computationally cheap linear relaxations for the dynamic model. The resulting relaxation algorithm along with a SBB procedure is implemented in the MC++ software package. GDO utilizing the proposed relaxation algorithm is demonstrated to have significantly reduced computational expense, up to orders of magnitude, compared to existing GDO methods.</p> / Doctor of Philosophy (PhD)