Effect of model uncertainty on some optimal routing problems

We study the effect of model uncertainties on optimal routing in a system of parallel queues. The uncertainty arises in modeling the service time distribution for the customers (jobs, packets) to be served. For a Poisson arrival process and Bernoulli routing, the optimal mean system delay generally depends on the variance of this distribution. However, as the input traffic load approaches the system capacity, the optimal routing assignment and corresponding mean system delay are shown to converge to a variance-invariant point. The implications of these results are examined in the context of gradient-based routing algorithms. An example of a model-independent algorithm using on-line gradient estimation is also included and its performance compared with that of model-based algorithms.This work was supported in part by the National Science Foundation under Grant ECS-88-01912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595.     

A descent algorithm for constrained stochastic extrema

In situations where it is not feasible to find an optimal feedback control law for a stochastic system, an open-loop law can often be derived by optimization. This article presents a method of finding the extremum of certain stochastic functionals analogous to the steepest descent method. Necessary conditions for the convergence of the algorithm are given. Two examples illustrate the use of the algorithm.This research was supported by the Office of Naval Research, Contract No. Nonr-1866 (16) and by the National Aeronautics and Space Administration, Grant No. NGR-22-007-068.     

球面上$\ell_1$正则优化的随机临近梯度方法

本文研究球面上的$\ell_1$正则优化问题,其目标函数由一般光滑函数项和非光滑$\ell_1$正则项构成,且假设光滑函数的随机梯度可由随机一阶oracle估计.这类优化问题被广泛应用在机器学习,图像、信号处理和统计等领域.根据流形临近梯度法和随机梯度估计技术,提出一种球面随机临近梯度算法.基于非光滑函数的全局隐函数定理,分析了子问题解关于参数的Lipschtiz连续性,进而证明了算法的全局收敛性.在基于随机数据集和实际数据集的球面$\ell_1$正则二次规划问题、有限和SPCA问题和球面$\ell_1$正则逻辑回归问题上数值实验结果显示所提出的算法与流形临近梯度法、黎曼随机临近梯度法相比CPU时间上具有一定的优越性.     

An algorithm for minimizing a differentiable function subject to box constraints and errors

We consider the problem of minimizing a differentiable function ofn parameters, with upper and lower bounds on the parameters. The motivation for this work comes from the optimization of the design of transient electrical circuits. In such optimization, the parameters are circuit elements, the bound constraints keep these parameters physically meaningful, and both the function and gradient evaluations contain errors. We describe a quasi-Newton algorithm for such problems. This algorithm handles the box constraints directly and approximates the given function locally by nonsingular quadratic functions. Numerical tests indicate that the algorithm can tolerate the errors, if the errors in the function and gradient are of the same relative size.This paper was presented at the SIAM National Meeting, Chicago, Illinois, 1976.This research was sponsored in part by the Air Force Office of Scientific Research (AFSC), United States Air Force, under Contract No. F44620-76-C-0022.     

Stochastic comparison algorithm for continuous optimization with estimation

The problem of stochastic optimization for arbitrary objective functions presents a dual challenge. First, one needs to repeatedly estimate the objective function; when no closed-form expression is available, this is only possible through simulation. Second, one has to face the possibility of determining local, rather than global, optima. In this paper, we show how the stochastic comparison approach recently proposed in Ref. 1 for discrete optimization can be used in continuous optimization. We prove that the continuous stochastic comparison algorithm converges to an -neighborhood of the global optimum for any >0. Several applications of this approach to problems with different features are provided and compared to simulated annealing and gradient descent algorithms.This work was supported in part by the National Science Foundation under Grants EID-92-12122 and ECS-88-01912, and by a Grant from United Technologies/Otis Elevator Company.     

The optimal control of diffusions

Using a differentiation result of Blagovescenskii and Freidlin calculations of Bensoussan are simplified and the adjoint process identified in a stochastic control problem in which the control enters both the drift and diffusion coefficients. A martingale representation result of Elliott and Kohlmann is then used to obtain the integrand in a stochastic integral, and explicit forward and backward equations satisfied by the adjoint process are derived.This research was partially supported by NSERC under Grant A7964, the U.S. Air Force Office of Scientific Research under Contract AFOSR-86-0332, and the U.S. Army Research Office under Contract DAAL03-87-K-0102.     

Optimal load sharing in soft real-time systems using likelihood ratios

We consider a load-sharing problem for a multiprocessor system in which jobs have real-time constraints: if the waiting time of a job exceeds a given random amount (called the laxity of the job), then the job is considered lost. To minimize the steady-state probability of loss with respect to the load-sharing parameters, we propose to use the likelihood ratio derivative estimate approach, which has recently been studied for sensitivity analysis of stochastic systems. We formulate a recursive stochastic optimization algorithm using likelihood ratio estimates to solve the optimization problem and provide a proof for almost sure convergence of the algorithm. The algorithm can be used for on-line optimization of the real-time system and does not require a priori knowledge of the arrival rate of customers to the system or the service time and laxity distributions. To illustrate our results, we provide simulation examples.This research was partially supported by an IBM Graduate Fellowship and by the National Science Foundation through Grant No. ECS-87-15217.     

Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation

This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.     

On the use of the energy norm in trust-region and adaptive cubic regularization subproblems

We propose a multi-time scale quasi-Newton based smoothed functional (QN-SF) algorithm for stochastic optimization both with and without inequality constraints. The algorithm combines the smoothed functional (SF) scheme for estimating the gradient with the quasi-Newton method to solve the optimization problem. Newton algorithms typically update the Hessian at each instant and subsequently (a) project them to the space of positive definite and symmetric matrices, and (b) invert the projected Hessian. The latter operation is computationally expensive. In order to save computational effort, we propose in this paper a quasi-Newton SF (QN-SF) algorithm based on the Broyden-Fletcher-Goldfarb-Shanno (BFGS) update rule. In Bhatnagar (ACM TModel Comput S. 18(1): 27–62, 2007), a Jacobi variant of Newton SF (JN-SF) was proposed and implemented to save computational effort. We compare our QN-SF algorithm with gradient SF (G-SF) and JN-SF algorithms on two different problems – first on a simple stochastic function minimization problem and the other on a problem of optimal routing in a queueing network. We observe from the experiments that the QN-SF algorithm performs significantly better than both G-SF and JN-SF algorithms on both the problem settings. Next we extend the QN-SF algorithm to the case of constrained optimization. In this case too, the QN-SF algorithm performs much better than the JN-SF algorithm. Finally we present the proof of convergence for the QN-SF algorithm in both unconstrained and constrained settings.     

Robustness of perturbation analysis estimators for queueing systems with unknown distributions

Sample-path-based stochastic gradient estimators for performance measures of queueing systems rely on the assumption that a probability distribution of the random vector of interest (e.g., a service or interarrival time sequence) is given. In this paper, we address the issue of dealing with unknown probability distributions and investigate the robustness of such estimators with respect to possibly erroneous distribution choices. We show that infinitesimal perturbation analysis (IPA) can be robust in this sense and, in some cases, provides distribution-independent estimates. Comparisons with other gradient estimators are provided, including experimental results. We also show that finite perturbation analysis (FPA), though only providing gradient approximations, possesses some attractive robustness properties with respect to unknown distribution parameters. An application of FPA estimation is included for a queueing system performance optimization problem involving customers with real-time constraints.This work was supported in part by the National Science Foundation Grant ECS-88-01912 and by the Office of Naval Research Contract N00014-87-K-0304.The authors wish to thank Dr. Jack Holtzman for several useful comments and suggestions.