Stochastic optimization with averaging of trajectories

A recursive stochastic optimization procedure under dependent disturbances is studied. It is based on the Polyak-Ruppert algorithm with trajectory averaging. Almost sure convergence of the algorithm is proved as well as asymptotic normality of the delivered estimates. It is shown that the presented algorithm attains the highest possible asymptotic convergence rate for stochastic approximation algorithms     

Auxiliary model identification method for multirate multi-input systems based on least squares

This paper derives state-space models for multirate multi-input sampled-data systems. Based on the corresponding transfer function models, an auxiliary model based recursive least squares algorithm is presented to identify the parameters of the multirate systems from the multirate input–output data. Further, convergence properties of the proposed algorithm are analyzed. Finally, an illustrative example is given.     

On-line identification of parameters of a linear multivariable discrete-time system and their convergence characteristics

A recursive algorithm for on-line identification of the parameters of linear, discrete-time, multi-input, multi-output nondynamical, and dynamical systems using noisy input and output measurements is presented in detail. Necessary and sufficient conditions for the convergence of the recursive algorithm, under certain restrictive assumptions, for arbitrary choice of initial values of the matrices described in the sequel are explicitly derived, which is one of the new results of this paper.     

递推阻尼最小二乘法的收敛性与稳定性

递推最小二乘法是参数辨识中最常用的方法,但容易产生参数爆发现象.因此对一种更稳定的辨识方法——递推阻尼最小二乘法进行了收敛特性的分析.在使用算法之前先归一化测量向量,结果表明,参数化距离收敛于一个零均值随机变量,并且在持续激励条件下,适应增益矩阵的条件数有界.参数化距离的方差有界.     

Online EM Algorithm for Hidden Markov Models

Online (also called “recursive” or “adaptive”) estimation of fixed model parameters in hidden Markov models is a topic of much interest in times series modeling. In this work, we propose an online parameter estimation algorithm that combines two key ideas. The first one, which is deeply rooted in the Expectation-Maximization (EM) methodology, consists in reparameterizing the problem using complete-data sufficient statistics. The second ingredient consists in exploiting a purely recursive form of smoothing in HMMs based on an auxiliary recursion. Although the proposed online EM algorithm resembles a classical stochastic approximation (or Robbins–Monro) algorithm, it is sufficiently different to resist conventional analysis of convergence. We thus provide limited results which identify the potential limiting points of the recursion as well as the large-sample behavior of the quantities involved in the algorithm. The performance of the proposed algorithm is numerically evaluated through simulations in the case of a noisily observed Markov chain. In this case, the algorithm reaches estimation results that are comparable to those of the maximum likelihood estimator for large sample sizes. The supplemental material for this article available online includes an appendix with the proofs of Theorem 1 and Corollary 1 stated in Section 4 as well as the MATLAB/OCTAVE code used to implement the algorithm in the case of a noisily observed Markov chain considered in Section 5.     

An RQP algorithm using a differentiable exact penalty function for inequality constrained problems

In this paper we propose a recursive quadratic programming algorithm for nonlinear programming problems with inequality constraints that uses as merit function a differentiable exact penalty function. The algorithm incorporates an automatic adjustment rule for the selection of the penalty parameter and makes use of an Armijo-type line search procedure that avoids the need to evaluate second order derivatives of the problem functions. We prove that the algorithm possesses global and superlinear convergence properties. Numerical results are reported.     

A relaxed version of Bregman's method for convex programming

A new type of relaxation for Bregman's method, an iterative primal-dual algorithm for linearly constrained convex programming, is presented. It is shown that the new relaxation procedure generalizes the usual concept of relaxation and preserves the convergence properties of Bregman's algorithm for a suitable choice of the relaxation parameters. For convergence, Bregman's method requires that the objective function satisfy certain conditions. A sufficient and easily checkable condition for these requirements to hold is also given.     

Approximation of an Analog Diffusion Network with Applications to Image Estimation

This work is concerned with a numerical procedure for approximating an analog diffusion network. The key idea is to take advantage of the separable feature of the noise for the diffusion machine and use a parallel processing method to develop recursive algorithms. The asymptotic properties are studied. The main result of this paper is to establish the convergence of a continuous-time interpolation of the discrete-time algorithm to that of the analog diffusion network via weak convergence methods. The parallel processing feature of the network makes it attractive for solving large-scale optimization problems. Applications to image estimation are considered. Not only is this algorithm useful for the image estimation problems, but it is widely applicable to many related optimization problems.     

Convergence of orthogonal greedy algorithm with errors in projectors

A model of orthogonal greedy algorithm is proposed. This model allows one to consider computational errors and to study the stability of this algorithm with respect to errors in projections onto subspaces. A criterion for the convergence of orthogonal greedy expansion to the expanded element is given in terms of computational errors.     

基于凸组合共轭梯度法的ARIMA模型参数估计

提出了一种凸组合共轭梯度算法,并将其算法应用到ARIMA模型参数估计中.新算法由改进的谱共轭梯度算法与共轭梯度算法作凸组合构造而成,具有下述特性:1)具备共轭性条件;2)自动满足充分下降性.证明了在标准Wolfe线搜索下新算法具备完全收敛性,最后数值实验表明通过调节凸组合参数,新算法更加快速有效,通过具体实例证实了模型的显著拟合效果.     

Estimation of IIR Systems with Binary-Valued Observations*

Estimation and control problems with binary-valued observations exist widely in practical systems. However, most of the related works are devoted to finite impulse response (FIR for short) systems, and the theoretical problem of infinite impulse response (IIR for short) systems has been less explored. To study the estimation problems of IIR systems with binary-valued observations, the authors introduce a projected recursive estimation algorithm and analyse its global convergence properties, by using the stochastic Lyapunov function methods and the limit theory on double array martingales. It is shown that the estimation algorithm has similar convergence results as those for FIR systems under a weakest possible non-persistent excitation condition. Moreover, the upper bound for the accumulated regret of adaptive prediction is also established without resorting to any excitation condition.     

Data-driven recursive least squares methods for non-affined nonlinear discrete-time systems

Aiming at identifying nonlinear systems, one of the most challenging problems in system identification, a class of data-driven recursive least squares algorithms are presented in this work. First, a full form dynamic linearization based linear data model for nonlinear systems is derived. Consequently, a full form dynamic linearization-based data-driven recursive least squares identification method for estimating the unknown parameter of the obtained linear data model is proposed along with convergence analysis and prediction of the outputs subject to stochastic noises. Furthermore, a partial form dynamic linearization-based data-driven recursive least squares identification algorithm is also developed as a special case of the full form dynamic linearization based algorithm. The proposed two identification algorithms for the nonlinear nonaffine discrete-time systems are flexible in applications without relying on any explicit mechanism model information of the systems. Additionally, the number of the parameters in the obtained linear data model can be tuned flexibly to reduce computation complexity. The validity of the two identification algorithms is verified by rigorous theoretical analysis and simulation studies.     

Bayesian Inference via Filtering for a Class of Counting Processes: Application to the Micromovement of Asset Price

This paper highlights recent developments in a rich class of counting process models for the micromovement of asset price and in the Bayesian inference (estimation and model selection) via filtering for the class of models. A specific micromovement model built upon linear Brownian motion with jumping stochastic volatility is used to demonstrate the procedure to develop a micromovement model with specific tick-level sample characteristics. The model is further used to demonstrate the procedure to implement Bayes estimation via filtering, namely, to construct a recursive algorithm for computing the trade-by-trade Bayes parameter estimates, especially for the stochastic volatility. The consistency of the recursive algorithm model is proven. Simulation and real-data examples are provided as well as a brief example of Bayesian model selection via filtering.     

The rate of convergence of weak greedy approximations over orthogonal dictionaries

The convergence rate of a weak orthogonal greedy algorithm is studied for the subspace ?¹ ? ?² and orthogonal dictionaries. It is shown that general results on convergence rate of weak orthogonal greedy algorithms can be essentially improved in the studied case. It is also shown that this improvement is asymptotically sharp.     

Computational methods for modifying seemingly unrelated regressions models

Computational efficient methods for updating seemingly unrelated regressions models with new observations are proposed. A recursive algorithm to solve a series of updating problems is developed. The algorithm is based on orthogonal transformations and has as main computational tool the updated generalized QR decomposition (UGQRD). Strategies to compute the orthogonal factorizations by exploiting the block-sparse structure of the matrices are designed. The problems of adding and deleting exogenous variables from the seemingly unrelated regressions model have also been investigated. The solution of these problems utilize the strategies for computing the UGQRD.     

Particle-based online estimation of tangent filters with application to parameter estimation in nonlinear state-space models

This paper presents a novel algorithm for efficient online estimation of the filter derivatives in general hidden Markov models. The algorithm, which has a linear computational complexity and very limited memory requirements, is furnished with a number of convergence results, including a central limit theorem with an asymptotic variance that can be shown to be uniformly bounded in time. Using the proposed filter derivative estimator, we design a recursive maximum likelihood algorithm updating the parameters according the gradient of the one-step predictor log-likelihood. The efficiency of this online parameter estimation scheme is illustrated in a simulation study.

     

A recursive quadratic programming algorithm that uses differentiable exact penalty functions

In this paper, a recursive quadratic programming algorithm for solving equality constrained optimization problems is proposed and studied. The line search functions used are approximations to Fletcher's differentiable exact penalty function. Global convergence and local superlinear convergence results are proved, and some numerical results are given.     

采用增广拉格朗日乘子形式的罚函数作线性搜索的递归等式约束二次逼近算法

1.引言 本文所讨论的问题如下: Min f(x) x∈R~n, s.t. c_i(x)=0,i=1,…,q,(1.1) c_i(x)≤0,i=q+1,…,p.解此问题的递归等式约束二次逼近算法,是由Murry(1969)提出,而后由Biggs(1972)发展的.此项研究是从罚函数的轨迹出发,建立一个只包含等式约束的二次规划子问题,从而可用代数的方法求得搜索方向.并沿该方向作线性搜索而完成一次迭代过程.Biggs将二次罚函数作为效应函数用于线性搜索,并证明了该算法具有全局收敛性和局部超线     

An algorithm for solving the eigenvalue problem for a class of operator pencils

We study the generalized eigenvalue problem for a uniformly hyperbolic or totally hyperbolic polynomial operator pencil of arbitrary order. In the context of the variational approach to the problem of determining the eigenvalues of such pencils we propose and justify a recursive algorithm for finding an eigenpair. To accelerate the convergence we propose using the Rayleigh-Ritz procedure. We give data from a numerical implementation of the algorithm. Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, No. 37, 1994, pp. 24–28.     

On the orthogonality of residual polynomials\newline of minimax polynomial preconditioning

Summary. This paper studies polynomials used in polynomial preconditioning for solving linear systems of equations. Optimum preconditioning polynomials are obtained by solving some constrained minimax approximation problems. The resulting residual polynomials are referred to as the de Boor-Rice and Grcar polynomials. It will be shown in this paper that the de Boor-Rice and Grcar polynomials are orthogonal polynomials over several intervals. More specifically, each de Boor-Rice or Grcar polynomial belongs to an orthogonal family, but the orthogonal family varies with the polynomial. This orthogonality property is important, because it enables one to generate the minimax preconditioning polynomials by three-term recursive relations. Some results on the convergence properties of certain preconditioning polynomials are also presented. Received February 1, 1992/Revised version received July 7, 1993