Stochastic approximation problem is to find some root or extremum of a nonlinear function for which only noisy measurements of the function are available. The classical algorithm for stochastic approximation problem i...Stochastic approximation problem is to find some root or extremum of a nonlinear function for which only noisy measurements of the function are available. The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm, which uses the noisy evaluation of the negative gradient direction as the iterative direction. In order to accelerate the RM algorithm, this paper gives a flame algorithm using adaptive iterative directions. At each iteration, the new algorithm goes towards either the noisy evaluation of the negative gradient direction or some other directions under some switch criterions. Two feasible choices of the criterions are proposed and two corresponding frame algorithms are formed. Different choices of the directions under the same given switch criterion in the frame can also form different algorithms. We also proposed the simultanous perturbation difference forms for the two frame algorithms. The almost surely convergence of the new algorithms are all established. The numerical experiments show that the new algorithms are promising.展开更多
In this paper, the simultaneous perturbation stochastic approximation (SPSA) algorithm is used for seeking optimal parameters in an adaptive filter developed for assimilating observations in the very high dimensiona...In this paper, the simultaneous perturbation stochastic approximation (SPSA) algorithm is used for seeking optimal parameters in an adaptive filter developed for assimilating observations in the very high dimensional dynamical systems. The main results show that the SPSA is capable of yielding the high filter performance similar to that produced by classical optimization algorithms, with better performance for non-linear filtering problems as more and more observations are assimilated. The advantage of the SPSA is that at each iteration it requires only two measurements of the objective function to approximate the gradient vector regardless of the dimension of the control vector (or maximally, three measurements if second-order optimization algorithms are used). The SPSA approach is thus free from the need to develop a discrete adjoint of tangent linear model as it is required up to now for solving optimization problems in very high dimensional systems. This technique offers promising perspectives on developing optimal assimilation systems encountered in the field of data assimilation in meteorology and oceanography.展开更多
Principal component analysis(PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via a...Principal component analysis(PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via an orthogonal transformation. To handle streaming data and reduce the complexities of PCA,(subspace)online PCA iterations were proposed to iteratively update the orthogonal transformation by taking one observed data point at a time. Existing works on the convergence of(subspace) online PCA iterations mostly focus on the case where the samples are almost surely uniformly bounded. In this paper, we analyze the convergence of a subspace online PCA iteration under more practical assumptions and obtain a nearly optimal finite-sample error bound. Our convergence rate almost matches the minimax information lower bound. We prove that the convergence is nearly global in the sense that the subspace online PCA iteration is convergent with high probability for random initial guesses. This work also leads to a simpler proof of the recent work on analyzing online PCA for the first principal component only.展开更多
One-bit feedback systems generate binary data as their output and the system performance is usually measured by the success rate with a fixed parameter combination. Traditional methods need many executions for paramet...One-bit feedback systems generate binary data as their output and the system performance is usually measured by the success rate with a fixed parameter combination. Traditional methods need many executions for parameter optimization. Hence, it is impractical to utilize these methods in Expensive One-Bit Feedback Systems (EOBFSs), where a single system execution is costly in terms of time or money. In this paper, we propose a novel algorithm, named Iterative Regression and Optimization (IRO), for parameter optimization and its corresponding scheme based on the Maximum Likelihood Estimation (MLE) method and Particle Swarm Optimization (PSO) method, named MLEPSO-IRO, for parameter optimization in EOBFSs. The IRO algorithm is an iterative algorithm, with each iteration comprising two parts: regression and optimization. Considering the structure of IRO and the Bernoulli distribution property of the output of EOBFSs, MLE and a modified PSO are selected to implement the regression and optimization sections, respectively, in MLEPSO-IRO. We also provide a theoretical analysis for the convergence of MLEPSO-IRO and provide numerical experiments on hypothesized EOBFSs and one real EOBFS in comparison to traditional methods. The results indicate that MLEPSO-IRO can provide a much better result with only a small amount of system executions.展开更多
This paper introduces a post-iteration averaging algorithm to achieve asymptotic optimality in convergence rates of stochastic approximation algorithms for consensus control with structural constraints. The algorithm ...This paper introduces a post-iteration averaging algorithm to achieve asymptotic optimality in convergence rates of stochastic approximation algorithms for consensus control with structural constraints. The algorithm involves two stages. The first stage is a coarse approximation obtained using a sequence of large stepsizes. Then, the second stage provides a refinement by averaging the iterates from the first stage. We show that the new algorithm is asymptotically efficient and gives the optimal convergence rates in the sense of the best scaling factor and 'smallest' possible asymptotic variance.展开更多
For control processes with one control factor and ternary response, it is important to find the effective settings of the control factor. Especially, it is often of scientific and practical interest tofind the window ...For control processes with one control factor and ternary response, it is important to find the effective settings of the control factor. Especially, it is often of scientific and practical interest tofind the window of the control factor that is necessary to cause the probability of normal response larger than a specified p. This article proposes an optimal stochastic approximation to estimate the window of interest. Simulation study shows that the proposed method gives an effcient estimation with small sample size.展开更多
Several decades ago,Profs.Sean Meyn and Lei Guo were postdoctoral fellows at ANU,where they shared interest in recursive algorithms.It seems fitting to celebrate Lei Guo’s 60 th birthday with a review of the ODE Meth...Several decades ago,Profs.Sean Meyn and Lei Guo were postdoctoral fellows at ANU,where they shared interest in recursive algorithms.It seems fitting to celebrate Lei Guo’s 60 th birthday with a review of the ODE Method and its recent evolution,with focus on the following themes:The method has been regarded as a technique for algorithm analysis.It is argued that this viewpoint is backwards:The original stochastic approximation method was surely motivated by an ODE,and tools for analysis came much later(based on establishing robustness of Euler approximations).The paper presents a brief survey of recent research in machine learning that shows the power of algorithm design in continuous time,following by careful approximation to obtain a practical recursive algorithm.While these methods are usually presented in a stochastic setting,this is not a prerequisite.In fact,recent theory shows that rates of convergence can be dramatically accelerated by applying techniques inspired by quasi Monte-Carlo.Subject to conditions,the optimal rate of convergence can be obtained by applying the averaging technique of Polyak and Ruppert.The conditions are not universal,but theory suggests alternatives to achieve acceleration.The theory is illustrated with applications to gradient-free optimization,and policy gradient algorithms for reinforcement learning.展开更多
This paper is a continuation of the research carried out in [1]-[2], where the robustnessanalysis for stochastic approximation algorithms is given for two cases: 1. The regression functionand the Liapunov function are...This paper is a continuation of the research carried out in [1]-[2], where the robustnessanalysis for stochastic approximation algorithms is given for two cases: 1. The regression functionand the Liapunov function are not zero at the sought-for x^0, 2. lim supnot zero, here {ξ_i} are the measurement errors and {a_n} are the weighting coefficients in thealgorithm. Allowing these deviations from zero to occur simultaneously but to remain small, thispaper shows that the estimation error is still small even for a class fo measurement errors moregeneral than that considered in [2].展开更多
In this paper the Kiefer-Wolfowitz (KW) procedure for searching the extremum of the regression function as well as the Robbins-Monro (RM) procedure for solving the regression equation are modified in order that they c...In this paper the Kiefer-Wolfowitz (KW) procedure for searching the extremum of the regression function as well as the Robbins-Monro (RM) procedure for solving the regression equation are modified in order that they can be applied to the case when the measurement errors form an ARMA process. Simple conditions are given to guarantee their convergence to the extremum and the root of regression function respectively by using a new approach combining both the probabilistic method and the ordinary differential equation (ODE) method. The results given here are better than the well-known ones even if the measurement error is the martingale difference sequence.展开更多
The pathwise convergence of a distributed, asynchronous stochastic approximation (SA) scheme is analyzed. The conditions imposed on the step size and noise are the weakest in comparison with the existing ones. The ste...The pathwise convergence of a distributed, asynchronous stochastic approximation (SA) scheme is analyzed. The conditions imposed on the step size and noise are the weakest in comparison with the existing ones. The step sizes in different processors are allowed to be different, and the time-delays between processors are also allowed to be different and even time-varying.展开更多
In this paper,a distributed stochastic approximation algorithm is proposed to track the dynamic root of a sum of time-varying regression functions over a network.Each agent updates its estimate by using the local obse...In this paper,a distributed stochastic approximation algorithm is proposed to track the dynamic root of a sum of time-varying regression functions over a network.Each agent updates its estimate by using the local observation,the dynamic information of the global root,and information received from its neighbors.Compared with similar works in optimization area,we allow the observation to be noise-corrupted,and the noise condition is much weaker.Furthermore,instead of the upper bound of the estimate error,we present the asymptotic convergence result of the algorithm.The consensus and convergence of the estimates are established.Finally,the algorithm is applied to a distributed target tracking problem and the numerical example is presented to demonstrate the performance of the algorithm.展开更多
Let J be the zero set of the gradient fx of a function f:Rn→R. Under fairly general conditions the stochastic approximation algorithm ensures d(f(xk),f(J))→0, as k→∞. First of all, the paper considers this proble...Let J be the zero set of the gradient fx of a function f:Rn→R. Under fairly general conditions the stochastic approximation algorithm ensures d(f(xk),f(J))→0, as k→∞. First of all, the paper considers this problem: Under what conditions the convergence d(f(xk),f(J)) → 0 implies k →∞ d(xk,J)→O. It is shown that such implication takes place if fx is continuous and f(J) is nowhere dense. Secondly, an intensified version of Sard's theorem has been proved, which itself is interesting. As a particular case, it provides two independent sufficient conditions as answers to the previous question: If f is a C1 function and either i) J is a compact set or ii) for any bounded set B, f-1(B)is bounded, then f(J) is nowhere dense. Finally, some tools in algebraic geometry are used to prove that j(J) is a finite set if f is a polynomial. Hence f(J) is nowhere dense in the polynomial case.展开更多
We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method ...We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method to update the sample density functions. We also prove the asymptotic convergence of this algorithm, and report some numerical results to illuminate its effectiveness.展开更多
In this paper, an adaptive estimation algorithm is proposed for non-linear dynamic systems with unknown static parameters based on combination of particle filtering and Simultaneous Perturbation Stochastic Approxi- ma...In this paper, an adaptive estimation algorithm is proposed for non-linear dynamic systems with unknown static parameters based on combination of particle filtering and Simultaneous Perturbation Stochastic Approxi- mation (SPSA) technique. The estimations of parameters are obtained by maximum-likelihood estimation and sampling within particle filtering framework, and the SPSA is used for stochastic optimization and to approximate the gradient of the cost function. The proposed algorithm achieves combined estimation of dynamic state and static parameters of nonlinear systems. Simulation result demonstrates the feasibilitv and efficiency of the proposed algorithm展开更多
Stochastic period-doubling bifurcation is explored in a forced Duffing system with a bounded random parameter as an additional weak harmonic perturbation added to the system. Firstly, the biharmonic driven Duffing sys...Stochastic period-doubling bifurcation is explored in a forced Duffing system with a bounded random parameter as an additional weak harmonic perturbation added to the system. Firstly, the biharmonic driven Duffing system with a random parameter is reduced to its equivalent deterministic one, and then the responses of the stochastic system can be obtained by available effective numerical methods. Finally, numerical simulations show that the phase of the additional weak harmonic perturbation has great influence on the stochastic period-doubling bifurcation in the biharmonic driven Duffing system. It is emphasized that, different from the deterministic biharmonic driven Duffing system, the intensity of random parameter in the Duffing system can also be taken as a bifurcation parameter, which can lead to the stochastic period-doubling bifurcations.展开更多
Simultaneous perturbation stochastic approximation (SPSA) belongs to the class of gradient-free optimization methods that extract gradient information from successive objective function evaluation. This paper descri...Simultaneous perturbation stochastic approximation (SPSA) belongs to the class of gradient-free optimization methods that extract gradient information from successive objective function evaluation. This paper describes an improved SPSA algorithm, which entails fuzzy adaptive gain sequences, gradient smoothing, and a step rejection procedure to enhance convergence and stability. The proposed fuzzy adaptive simultaneous perturbation approximation (FASPA) algorithm is particularly well suited to problems involving a large number of parameters such as those encountered in nonlinear system identification using neural networks (NNs). Accordingly, a multilayer perceptron (MLP) network with popular training algorithms was used to predicate the system response. We found that an MLP trained by FASPSA had the desired accuracy that was comparable to results obtained by traditional system identification algorithms. Simulation results for typical nonlinear systems demonstrate that the proposed NN architecture trained with FASPSA yields improved system identification as measured by reduced time of convergence and a smaller identification error.展开更多
A simple model of the phase-detection autofocus device based on the partially masked sensor pixels is described. The cross-correlation function of the half-images registered by the masked pixels is proposed as a focus...A simple model of the phase-detection autofocus device based on the partially masked sensor pixels is described. The cross-correlation function of the half-images registered by the masked pixels is proposed as a focus function. It is shown that—in such setting—focusing is equivalent to searching of the cross-correlation function maximum. Application of stochastic approximation algorithms to unimodal and non-unimodal focus functions is shortly discussed.展开更多
Most of existing methods in system identification with possible exception of those for linear systems are off-line in nature, and hence are nonrecursive. This paper demonstrates the recent progress in recursive system...Most of existing methods in system identification with possible exception of those for linear systems are off-line in nature, and hence are nonrecursive. This paper demonstrates the recent progress in recursive system identification. The recursive identification algorithms are presented not only for linear systems (multivariate ARMAX systems) but also for nonlinear systems such as the Hammerstein and Wiener systems, and the nonlinear ARX systems. The estimates generated by the algorithms are online updated and converge a.s. to the true values as time tends to infinity.展开更多
Power control problems for wireless communication networks are investigated in direct-sequence codedivision multiple-access (DS/CDMA) channels. It is shown that the underlying problem can be formulated as a constrai...Power control problems for wireless communication networks are investigated in direct-sequence codedivision multiple-access (DS/CDMA) channels. It is shown that the underlying problem can be formulated as a constrained optimization problem in a stochastic framework. For effective solutions to this optimization problem in real time, recursive algorithms of stochastic approximation type are developed that can solve the problem with unknown system components. Under broad conditions, convergence of the algorithms is established by using weak convergence methods.展开更多
The present aim is to update, upon arrival of new learning data, the parameters of a score constructed with an ensemble method involving linear discriminant analysis and logistic regression in an online setting, witho...The present aim is to update, upon arrival of new learning data, the parameters of a score constructed with an ensemble method involving linear discriminant analysis and logistic regression in an online setting, without the need to store all of the previously obtained data. Poisson bootstrap and stochastic approximation processes were used with online standardized data to avoid numerical explosions, the convergence of which has been established theoretically. This empirical convergence of online ensemble scores to a reference “batch” score was studied on five different datasets from which data streams were simulated, comparing six different processes to construct the online scores. For each score, 50 replications using a total of 10N observations (N being the size of the dataset) were performed to assess the convergence and the stability of the method, computing the mean and standard deviation of a convergence criterion. A complementary study using 100N observations was also performed. All tested processes on all datasets converged after N iterations, except for one process on one dataset. The best processes were averaged processes using online standardized data and a piecewise constant step-size.展开更多
基金supported by the Chinese NSF grants 10571171 and 40233029.
文摘Stochastic approximation problem is to find some root or extremum of a nonlinear function for which only noisy measurements of the function are available. The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm, which uses the noisy evaluation of the negative gradient direction as the iterative direction. In order to accelerate the RM algorithm, this paper gives a flame algorithm using adaptive iterative directions. At each iteration, the new algorithm goes towards either the noisy evaluation of the negative gradient direction or some other directions under some switch criterions. Two feasible choices of the criterions are proposed and two corresponding frame algorithms are formed. Different choices of the directions under the same given switch criterion in the frame can also form different algorithms. We also proposed the simultanous perturbation difference forms for the two frame algorithms. The almost surely convergence of the new algorithms are all established. The numerical experiments show that the new algorithms are promising.
文摘In this paper, the simultaneous perturbation stochastic approximation (SPSA) algorithm is used for seeking optimal parameters in an adaptive filter developed for assimilating observations in the very high dimensional dynamical systems. The main results show that the SPSA is capable of yielding the high filter performance similar to that produced by classical optimization algorithms, with better performance for non-linear filtering problems as more and more observations are assimilated. The advantage of the SPSA is that at each iteration it requires only two measurements of the objective function to approximate the gradient vector regardless of the dimension of the control vector (or maximally, three measurements if second-order optimization algorithms are used). The SPSA approach is thus free from the need to develop a discrete adjoint of tangent linear model as it is required up to now for solving optimization problems in very high dimensional systems. This technique offers promising perspectives on developing optimal assimilation systems encountered in the field of data assimilation in meteorology and oceanography.
基金supported by National Natural Science Foundation of China(Grant No.11901340)National Science Foundation of USA(Grant Nos.DMS-1719620 and DMS-2009689)the ST Yau Centre at the Yang Ming Chiao Tung University.
文摘Principal component analysis(PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via an orthogonal transformation. To handle streaming data and reduce the complexities of PCA,(subspace)online PCA iterations were proposed to iteratively update the orthogonal transformation by taking one observed data point at a time. Existing works on the convergence of(subspace) online PCA iterations mostly focus on the case where the samples are almost surely uniformly bounded. In this paper, we analyze the convergence of a subspace online PCA iteration under more practical assumptions and obtain a nearly optimal finite-sample error bound. Our convergence rate almost matches the minimax information lower bound. We prove that the convergence is nearly global in the sense that the subspace online PCA iteration is convergent with high probability for random initial guesses. This work also leads to a simpler proof of the recent work on analyzing online PCA for the first principal component only.
文摘One-bit feedback systems generate binary data as their output and the system performance is usually measured by the success rate with a fixed parameter combination. Traditional methods need many executions for parameter optimization. Hence, it is impractical to utilize these methods in Expensive One-Bit Feedback Systems (EOBFSs), where a single system execution is costly in terms of time or money. In this paper, we propose a novel algorithm, named Iterative Regression and Optimization (IRO), for parameter optimization and its corresponding scheme based on the Maximum Likelihood Estimation (MLE) method and Particle Swarm Optimization (PSO) method, named MLEPSO-IRO, for parameter optimization in EOBFSs. The IRO algorithm is an iterative algorithm, with each iteration comprising two parts: regression and optimization. Considering the structure of IRO and the Bernoulli distribution property of the output of EOBFSs, MLE and a modified PSO are selected to implement the regression and optimization sections, respectively, in MLEPSO-IRO. We also provide a theoretical analysis for the convergence of MLEPSO-IRO and provide numerical experiments on hypothesized EOBFSs and one real EOBFS in comparison to traditional methods. The results indicate that MLEPSO-IRO can provide a much better result with only a small amount of system executions.
基金supported by the U.S. Army Research Office (No. W911NF-12-1-0223)
文摘This paper introduces a post-iteration averaging algorithm to achieve asymptotic optimality in convergence rates of stochastic approximation algorithms for consensus control with structural constraints. The algorithm involves two stages. The first stage is a coarse approximation obtained using a sequence of large stepsizes. Then, the second stage provides a refinement by averaging the iterates from the first stage. We show that the new algorithm is asymptotically efficient and gives the optimal convergence rates in the sense of the best scaling factor and 'smallest' possible asymptotic variance.
基金supported by the National Natural Science Foundation of China under Grant No.11371054
文摘For control processes with one control factor and ternary response, it is important to find the effective settings of the control factor. Especially, it is often of scientific and practical interest tofind the window of the control factor that is necessary to cause the probability of normal response larger than a specified p. This article proposes an optimal stochastic approximation to estimate the window of interest. Simulation study shows that the proposed method gives an effcient estimation with small sample size.
基金ARO W911NF1810334NSF under EPCN 1935389the National Renewable Energy Laboratory(NREL)。
文摘Several decades ago,Profs.Sean Meyn and Lei Guo were postdoctoral fellows at ANU,where they shared interest in recursive algorithms.It seems fitting to celebrate Lei Guo’s 60 th birthday with a review of the ODE Method and its recent evolution,with focus on the following themes:The method has been regarded as a technique for algorithm analysis.It is argued that this viewpoint is backwards:The original stochastic approximation method was surely motivated by an ODE,and tools for analysis came much later(based on establishing robustness of Euler approximations).The paper presents a brief survey of recent research in machine learning that shows the power of algorithm design in continuous time,following by careful approximation to obtain a practical recursive algorithm.While these methods are usually presented in a stochastic setting,this is not a prerequisite.In fact,recent theory shows that rates of convergence can be dramatically accelerated by applying techniques inspired by quasi Monte-Carlo.Subject to conditions,the optimal rate of convergence can be obtained by applying the averaging technique of Polyak and Ruppert.The conditions are not universal,but theory suggests alternatives to achieve acceleration.The theory is illustrated with applications to gradient-free optimization,and policy gradient algorithms for reinforcement learning.
基金This project is supported by the National Natural Science Foundation of China
文摘This paper is a continuation of the research carried out in [1]-[2], where the robustnessanalysis for stochastic approximation algorithms is given for two cases: 1. The regression functionand the Liapunov function are not zero at the sought-for x^0, 2. lim supnot zero, here {ξ_i} are the measurement errors and {a_n} are the weighting coefficients in thealgorithm. Allowing these deviations from zero to occur simultaneously but to remain small, thispaper shows that the estimation error is still small even for a class fo measurement errors moregeneral than that considered in [2].
文摘In this paper the Kiefer-Wolfowitz (KW) procedure for searching the extremum of the regression function as well as the Robbins-Monro (RM) procedure for solving the regression equation are modified in order that they can be applied to the case when the measurement errors form an ARMA process. Simple conditions are given to guarantee their convergence to the extremum and the root of regression function respectively by using a new approach combining both the probabilistic method and the ordinary differential equation (ODE) method. The results given here are better than the well-known ones even if the measurement error is the martingale difference sequence.
基金This work was supported by the National Natural Science Foundation of China (Grant Nos. 2666100 and 69804010) the National Key Project of China.
文摘The pathwise convergence of a distributed, asynchronous stochastic approximation (SA) scheme is analyzed. The conditions imposed on the step size and noise are the weakest in comparison with the existing ones. The step sizes in different processors are allowed to be different, and the time-delays between processors are also allowed to be different and even time-varying.
基金This work was supported by the National Key Research and Development Program of China under Grant 2018YFA0703800the National Natural Science Foundation of China under Grant 61822312This work was also supported(in part)by the Strategic Priority Research Program of Chinese Academy of Sciences under Grant No.XDA27000000.
文摘In this paper,a distributed stochastic approximation algorithm is proposed to track the dynamic root of a sum of time-varying regression functions over a network.Each agent updates its estimate by using the local observation,the dynamic information of the global root,and information received from its neighbors.Compared with similar works in optimization area,we allow the observation to be noise-corrupted,and the noise condition is much weaker.Furthermore,instead of the upper bound of the estimate error,we present the asymptotic convergence result of the algorithm.The consensus and convergence of the estimates are established.Finally,the algorithm is applied to a distributed target tracking problem and the numerical example is presented to demonstrate the performance of the algorithm.
基金Supported by the National Natural Science Foundation of China (G69774008, G59837270, G1998020308)and National Key Project.
文摘Let J be the zero set of the gradient fx of a function f:Rn→R. Under fairly general conditions the stochastic approximation algorithm ensures d(f(xk),f(J))→0, as k→∞. First of all, the paper considers this problem: Under what conditions the convergence d(f(xk),f(J)) → 0 implies k →∞ d(xk,J)→O. It is shown that such implication takes place if fx is continuous and f(J) is nowhere dense. Secondly, an intensified version of Sard's theorem has been proved, which itself is interesting. As a particular case, it provides two independent sufficient conditions as answers to the previous question: If f is a C1 function and either i) J is a compact set or ii) for any bounded set B, f-1(B)is bounded, then f(J) is nowhere dense. Finally, some tools in algebraic geometry are used to prove that j(J) is a finite set if f is a polynomial. Hence f(J) is nowhere dense in the polynomial case.
基金Project supported by the National Natural Science Foundation of China (No.10671117)Shanghai Leading Academic Discipline Project (No.J050101)the Youth Science Foundation of Hunan Education Department of China (No.06B037)
文摘We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method to update the sample density functions. We also prove the asymptotic convergence of this algorithm, and report some numerical results to illuminate its effectiveness.
基金the National Natural Science Foundation of China (No. 60404011)
文摘In this paper, an adaptive estimation algorithm is proposed for non-linear dynamic systems with unknown static parameters based on combination of particle filtering and Simultaneous Perturbation Stochastic Approxi- mation (SPSA) technique. The estimations of parameters are obtained by maximum-likelihood estimation and sampling within particle filtering framework, and the SPSA is used for stochastic optimization and to approximate the gradient of the cost function. The proposed algorithm achieves combined estimation of dynamic state and static parameters of nonlinear systems. Simulation result demonstrates the feasibilitv and efficiency of the proposed algorithm
基金Project supported by the National Natural Science Foundation of China(Grant Nos10472091and10332030)
文摘Stochastic period-doubling bifurcation is explored in a forced Duffing system with a bounded random parameter as an additional weak harmonic perturbation added to the system. Firstly, the biharmonic driven Duffing system with a random parameter is reduced to its equivalent deterministic one, and then the responses of the stochastic system can be obtained by available effective numerical methods. Finally, numerical simulations show that the phase of the additional weak harmonic perturbation has great influence on the stochastic period-doubling bifurcation in the biharmonic driven Duffing system. It is emphasized that, different from the deterministic biharmonic driven Duffing system, the intensity of random parameter in the Duffing system can also be taken as a bifurcation parameter, which can lead to the stochastic period-doubling bifurcations.
文摘Simultaneous perturbation stochastic approximation (SPSA) belongs to the class of gradient-free optimization methods that extract gradient information from successive objective function evaluation. This paper describes an improved SPSA algorithm, which entails fuzzy adaptive gain sequences, gradient smoothing, and a step rejection procedure to enhance convergence and stability. The proposed fuzzy adaptive simultaneous perturbation approximation (FASPA) algorithm is particularly well suited to problems involving a large number of parameters such as those encountered in nonlinear system identification using neural networks (NNs). Accordingly, a multilayer perceptron (MLP) network with popular training algorithms was used to predicate the system response. We found that an MLP trained by FASPSA had the desired accuracy that was comparable to results obtained by traditional system identification algorithms. Simulation results for typical nonlinear systems demonstrate that the proposed NN architecture trained with FASPSA yields improved system identification as measured by reduced time of convergence and a smaller identification error.
基金supported by the NCN grant UMO-2011/01/B/ST7/00666.
文摘A simple model of the phase-detection autofocus device based on the partially masked sensor pixels is described. The cross-correlation function of the half-images registered by the masked pixels is proposed as a focus function. It is shown that—in such setting—focusing is equivalent to searching of the cross-correlation function maximum. Application of stochastic approximation algorithms to unimodal and non-unimodal focus functions is shortly discussed.
基金supported by NSFC (60221301 and 60874001)a grant from the National Laboratory of Space Intelligent Control
文摘Most of existing methods in system identification with possible exception of those for linear systems are off-line in nature, and hence are nonrecursive. This paper demonstrates the recent progress in recursive system identification. The recursive identification algorithms are presented not only for linear systems (multivariate ARMAX systems) but also for nonlinear systems such as the Hammerstein and Wiener systems, and the nonlinear ARX systems. The estimates generated by the algorithms are online updated and converge a.s. to the true values as time tends to infinity.
基金Research of G.Yin was supported by the National Science Foundation (CMS-0510655,DMS-0624849)the National Security Agency (MSPF-068-029)+3 种基金the National Natural Science Foundation of China (No.60574069)research of C.-A. Tan was supported by the National Science Foundation (CMS-0510655)research of L.Y.Wang was supported by the National Science Foundation (ECS-0329597, DMS-0624849)research of C.Z.Xu was supported by the National Science Foundation (CCF-0611750,DMS-0624849,CNS-0702488,CRI-0708232).
文摘Power control problems for wireless communication networks are investigated in direct-sequence codedivision multiple-access (DS/CDMA) channels. It is shown that the underlying problem can be formulated as a constrained optimization problem in a stochastic framework. For effective solutions to this optimization problem in real time, recursive algorithms of stochastic approximation type are developed that can solve the problem with unknown system components. Under broad conditions, convergence of the algorithms is established by using weak convergence methods.
文摘The present aim is to update, upon arrival of new learning data, the parameters of a score constructed with an ensemble method involving linear discriminant analysis and logistic regression in an online setting, without the need to store all of the previously obtained data. Poisson bootstrap and stochastic approximation processes were used with online standardized data to avoid numerical explosions, the convergence of which has been established theoretically. This empirical convergence of online ensemble scores to a reference “batch” score was studied on five different datasets from which data streams were simulated, comparing six different processes to construct the online scores. For each score, 50 replications using a total of 10N observations (N being the size of the dataset) were performed to assess the convergence and the stability of the method, computing the mean and standard deviation of a convergence criterion. A complementary study using 100N observations was also performed. All tested processes on all datasets converged after N iterations, except for one process on one dataset. The best processes were averaged processes using online standardized data and a piecewise constant step-size.