引入D2D通信的蜂窝网上行资源分配算法

该文研究了引入Device-to-Device (D2D)通信的蜂窝网系统中的上行资源分配问题。首先将该问题建模为一个简洁的二值整数规划问题。然而整数规划仍是NP难问题。该文利用Canonical对偶理论,得到其对偶形式。该对偶问题是一个连续域内的凸问题。证明了在特定的条件下,可以通过求解对偶问题得到原问题的最优解,且对偶间隙为零。提出了一个基于Barrier方法的算法来求解对偶问题。仿真结果表明,该文的算法优于现有算法,且性能接近最优。     

Dual Ascent for Uncapacitated Telecommunications Network Design with Access,Backbone, and Switch Costs

We consider the telecommunications network design problem of simultaneously determining at which locations to place a switch, interconnecting all switches with backbone trunks, and connecting each location to some switch by an access circuit. We assume there are no capacity constraints, and minimize the sum of switch, backbone trunk, and access circuit costs using a dual ascent method that solves a sequence of dual uncapacitated facility location problems. A Steiner tree based heuristic provides a primal feasible design. On 15 random problems with 100 locations, the average duality gap is 2.0%.     

A Tutorial on Decomposition Methods for Network Utility Maximization

A systematic understanding of the decomposability structures in network utility maximization is key to both resource allocation and functionality allocation. It helps us obtain the most appropriate distributed algorithm for a given network resource allocation problem, and quantifies the comparison across architectural alternatives of modularized network design. Decomposition theory naturally provides the mathematical language to build an analytic foundation for the design of modularized and distributed control of networks. In this tutorial paper, we first review the basics of convexity, Lagrange duality, distributed subgradient method, Jacobi and Gauss–Seidel iterations, and implication of different time scales of variable updates. Then, we introduce primal, dual, indirect, partial, and hierarchical decompositions, focusing on network utility maximization problem formulations and the meanings of primal and dual decompositions in terms of network architectures. Finally, we present recent examples on: systematic search for alternative decompositions; decoupling techniques for coupled objective functions; and decoupling techniques for coupled constraint sets that are not readily decomposable.     

Duality Gap Estimation and Polynomial Time Approximation for Optimal Spectrum Management

Consider a communication system whereby multiple users share a common frequency band and must choose their transmit power spectra jointly in response to physical channel conditions including the effects of interference. The goal of the users is to maximize a system-wide utility function (e.g., weighted sum-rate of all users), subject to individual power constraints. A popular approach to solve the discretized version of this nonconvex problem is by Lagrangian dual relaxation. Unfortunately the discretized spectrum management problem is NP-hard and its Lagrangian dual is in general not equivalent to the primal formulation due to a positive duality gap. In this paper, we use a convexity result of Lyapunov to estimate the size of duality gap for the discretized spectrum management problem and show that the duality gap vanishes asymptotically at the rate O (1/radicN), where N is the size of the uniform discretization of the shared spectrum. If the channels are frequency flat, the duality gap estimate improves to O (1/N) . Moreover, when restricted to the FDMA spectrum sharing strategies, we show that the Lagrangian dual relaxation, combined with a linear programming scheme, can generate an epsiv-optimal solution for the continuous formulation of the spectrum management problem in polynomial time for any epsiv > 0.     

Geometric programming duals of channel capacity and rate distortion

We show that the Lagrange dual problems of the channel capacity problem with input cost and the rate distortion problem are simple geometric programs. Upper bounds on channel capacity and lower bounds on rate distortion can be efficiently generated from their duals. For channel capacity, the geometric programming dual characterization is shown to be equivalent to the minmax Kullback-Leibler (KL) characterization in Csiszar et al. (1981). For rate distortion, the geometric programming dual is extended to rate distortion with two-sided state information. A "duality by mapping" is then given between the Lagrange dual problems of channel capacity with input cost and rate distortion, which resolves several apparent asymmetries between their primal problems in the familiar form of mutual information optimization problems. Both the primal and dual problems can be interpreted in a common framework of free energy optimization from statistical physics.     

The dual parameterization approach to optimal least square FIRfilter design subject to maximum error constraints

This paper is concerned with the design of linear-phase finite impulse response (FIR) digital filters for which the weighted least square error is minimized, subject to maximum error constraints. The design problem is formulated as a semi-infinite quadratic optimization problem. Using a newly developed dual parameterization method in conjunction with the Caratheodory's dimensional theorem, an equivalent dual finite dimensional optimization problem is obtained. The connection between the primal and the dual problems is established. A computational procedure is devised for solving the dual finite dimensional optimization problem. The optimal solution to the primal problem can then be readily obtained from the dual optimal solution. For illustration, examples are solved using the proposed computational procedure     

Reciprocity, discretization, and the numerical solution of directand inverse electromagnetic radiation and scattering problems

The author gives a formulation, based on Lorentz reciprocity, that unifies the finite element method (FEM) and the integral equation models. Wave propagation and scattering problems in electromagnetics have to be addressed with the aid of numerical techniques. Many of these methods can be envisaged as being discretized versions of appropriate weak formulations of the pertinent operator (differential or integral) equations. For the relevant problems as formulated in the time Laplace-transform domain it is shown that the Lorentz reciprocity theorem encompasses all known weak formulations, while its discretization leads to the discretized forms of the corresponding operator equations, in particular to their finite-element and integral-equation modeling schemes. Both direct (forward) and inverse problems are discussed     

FFT computation with linear processor arrays using a data-driven control scheme

We consider the practical design of linear controllers to meet a given set ofH ₂ specifications. TheQ-parametrization reduces the problem to a quadratic minimization subject to multiple quadratic constraints, which we solve using semi-definite programming (SDP) methods. Each SDP iteration requires calculating a primal and dual search direction and minimizing the cost function along the plane defined by these search directions. The primal direction requires solving a least squares problem whose normal equation matrix is composed of a block-Toeplitz portion plus other structured matrices. We make use of Kronecker products and FFT's to greatly reduce the calculation. The dual search direction and plane search are accelerated by low-rank representations of the SDP structured matrices. As an example, we design controllers which explore the optimal tradeoff between in-band residual and out-of-band enhancement of acoustic radiation from a (mathematically modeled) submerged spherical shell, while simultaneously constraining two sensitivity measures. For this example we show that significant reduction in out-of-band enhancement is possible with only minor in-band penalties.     

A duality model of TCP and queue management algorithms

We propose a duality model of end-to-end congestion control and apply it to understanding the equilibrium properties of TCP and active queue management schemes. The basic idea is to regard source rates as primal variables and congestion measures as dual variables, and congestion control as a distributed primal-dual algorithm over the Internet to maximize aggregate utility subject to capacity constraints. The primal iteration is carried out by TCP algorithms such as Reno or Vegas, and the dual iteration is carried out by queue management algorithms such as DropTail, RED or REM. We present these algorithms and their generalizations, derive their utility functions, and study their interaction.     

FFT computation with linear processor arrays using a data-driven control scheme

We consider the practical design of linear controllers to meet a given set ofH ₂ specifications. TheQ-parametrization reduces the problem to a quadratic minimization subject to multiple quadratic constraints, which we solve using semi-definite programming (SDP) methods. Each SDP iteration requires calculating a primal and dual search direction and minimizing the cost function along the plane defined by these search directions. The primal direction requires solving a least squares problem whose normal equation matrix is composed of a block-Toeplitz portion plus other structured matrices. We make use of Kronecker products and FFT's to greatly reduce the calculation. The dual search direction and plane search are accelerated by low-rank representations of the SDP structured matrices.As an example, we design controllers which explore the optimal tradeoff between in-band residual and out-of-band enhancement of acoustic radiation from a (mathematically modeled) submerged spherical shell, while simultaneously constraining two sensitivity measures. For this example we show that significant reduction in out-of-band enhancement is possible with only minor in-band penalties.This work was supported by the Office of Naval Research under Contract N00014-94-C-0128     

Multi-cell uplink-downlink beamforming throughput duality based on Lagrangian duality with per-base station power constraints

Despite significant research efforts in beamforming, the maximum achievable downlink throughput with beamforming in a multi-cell environment is not available due to difficulty in finding optimal downlink beamforming. Thus, to reformulate the problem into a more solvable form, we derive dual uplink throughput optimization problem to multi-cell downlink beam- forming throughput maximization with per-base station (BS) power constraints based on Lagrangian duality. The optimal downlink beamforming is shown to be a minimum mean squared error (MMSE) beamforming in the dual uplink. It is also shown that the dual uplink problem achieves the same optimal throughput as the primal downlink problem.     

Uplink-downlink duality via minimax duality

The sum capacity of a Gaussian vector broadcast channel is the saddle point of a minimax Gaussian mutual information expression where the maximization is over the set of transmit covariance matrices subject to a power constraint and the minimization is over the set of noise covariance matrices subject to a diagonal constraint. This sum capacity result has been proved using two different methods, one based on decision-feedback equalization and the other based on a duality between uplink and downlink channels. This paper illustrates the connection between the two approaches by establishing that uplink-downlink duality is equivalent to Lagrangian duality in minimax optimization. This minimax Lagrangian duality relation allows the optimal transmit covariance and the least-favorable-noise covariance matrices in a Gaussian vector broadcast channel to be characterized in terms of the dual variables. In particular, it reveals that the least favorable noise is not unique. Further, the new Lagrangian interpretation of uplink-downlink duality allows the duality relation to be generalized to Gaussian vector broadcast channels with arbitrary linear constraints. However, duality depends critically on the linearity of input constraints. Duality breaks down when the input constraint is an arbitrary convex constraint. This shows that the minimax representation of the broadcast channel sum capacity is more general than the uplink-downlink duality representation     

Modeling and efficient optimization for object-based scalabilityand some related problems

MPEG-4 is the first visual coding standard that allows coding of scenes as a collection of individual audio-visual objects. We present mathematical formulations for modeling object-based scalability and some functionalities that it brings with it. Our goal is to study algorithms that aid in semi-automating the authoring and subsequent selective addition/dropping of objects from a scene to provide content scalability. We start with a simplistic model for object-based scalability using the "knapsack problem"-a problem for which the optimal object set can be found using known schemes such as dynamic programming, the branch and bound method and approximation algorithms. The above formulation is then generalized to model authoring or multiplexing of scalable objects (e.g., objects encoded at various target bit-rates) using the "multiple choice knapsack problem." We relate this model to several problems that arise in video coding, the most prominent of these being the bit allocation problem. Unlike previous approaches to solve the operational bit allocation problem using Lagrangean relaxation, we discuss an algorithm that solves linear programming (LP) relaxation of this problem. We show that for this problem the duality gap for Lagrange and LP relaxations is exactly the same. The LP relaxation is solved using strong duality with dual descent-a procedure that can be completed in "linear" time. We show that there can be at most two fractional variables in the optimal primal solution and therefore this relaxation can be justified for many practical applications. This work reduces problem complexity, guarantees similar performance, is slightly more generic, and provides an alternate LP-duality based proof for earlier work by Shoham and Gersho (1988). In addition, we show how additional constraints may be added to impose inter-dependencies among objects in a presentation and discuss how object aggregation can be exploited in reducing problem complexity. The marginal analysis approach of Fox (1966) is suggested as a method of re-allocation with incremental inputs. It helps in efficiently re-optimizing the allocation when a system has user interactivity, appearing or disappearing objects, time driven events, etc. Finally, we suggest that approximation algorithms for the multiple choice knapsack problem, which can be used to quantify complexity vs. quality tradeoff at the encoder in a tunable and universal way.     

Analysis of heterogeneous electromagnetic scatterers: researchprogress of the past decade

A review of the current status of integral equation and finite element (FEM) (including time domain) modeling as applied particularly to penetrable bodies is provided. The direct numerical solution of the appropriate frequency-domain partial differential equations is an alternative that has recently been the focus of much effort by the research community and appears to offer computational advantages over the integral equation formulations. These frequency-domain approaches require the solution of a matrix equation; the direct time-domain solution of partial differential equations offers a third formulation that does not require a matrix solution and may be more efficient for electrically large structures. The author summarizes the development of these modeling procedures and attempts to identify some of the unresolved issues associated with their development     

三维目标电磁散射矢量有限元/边界元法的公式研究

研究应用于三维目标电磁散射分析的矢量有限元/边界元混合方法不同公式.分析表明,混合公式系统矩阵的条件数随边界元采用不同公式有很大差异,从而导致混合公式的稳定性有很大不同.并讨论了混合方法中边界元部分的单一检验基函数方法和组合检验基函数方法.认为组合检验基函数方法仍可被视为单一检验基函数方法;通过比较边界元部分使用单一检验基函数法和组合检验基函数法时所得计算结果,纠正了只有使用组合检验基函数,有限元/边界元混合方法才能得到精确结果的结论.综合考虑计算结果可靠性、精度及对内部谐振的免疫力等因素,给出了所推荐使用的有限元/边界元混合方法公式.     

基于CPU-GPU协同并行内点算法求解结构化非线性规划

大量工程应用问题可建模为结构化非线性规划,且这类问题的系数矩阵可分为稀疏型和稠密型两种类型.利用原始-对偶内点法（primal dual interior point method,PD-IPM）,并结合分布式并行技术可高效求解此类问题.经典工程问题-机组组合（unit commitment,UC）为稀疏系数矩阵的结构化非线性规划,本文根据PD-IPM原理,对UC模型进行连续松弛预处理,结合快速解耦技术解耦牛顿修正方程并设计CPU-GPU协同并行算法求解子问题,最后将结果与带稠密型子问题的结构化非线性规划的求解结果进行比较和分析.实验结果显示,本文所设计的算法对于两种不同类型的结构化非线性规划求解均能获得较好的加速比.     

Iterative rate-distortion optimization of H.264 with constant bit rate constraint

In this paper, we apply the primal-dual decomposition and subgradient projection methods to solve the rate-distortion optimization problem with the constant bit rate constraint. The primal decomposition method enables spatial or temporal prediction dependency within a group of picture (GOP) to be processed in the master primal problem. As a result, we can apply the dual decomposition to minimize independently the Lagrangian cost of all the MBs using the reference software model of H.264. Furthermore, the optimal Lagrange multiplier lambda* is iteratively derived from the solution of the dual problem. As an example, we derive the optimal bit allocation condition with the consideration of temporal prediction dependency among the pictures. Experimental results show that the proposed method achieves better performance than the reference software model of H.264 with rate control.     

A MacWilliams Identity for Convolutional Codes: The General Case

A MacWilliams identity for convolutional codes will be established. It makes use of the weight adjacency matrices of the code and its dual, based on state space realizations (the controller canonical form) of the codes in question. The MacWilliams identity applies to various notions of duality appearing in the literature on convolutional coding theory.     

A numerical investigation of interior resonances in the hybrid FEM/MoM method

The interior resonance problem that can occur when using a hybrid finite-element method/method of moments (FEM/MoM) method to model electromagnetic scattering problems is investigated. Calculations of the bistatic radar cross section of a coated dielectric sphere are presented using different formulations, solution approaches, and solvers. The solutions using the electric-field integral equation have significant errors near an interior resonance frequency. When the combined-field integral equation is employed, satisfactory solutions can be obtained that do not depend on the particular solution approach or solver.     

Dual forms for constrained adaptive filtering

A new structure for constrained adaptive filtering is proposed. It is based on a “dual” solution of the constrained minimization problems that arise in optimal broadband adaptive array processing. The dual solution is unique in the sense that its update equations involve the Lagrange multipliers rather than the adaptive filter weights. The dual approach is shown to be applicable to two types of adaptive filtering (or beamforming) problems. One is the linearly constrained power minimization beamformer and the other is the norm constrained robust beamformer. In each case, the equations defining the dual structure are derived, and the convergence of the resulting iteration is analyzed. Simulation results are included to illustrate the performance of the dual algorithms compared with the primal methods. It is shown that the convergence and computational complexity of the dual algorithms are similar to that of RLS-type algorithms