Optimal scheduling of parallel queues using stochastic flow models

We consider a classic scheduling problem for optimally allocating a resource to multiple competing users and place it in the framework of Stochastic Flow Models (SFMs). We derive Infinitesimal Perturbation Analysis (IPA) gradient estimators for the average holding cost with respect to resource allocation parameters. These estimators are easily obtained from a sample path of the system without any knowledge of the underlying stochastic process characteristics. Exploiting monotonicity properties of these IPA estimators, we prove the optimality of the well-known cμ-rule for an arbitrary finite number of queues and stochastic processes under non-idling policies and linear holding costs. Further, using the IPA derivative estimates obtained along with a gradient-based optimization algorithm, we find optimal solutions to similar problems with nonlinear holding costs extending current results in the literature.     

Perturbation Analysis for Stochastic Fluid Queueing Systems

Recent study for congestion control in high speed networks indicates that the derivative information for the congestion at the common buffer for multiple sources could be useful in achieving efficient and fair allocation of the bandwidth (Kelly, 1997; Kelly et al., 1998). In this paper we present an algorithm that estimates such derivatives for multiple on-off sources. The algorithm has its root in the infinitesimal perturbation analysis (IPA) for the classical queueing systems. Although the traditional IPA algorithm does not give unbiased derivative estimates for multi-class arrivals, we are able to prove the unbiasedness in the case of multi-class ON-OFF sources. The results in this paper may motivate a new look at the end-to-end congestion control issue.     

On Evaluating SFM-Based Infinitesimal Perturbation Analysis Estimates From Discrete Event System Data

This paper investigates the evaluation of infinitesimal perturbation analysis (IPA) estimates that have been derived based on a stochastic fluid model (SFM) using data observed from the sample path of a discrete event system (DES). First, we show that a straightforward implementation of the SFM-based IPA estimates may yield biased estimates when the data are obtained from the actual DES. Then, in order to better approximate the sample path of the DES, we propose a special case of SFM where the arrival and service processes are modeled by piecewise constant on/off sources. The proposed SFM violates some of the assumptions made in [1]-[4] , and, as a result, the sample derivatives no longer exist. However, using the proposed SFM, we obtain the left and right sided sample derivative estimates. As shown in this paper, the sided sample derivatives are much better in approximating the required derivatives compared to the straightforward implementation of the SFM-based IPA estimates.     

Using infinitesimal perturbation analysis of stochastic flow models to recover performance sensitivity estimates of discrete event systems

Stochastic Flow Models (SFMs) form a class of hybrid systems used as abstractions of complex Discrete Event Systems (DES) for the purpose of deriving performance sensitivity estimates through Infinitesimal Perturbation Analysis (IPA) techniques when these cannot be applied to the original DES. In this paper, we establish explicit connections between gradient estimators obtained through a SFM and those obtained in the underlying DES, thus providing analytical evidence for the effectiveness of these estimators which has so far been limited to empirical observations. We consider DES for which analytical expressions of IPA (or finite difference) estimators are available, specifically G/G/1 and G/G/1/K queueing systems. In the case of the G/G/1 system, we show that, when evaluated on the same sample path of the underlying DES, the IPA gradient estimators of states, event times, and various performance metrics derived through SFMs are, under certain conditions, the same as those of the associated DES or their expected values are asymptotically the same under large traffic rates. For G/G/1/K systems without and with feedback, we show that SFM-based derivative estimates capture basic properties of finite difference estimates evaluated on a sample path of the underlying DES.     

Characterizing and approximating eigenvalue sets of symmetric interval matrices

We consider the eigenvalue problem for the case where the input matrix is symmetric and its entries are perturbed, with perturbations belonging to some given intervals. We present a characterization of some of the exact boundary points, which allows us to introduce an inner approximation algorithm, that in many case estimates exact bounds. To our knowledge, this is the first algorithm that is able to guarantee exactness. We illustrate our approach by several examples and numerical experiments.     

Learning a factor model via regularized PCA

We consider the problem of learning a linear factor model. We propose a regularized form of principal component analysis (PCA) and demonstrate through experiments with synthetic and real data the superiority of resulting estimates to those produced by pre-existing factor analysis approaches. We also establish theoretical results that explain how our algorithm corrects the biases induced by conventional approaches. An important feature of our algorithm is that its computational requirements are similar to those of PCA, which enjoys wide use in large part due to its efficiency.     

Fitted strong stability-preserving schemes for the Black-Scholes-Barenblatt equation

We solve numerically a fully nonlinear Black–Scholes problem of Bellman type. The algorithm is focused on the so-called Delta greek, the first spatial derivative of the option price. Since the elliptic operator degenerates on the boundary we use a fitted finite volume discretization in space. Strong stability-preserving time-marching is further applied in accordance to the nonlinear nature of the differential problem. Numerical experiments validate our considerations.     

有向传感器网络中基于概率感知模型的最小连通k覆盖集算法

无线传感器网络的基本问题之一是,网络节点如何利用有限的能量对人们所关注的物理世界进行满意的监测,这可抽象为最小连通k覆盖集问题。传统的最小连通k覆盖集问题是基于确定型全向感知模型的,该模型过于理想化,不能适用于复杂的应用环境,也不能应用于有向传感器网络中。针对上述局限,本文提出了有向传感器网络中基于概率感感知模型的最小连通k覆盖集问题（MCKS）,并指出这是NP难问题;设计了基于0-1整数规划和最小生成树的集中式近 BDA）,分别证明两种算法最终得到的是MCKS问题的可行解,并分析了算法的时间复杂度、性能比和通信复杂度。通过仿真实验并与ILP算法和BGA算法进行比较的结果表明： 在基于概率感知模型的条件下,IPA和CBDA能够有效实现有向传感器网络中的连通k覆盖,并且激活节点数目较少,网络寿命延长。     

Motion estimation and segmentation

In the general structure-from-motion (SFM) problem involving several moving objects in a scene, the essential first step is to segment moving objects independently. We attempt to deal with the problem of optical flow estimation and motion segmentation over a pair of images. We apply a mean field technique to determine optical flow and motion boundaries and present a deterministic algorithm. Since motion discontinuities represented by line process are embedded in the estimation of the optical flow, our algorithm provides accurate estimates of optical flow especially along motion boundaries and handles occlusion and multiple motions. We show that the proposed algorithm outperforms other well-known algorithms in terms of estimation accuracy and timing.     

American option pricing problem transformed on finite interval

We study the American option pricing linear complementarity problem (LCP), transformed on finite interval as it is initially defined on semi-infinite real axis. We aim to validate this transformation, investigating the well-posedness of the resulting problem in weighted Sobolev spaces. The monotonic penalty method reformulates the LCP as a semi-linear partial differential equation (PDE) and our analysis of the penalized problem results in uniform convergence estimates. The resulting PDE is further discretized by a fitted finite volume method since the transformed partial differential operator degenerates on the boundary. We show solvability of the semi-discrete and fully discrete problems. The Brennan–Schwarz algorithm is also presented for comparison of the numerical experiments, given in support to our theoretical considerations.     

一种改进的智能电网能耗调度算法

为了提高电网的运行效率,提出一种新的实时能耗调度算法,通过考虑负载不确定性来实现每个用户的电费最小化.我们将负载调度描述为一个优化问题.为了降低计算复杂度,提出一种近似动态规划算法,以解决电器运行的调度问题.在研究问题时,考虑了必须运行和可控运行在内的不同电器.与大部分当前需求侧管理算法假设完全知晓用户用电需求不同,算法只需知道将来部分需求的估计即可.仿真结果表明,能量调度算法既降低了用户用电支出,又提高了负载需求的峰均比,为用户和电力公司带来收益.     

Perturbation analysis and optimization of stochastic flow networks

We consider a stochastic fluid model of a network consisting of several single-class nodes in tandem and perform perturbation analysis for the node queue contents and associated event times with respect to a threshold parameter at the first node. We then derive infinitesimal perturbation analysis (IPA) derivative estimators for loss and buffer occupancy performance metrics with respect to this parameter and show that these estimators are unbiased. We also show that the estimators depend only on data directly observable from a sample path of the actual underlying discrete event system, without any knowledge of the stochastic characteristics of the random processes involved. This renders them computable in online environments and easily implementable for network management and optimization. This is illustrated by combining the IPA estimators with standard gradient based stochastic optimization methods and providing simulation examples.     

A semi-direct approach to structure from motion

The problem of structure from motion is often decomposed into two steps: feature correspondence and three-dimensional reconstruction. This separation often causes gross errors when establishing correspondence fails. Therefore, we advocate the necessity to integrate visual information not only in time (i.e. across different views), but also in space, by matching regions – rather than points – using explicit photometric deformation models. We present an algorithm that integrates image-feature tracking and three-dimensional motion estimation into a closed loop, while detecting and rejecting outlier regions that do not fit the model. Due to occlusions and the causal nature of our algorithm, a drift in the estimates accumulates over time. We describe a method to perform global registration of local estimates of motion and structure by matching the appearance of feature regions stored over long time periods. We use image intensities to construct a score function that takes into account changes in brightness and contrast. Our algorithm is recursive and suitable for real-time implementation.     

Interval Methods for Sinusoidal Parameter Estimation: A Comparative Analysis

In this paper, we address the problem of determining maximum-likelihood estimates of sinusoid parameters from a signal that consists of sinusoids and additive noise. We present three algorithms that integrate interval methods for global optimization with procedures that decompose the problem into smaller ones. Interval methods represent a global optimization technique that is based upon the branch and bound principle. More specifically, we decompose the problems via the expectation-maximization algorithm and variations of the coordinate descent algorithm. Although, we have not proven that the proposed algorithms converge to the global optimum, their performance in our simulation example was much superior to that of the popular iterative quadratic maximum likelihood (IQML) method.     

Bayesian shape estimation: Shape-from-shading and photometric stereo revisited

We present a Bayesian approach to the machine vision processes of shape-from-shading and photometric stereo, also considering the associated question of the detection of shape discontinuities. The shape reconstruction problem is formulated as a maximum a posteriori (MAP) estimation from probability distributions of Gibbs form, and is solved via simulated annealing. In shape-from-shading, our formulation leads to a constrained optimization problem, where the constraints come from the image irradiance equation and from the incorporation of the necessary boundary conditions. In photometric stereo, we are able to estimate shape directly from degraded input images. We also propose an edge-detection algorithm that works cooperatively with the reconstruction process, employing the shape estimates to locate the discontinuities of the reconstructed surface. We show results of the application of our framework both to synthetic and to real imagery.     

Steerable local frequency based multispectral multifocus image fusion

Design of a focus measure and a fusion algorithm which will perform well across different spectra remains an extremely challenging task. In this work, the problem of multispectral multifocus image fusion is addressed using the phase information of the source image pixels at different orientations. We make the local frequency, the spatial derivative of the local phase of the pixels, steerable to obtain a good novel focus measure. Oriented analytic image based on the theory of steerable filters is constructed for that purpose. A multifocus fusion algorithm is proposed next using this focus measure. Comprehensive experimentations clearly demonstrate that our focus measure as well as the multifocus fusion algorithm yield promising results across the visual (VIS), the near-infrared (NIR) and the thermal (TH) spectra.     

基于改进图像导数框架的颜色恒常性计算方法

在基于图像导数框架的颜色恒常性算法的基础上,进一步考虑边缘类型和颜色通道间的相关性对于光照色度估计的影响,提出一种基于改进图像导数框架的颜色恒常性计算方法。根据导数图像中像素的饱和度提出一种饱和度权值方案;基于光学特性对导数图像中的边缘进行分类,通过引入照度准不变量提出类型相关的边缘权值方案;将两种权值方案与图像导数框架相结合,并据此进行光照色度估计,利用von Kries对角变换对偏色图像进行校正。实验结果表明该算法有效提高了光照色度估计的准确性,改善了颜色恒常性算法的效果。     

On derivative estimation of single-server queues via structural infinitesimal perturbation analysis

In Dai and Ho (1994) we developed a method, referred to asstructural infinitesimal perturbation analysis (SIPA), to address the need for derivative estimation with respect to a special type of parameter. However, it was not clear how much computational effort is required to implement this method. Derivative estimation via SIPA can be complicated in implementation. Such computational problems, also arise in several other derivative estimation methods. In this paper we take SIPA as a typical method and apply it to a special class of DEDS-several variations of single-server queues, focusing on the issue of implementation. We demonstrate that SIPA can be efficiently implemented. In some cases, it can be as simple as theinfinitesimal perturbation analysis (IPA), method which is considered to be the most efficient method available so far. The main approach we take is to combine SIPA with finite perturbation analysis and cut-and-paste techniques. Explicit formulae are given to various problems, some being impossible to solve using the traditional IPA method. Numerical examples are employed to illustrate the results.     

递推鲁棒频域辨识算法

本文研究了带未建模动态系统的频域辨识问题，辨识结果为传递函在单位圆上的有限个点估计及其误差界。理论分析和仿真结果都表明，本文采取的求取误差界的方法比文［４］的方法导致更佳的估计和较小的误差界。     

Uncovering delayed patterns in noisy and irregularly sampled time series: An astronomy application

We study the problem of estimating the time delay between two signals representing delayed, irregularly sampled and noisy versions of the same underlying pattern. We propose and demonstrate an evolutionary algorithm for the (hyper)parameter estimation of a kernel-based technique in the context of an astronomical problem, namely estimating the time delay between two gravitationally lensed signals from a distant quasar. Mixed types (integer and real) are used to represent variables within the evolutionary algorithm. We test the algorithm on several artificial data sets, and also on real astronomical observations of quasar Q0957+561. By carrying out a statistical analysis of the results we present a detailed comparison of our method with the most popular methods for time delay estimation in astrophysics. Our method yields more accurate and more stable time delay estimates. Our methodology can be readily applied to current state-of-the-art optical monitoring data in astronomy, but can also be applied in other disciplines involving similar time series data.