Search

Propagation of errors in identifying constant coefficient parameters of a discrete time linear system, using stochastic approximation algorithms, is investigated. Error and sensitivity analysis algorithms are derived for the cases when there is structural modeling error as well as when the a priori statistics of identified parameters, and plant and measurement noise, are incorrectly specified. The error and sensitivity analysis algorithms are useful as a design tool to better specify appropriate identification algorithms for actual implementation. The error and sensitivity analysis algorithms are applied to several examples including identification of eight predictor coefficients for adaptive digitized speech transmission.

Following the convergence proofs for stochastic approximation identification of pure autoregressive (AR) processes with dependent observations, as derived by Saridis and Stein, it is shown that the convergence for mixed autoregressive-moving-average (ARMA) cases can also be proved when none of the AR or the MA parameters or of the covariances are assumed known. Consequently, a generalized stochastic approximations identification procedure for ARMA processes is derived, which is extendable to any linear Kalrman filter models.

The parameter identification problem in the theory of adaptive control systems is considered from the point of view of stochastic approximation. A generalized algorithm for on-line identification of a stochastic linear discrete-time system using noisy input and output measurements is presented and shown to converge in the mean-square sense. The algorithm requires knowledge of the noise variances involved. It is shown that this requirement is a disadvantage associated with on-line identification schemes based on minimum mean-square-error criteria. The paper also presents two off-line identification schemes which utilize measurements obtained from repeated runs of the system's transient response and do not require explicit knowledge of the noise variances. These algorithms converge with probability one to the true parameter values.

The aim of this paper is the provision of a framework for a practical stochastic unconstrained optimization theory. The results are based on certain concepts of stochastic approximation, although not restricted to those procedures, and aim at incorporating the great flexibility of currently available deterministic optimization ideas into the stochastic problem, whenever optimization must be done by Monte Carlo or sampling methods. Hills with nonunique stationary points are treated. A framework has been provided, with which convergence of stochastic versions of conjugate gradient, partan, etc., can be discussed and proved.

A stochastic approximation procedure that minimizes a mean-square-error criterion is proposed in this paper. It is applied first to derive an algorithm for recursive estimation of the mean-square-error approximation of the function which relates the input signals and the responses of a memoryless system. The input signals are assumed to be generated at random with an unknown probability density function, and the response is measured with an error which has zero mean and finite variance. A performance index for evaluating the rate of convergence of the algorithm is defined and then the optimal form of the algorithm is derived. It is shown that the least-square-error fit of the measured output signals of the systems offers a recursive formula which is a special case of the proposed algorithm. A recursive formula for estimation of a priori probabilities of the pattern classes using unclassified samples is then presented. The rate of convergence is computed. A minimum square-error estimate of a continuous probability density function is also obtained by the same algorithm.

In a typical instance of a network design problem, we are given a directed or undirected graph G = (V,E), non-negative edge-costs ce for all e ∈ E, and our goal is to find a minimum-cost subgraph H of G that satisfies some design criteria. For example, we may wish to find a minimum-cost set of edges that induces a connected graph (this is the minimum-cost spanning tree problem), or we might want to find a minimum-cost set of arcs in a directed graph such that every vertex can reach every other vertex (this is the minimum-cost strongly connected subgraph problem). This abstract model for network design problems has a large number of practical applications; the design process of telecommunication and traffic networks, and VLSI chip design are just two examples. Many practically relevant instances of network design problems are NP-hard, and thus likely intractable. This survey focuses on approximation algorithms as one possible way of circumventing this impasse. Approximation algorithms are efficient (i.e., they run in polynomial-time), and they compute solutions to a given instance of an optimization problem whose objective values are close to those of the respective optimum solutions. More concretely, most of the problems discussed in this survey are minimization problems. We then say that an algorithm is an α-approximation for a given problem if the ratio of the cost of an approximate solution computed by the algorithm to that of an optimum solution is at most α over all instances. In the following we will also sometimes refer to α as the performance guarantee of the respective approximation algorithm. The last 30 years have seen a tremendous amount of research on approximation algorithms for network design problems. And over this period, several technical themes have emerged, and have been explored and exploited to give algorithms and analyze their performance. Our aim in this survey is to provide an overview over these techniques. Each of the following sections focuses on one technique and has two main parts: first, we present an introductory application to the well-known classical minimum-spanning tree problem. The second part of each section demonstrates more sophisticated recent example applications of the respective technique. Throughout we assume that the reader is familiar with fundamental concepts of graph theory, combinatorial optimization, and approximation algorithms. While we may recap certain key definitions, we rely on the reader to be familiar with others. We refer to the excellent text books [45, 160, 163] for background reading. The minimum spanning tree problem has been studied for at least a century, and it is clearly one of the most prominent network design problems. The input to an instance of this problem consists of an undirected graph G = (V,E) each of whose edges e ∈ E is endowed by an arbitrary cost ce, and the goal is to compute a spanning tree of smallest cost. The earliest known algorithm for this problem was developed by Boruvka [ ˙ 21], and since then a vast number of techniques have been developed and subsequently used in order to devise increasingly sophisticated algorithms.

The paper gives convergence theorems for several sequential Monte-Carlo or stochastic approximation algorithms for finding a local minimum of a function $f(\bullet)$ on a set $C$ defined by $C = \{x: q^i(x) \leqq 0, i = 1, 2, \cdots, s\}. f(\bullet)$ is unknown, but "noise perturbed" values can be observed at any desired parameter $x \in C$. The algorithms generate a sequence of random variables $\{X_n\}$ such that (for a.a. $\omega$) any convergent subsequence of $\{X_n(\omega)\}$ converges to a point where a certain necessary condition for constrained optimality holds. The techniques are drawn from both stochastic approximation, and non-linear programming.

This study presents the conditions of applicability of stochastic approximation algorithms that minimize a mean-square error criterion for identification of a linear discrete-time stationary system without dynamical numerator. The acceleration of the convergence is discussed. Then a tentative is outlined to overcome the previous requirement of states accessibility.

In the test cover problem a set of m items is given together with a collection of subsets, called tests. A smallest subcollection of tests is to be selected such that for each pair of items there is a test in the selection that contains exactly one of the two items. It is known that the problem is NP-hard and that the greedy algorithm has a performance ratio O(log m). We observe that, unless P=NP, no polynomial-time algorithm can do essentially better. For the case that each test contains at most k items, we give an O(log k)-approximation algorithm. We pay special attention to the case that each test contains at most two items. A strong relation with a problem of packing paths in a graph is established, which implies that even this special case is NP-hard. We prove APX-hardness of both problems, derive performance guarantees for greedy algorithms, and discuss the performance of a series of local improvement heuristics.

This paper considers embeddings f of arbitrary finite metrics into the line metric ℜ so that none of the distances is shrunk by the embedding f; the quantity of interest is the factor by which the average distance in the metric is stretched. We call this quantity the average distortion of the non-contracting map f. We prove that finding the best embedding of even a tree metric into a line metric to minimize the average distortion is NP-hard, and hence focus on approximating the average distortion of the best possible embedding for the given input metric. We give a constant-factor approximation for the problem of embedding general metrics into the line metric. For the case of n-point tree metrics, we provide a quasi-polynomial time approximation scheme which outputs an embedding with distortion at most (1 + e) times the optimum in time nO(log n/e^2). Finally, when the average distortion is measured only over the endpoints of the edges of an input tree metric, we show how to exploit the structure of tree metrics to give an exact solution in polynomial time.

We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an edge weighted graph G = (V, E), in the edge based upgrading model, it is assumed that each edge e of the given network also has an associated function ce (t) that specifies the cost of upgrading the edge by an amount t. A reduction strategy specifies for each edge e the amount by which the length ℓ(e) is to be reduced. In the node based upgrading model, a node v can be upgraded at an expense of c(v). Such an upgrade reduces the delay of each edge incident on v. For a given budget B, the goal is to find an improvement strategy such that the total cost of reduction is at most the given budget B and the cost of a subgraph (e.g. minimum spanning tree) under the modified edge lengths is the best over all possible strategies which obey the budget constraint. After providing a brief overview of the models and definitions of the various problems considered, we present several new results on the complexity and approximability of network improvement problems.

This paper considers the identification problem of linear control systems by use of stochastic approximation. There are two approaches to constructing models based on stochastic approximation: dynamical model approach and finite memory model one. In the former approach Saridis and Stein [1] have obtained the most general results. And in the latter approach Holmes [2] has established an algorithm giving an unbiased estimate. But it is common with these two works that (i) only white noise sequence is allowed for the input sequence and (ii) the updating of the estimates occurs at every finite time interval.

This correspondence considers the application of stochastic approximation algorithms to a broad class of system identification problems. Both asymptotic and initial convergence properties of the algorithms are discussed. A suboptimal procedure for parameter selection and a means of convergence acceleration are suggested.