No description available.

Performance and stability of many iterative algorithms such as stochastic gradient descent largely depend on a fixed and scalar step-size parameter. Use of a fixed and scalar step-size value may lead to limited performance in many problems. We study several existing step-size adaptation algorithms in nonstationary, supervised learning problems using simulated and real-world data. We discover that effectiveness of the existing step-size adaptation algorithms requires tuning of a meta parameter across problems. We introduce a new algorithm - Autostep - by combining several new techniques with an existing algorithm, and demonstrate that it can effectively adapt a vector step-size parameter on all of our training and test problems without tuning its meta parameter across them. Autostep is the first step-size adaptation algorithm that can be used in widely different problems with the same setting of all of its parameters.

Finite-difference methods for computing the derivative of a function with respect to an independent variable require knowledge of the perturbation step size for that variable. Although rules of thumb exist for determining the magnitude of the step size, their effectiveness diminishes for complicated functions or when numerically solving difficult optimization problems. This dissertation investigates the problem of determining the step size that minimizes the total error associated with finite-difference derivative approximations. The total error is defined as the sum of errors from numerical sources (roundoff error) and mathematical approximations (truncation error). Several finite-difference approximations are considered, and expressions are derived for the errors associated with each approximation. Analysis of these errors leads to an algorithm that determines the optimal perturbation step size that minimizes the total error. A benefit of this algorithm is that the computed optimal step size, when used with neighboring values of the independent variable, results in approximately the same magnitude of error in the derivative. This allows the same step size to be used for several successive iterations of the independent variable in an optimization loop. A range of independent variable values for which the optimal step size can safely remain constant is also computed. In addition to roundoff and truncation errors within the finite-difference method, numerical errors within the actual function implementation are also considered. It is shown that the optimal step size can be used to compute an upper bound for these condition errors, without any prior knowledge of the function implementation. Knowledge of a function's condition error is of great assistance during the debugging stages of simulation design. Although the fundamental analysis assumes a scalar function of a scalar independent variable, it is later extended to the general case of a vector function of a vector independent variable. Several numerical examples are shown, ranging from simple polynomial and trigonometric functions to complex trajectory optimization problems. In each example, the step size is computed using the algorithm developed herein, a rule-of-thumb method, and an alternative statistical algorithm, and the resulting finite-difference derivatives are compared to the true derivative where available. / text

This work presents a method for screening synchrophasor data to search for power system events of interest. The method employs prony algorithm to perform modal analysis and estimate mode amplitude, frequency, and damping ratio on the data obtained from the Texas Synchrophasor Network. The procedure uses seven different Linear Prediction Model (LPM) orders, plus a 10 second window width that slides in steps of 1 second, to minimize the possibility of overlooking events of interest. Further, the algorithm is extended to include user defined modal characteristics thresholds, window length and step size to capture specific power system events. / text

This dissertation focuses on the development of adaptive time-stepping and high-order parallel stages exponential Runge–Kutta methods for discretizing stiff partial differential equations (PDEs). The design of exponential Runge–Kutta methods relies heavily on the existing stiff order conditions available in the literature, primarily up to order 5. It is well-known that constructing higher-order efficient methods that strictly satisfy all the stiff order conditions is challenging. Typically, methods up to order 5 have been derived by relaxing one or more order conditions, depending on the desired accuracy level. Our approach will be based on a comprehensive investigation of these conditions. We will derive novel and efficient exponential Runge–Kutta schemes of orders up to 5, which not only fulfill the stiff order conditions in a strict sense but also support the implementation of variable step sizes. Furthermore, we develop the first-ever sixth-order exponential Runge–Kutta schemes by leveraging the exponential B-series theory. Notably, all the newly derived schemes allow the efficient computation of multiple stages, either simultaneously or in parallel. To establish the convergence properties of the proposed methods, we perform an analysis within an abstract Banach space in the context of semigroup theory. Our numerical experiments are given on parabolic PDEs to confirm the accuracy and efficiency of the newly constructed methods.

No description available.

On s'intéresse à l'étude d'algorithmes stochastiques pour l'optimisation numérique boîte-noire. Dans la première partie de cette thèse, on présente une méthodologie pour évaluer efficacement des stratégies d'adaptation du step-size dans le cas de l'optimisation boîte-noire sans contraintes. Le step-size est un paramètre important dans les algorithmes évolutionnaires tels que les stratégies d'évolution; il contrôle la diversité de la population et, de ce fait, joue un rôle déterminant dans la convergence de l'algorithme. On présente aussi les résultats empiriques de la comparaison de trois méthodes d'adaptation du step-size. Ces algorithmes sont testés sur le testbed BBOB (black-box optimization benchmarking) de la plateforme COCO (comparing continuous optimisers). Dans la deuxième partie de cette thèse, sont présentées nos contributions dans le domaine de l'optimisation boîte-noire avec contraintes. On analyse la convergence linéaire d'algorithmes stochastiques adaptatifs pour l'optimisation sous contraintes dans le cas de contraintes linéaires, gérées avec une approche Lagrangien augmenté adaptative. Pour ce faire, on étend l'analyse par chaines de Markov faite dans le cas d'optimisation sans contraintes au cas avec contraintes: pour chaque algorithme étudié, on exhibe une classe de fonctions pour laquelle il existe une chaine de Markov homogène telle que la stabilité de cette dernière implique la convergence linéaire de l'algorithme. La convergence linéaire est déduite en appliquant une loi des grands nombres pour les chaines de Markov, sous l'hypothèse de la stabilité. Dans notre cas, la stabilité est validée empiriquement. / We investigate various aspects of adaptive randomized (or stochastic) algorithms for both constrained and unconstrained black-box continuous optimization. The first part of this thesis focuses on step-size adaptation in unconstrained optimization. We first present a methodology for assessing efficiently a step-size adaptation mechanism that consists in testing a given algorithm on a minimal set of functions, each reflecting a particular difficulty that an efficient step-size adaptation algorithm should overcome. We then benchmark two step-size adaptation mechanisms on the well-known BBOB noiseless testbed and compare their performance to the one of the state-of-the-art evolution strategy (ES), CMA-ES, with cumulative step-size adaptation. In the second part of this thesis, we investigate linear convergence of a (1 + 1)-ES and a general step-size adaptive randomized algorithm on a linearly constrained optimization problem, where an adaptive augmented Lagrangian approach is used to handle the constraints. To that end, we extend the Markov chain approach used to analyze randomized algorithms for unconstrained optimization to the constrained case. We prove that when the augmented Lagrangian associated to the problem, centered at the optimum and the corresponding Lagrange multipliers, is positive homogeneous of degree 2, then for algorithms enjoying some invariance properties, there exists an underlying homogeneous Markov chain whose stability (typically positivity and Harris-recurrence) leads to linear convergence to both the optimum and the corresponding Lagrange multipliers. We deduce linear convergence under the aforementioned stability assumptions by applying a law of large numbers for Markov chains. We also present a general framework to design an augmented-Lagrangian-based adaptive randomized algorithm for constrained optimization, from an adaptive randomized algorithm for unconstrained optimization.

Simuler temporellement les réseaux électriques modernes requiert d'importants moyens de calcul de par la dimension et la raideur des systèmes différentiels algébriques résultants. De plus, la fréquence d'oscillation de certains signaux simulés contraint fortement le pas d'intégration des schémas classiques, y compris en régime établi où ils sont proches de sinusoïdes oscillant à la fréquence nominale du système. L'objectif de la méthode des prédicteurs sinusoïdaux proposée dans cette thèse est donc de tirer parti de cette propriété afin d'améliorer les performances du solveur tout en contrôlant l'erreur de calcul. Elle consiste à décomposer la solution en deux parties : une sinusoïde, dont les coefficients de Fourier sont fixés pour chaque intervalle d'intégration puis mis à jour par estimation paramétrique, et un terme de correction sur lequel le système d'EDA est reformulé et résolu à l'aide d'un schéma d'intégration à pas adaptatif. Une attention particulière a été portée au choix de l'estimateur paramétrique, ce dernier ayant un impact direct sur le pas d'intégration de par sa précision et indirect de par son effet sur la stabilité globale de la méthode. L'estimateur finalement développé consiste à calculer les coefficients de Fourier qui minimisent une mesure de la stationnarité du système. Ce dernier étant convergent en régime permanent, le terme de correction est progressivement amorti, permettant ainsi d'accroître considérablement le pas d'intégration. Cette méthode, intégrée au sein du solveur SUNDIALS IDA puis interfacée avec un moteur de calcul industriel, permet d'accélérer très nettement les simulations en comparaison avec une implémentation classique / Modern power systems time-domain simulations require important computational resources due to the resulting differential algebraic systems dimension and stiffness. In addition, some simulated signals oscillation frequency dramatically limits the classical schemes step size, even in steady-state during which they are close to sinusoids oscillating at system nominal frequency. That's why the sinusoidal predictors method proposed in this thesis aims at taking this property into account in order to enhance solver performances while controlling the integration error. It consists in decomposing the solution into two parts: a sinusoid, whose Fourier coefficients are fixed for each time integration interval and then updated by parametric estimation, and a correction term on which the DAE system is rewritten and solved using an adaptive step size integration scheme. A particular focus has been given on the estimator choice, given its precision direct impact on the step size and its indirect effect on the global method stability. The finally developed estimator consists in computing Fourier coefficients minimizing a system stationarity measurement. As it converges in steady-state, the correction term is progressively damped, which enables to considerably increase the step size. This method, integrated into the reference solver SUNDIALS IDA and interfaced with an industrial simulation engine, enables to very significantly accelerate simulations in comparison with a classical implementation

Ionospheric scintillation is a phenomenon caused by varying concentrations of charged particles in the upper atmosphere that induces deep fades and rapid phase rotations in satellite signals, including GPS. During periods of scintillation, carrier tracking loops often lose lock on the signal because the rapid phase rotations generate cycle slips in the PLL. One solution to mitigating this problem is by employing decision-directed carrier recovery algorithms that achieve data wipe-off using differential bit detection techniques. Other techniques involve PLLs with variable bandwidth and variable integration times. Since nearly 60% of the GPS signal repeats between frames, this thesis explores PLLs utilizing variable integration times and decision-directed algorithms that exploit the repeating data as a training sequence to aid in phase error estimation. Experiments conducted using a GPS signal generator, software radio, and MATLAB scintillation testbed compare the bit error rate of each of the receiver models. Training-based methods utilizing variable integration times show significant reductions in the likelihood of total loss of lock.

The objective of this research is to presents new acoustic echo cancellation design methods that can effectively work in the nonlinear environment. Acoustic echo is an annoying issue for voice communication systems. Because of room acoustics and delay in the transmission path, echoes affect the sound quality and may hamper communications. Acoustic echo cancellers (AECs) are employed to remove the acoustic echo while keeping full-duplex communications. AEC designs face a variety of challenges, including long room impulse response, acoustic path nonlinearity, ambient noise, and double-talk situation. We investigate two parts of echo canceller design: echo cancellation algorithm design and control logic algorithm design. In the first part, our work focuses on the nonlinear adaptive and fast-convergence algorithms. We investigate three different structures: predistortion linearization, cascade structure, and nonlinear residual echo suppressor. Specifically, we are interested in the coherence function, since it provides a means for quantifying linear association between two stationary random processes. By using the coherence as a criterion to design the nonlinear echo canceller in the system, our method guarantees the algorithm stability and leads to a faster convergence rate. In the second part, our work focuses on the robustness of AECs in the presence of interference. With regard to the near-end speech, we investigate the double-talk detector (DTD) design in conjunction with nonlinear AECs. Specifically, we propose to design a DTD based on the mutual information (MI). We show that the advantage of the MI-based method, when compared with the existing methods, is that it is applicable to both the linear and nonlinear scenarios. With respect to the background noise, we propose a variable step-size and variable tap-length least mean square (LMS) algorithm. Based on the fact that the room impulse response usually exhibits an exponential decay power profile in acoustic echo cancellation applications, the proposed method finds optimal step size and tap length at each iteration. Thus, it achieves faster convergence rate and better steady-state performance. We show a number of experimental results to illustrate the performance of the proposed algorithms.