Search

Smoothed functional (SF) algorithm estimates the gradient of the stochastic optimization problem by convolution with a smoothening kernel. This process helps the algorithm to converge to a global minimum or a point close to it. We study a two-time scale SF based gradient search algorithm with Nesterov’s acceleration for stochastic optimization problems. The main contribution of our work is to prove the convergence of this algorithm using the stochastic approximation theory. We propose a novel Lyapunov function to show the associated second-order ordinary differential equations’ (o.d.e.) stability for a non-autonomous system. We compare our algorithm with other smoothed functional algorithms such as Quasi-Newton SF, Gradient SF and Jacobi Variant of Newton SF on two different optimization problems: first, on a simple stochastic function minimization problem, and second, on the problem of optimal routing in a queueing network. Additionally, we compared the algorithms on real weather data in a weather prediction task. Experimental results show that our algorithm performs significantly better than these baseline algorithms.

This paper deals with the management of multimode sensors such as multifunction radars. We consider the problems of multitarget radar scheduling formulated as multivariate partially observed Markov decision process (POMDPs). The aim is to compute the scheduling policy to determine which target to choose and how long to continue with this choice so as to minimize a cost function. We give sufficient conditions on the cost function, dynamics of the Markov chain target and observation probabilities so that the optimal scheduling policy has a threshold structure with respect to the multivariate TP2 ordering. This implies that the optimal parameterized policy can be estimated efficiently. We then present stochastic approximation algorithms for estimating the best multilinear threshold policy. [ABSTRACT FROM AUTHOR]

We consider the optimal sensor scheduling problem formulated as a partially observed Markov decision process (POMDP). Due to operational constraints, at each time instant, the scheduler can dynamically select one out of a finite number of sensors and record a noisy measurement of an underlying Markov chain. The aim is to compute the optimal measurement scheduling policy, so as to minimize a cost function comprising of estimation errors and measurement costs. The formulation results in a nonstandard POMDP that is nonlinear in the information state. We give sufficient conditions on the cost function, dynamics of the Markov chain and observation probabilities so that the optimal scheduling policy has a threshold structure with respect to a monotone likelihood ratio (MLR) ordering. As a result, the computational complexity of implementing the optimal scheduling policy is inexpensive. We then present stochastic approximation algorithms for estimating the best linear MLR order threshold policy. [ABSTRACT FROM AUTHOR]

High-speed downlink packet access (HSDPA) achieves high data rates and high spectral efficiency by using adaptive modulation and coding schemes and employing multicode CDMA. In this paper, we present opportunistic algorithms for scheduling HSDPA users and selecting modulation/coding and multicode schemes that exploit channel and buffer variations to increase the probability of uninterrupted media play-out. First, we introduce a stochastic discrete event model for a HSDPA system. By employing the discrete event model, we transform the scheduling problem of providing uninterrupted play-out to a feasibility problem that considers two sets of stochastic quality-of-service (QoS) constraints: stability constraints and robustness constraints. A methodology for obtaining a feasible solution is then proposed by starting with a so-called stable algorithm that satisfies the stability QoS constraints. Next, we present stochastic approximation algorithms that adapt the parameters of the stable algorithm in a way that a feasible point for the robustness QoS is reached within the feasibility region of the stability QoS [ABSTRACT FROM PUBLISHER]