Newton-based stochastic optimization using q-Gaussian smoothed functional algorithms

We present the first q-Gaussian smoothed functional (SF) estimator of the Hessian and the first Newton-based stochastic optimization algorithm that estimates both the Hessian and the gradient of the objective function using q-Gaussian perturbations. Our algorithm requires only two system simulations (regardless of the parameter dimension) and estimates both the gradient and the Hessian at each update epoch using these. We also present a proof of convergence of the proposed algorithm. In a related recent work (Ghoshdastidar, Dukkipati, & Bhatnagar, 2014), we presented gradient SF algorithms based on the q-Gaussian perturbations. Our work extends prior work on SF algorithms by generalizing the class of perturbation distributions as most distributions reported in the literature for which SF algorithms are known to work turn out to be special cases of the q-Gaussian distribution. Besides studying the convergence properties of our algorithm analytically, we also show the results of numerical simulations on a model of a queuing network, that illustrate the significance of the proposed method. In particular, we observe that our algorithm performs better in most cases, over a wide range of q-values, in comparison to Newton SF algorithms with the Gaussian and Cauchy perturbations, as well as the gradient q-Gaussian SF algorithms. (C) 2014 Elsevier Ltd. All rights reserved.

Simultaneous Perturbation Newton Algorithms for Simulation Optimization

We present a new Hessian estimator based on the simultaneous perturbation procedure, that requires three system simulations regardless of the parameter dimension. We then present two Newton-based simulation optimization algorithms that incorporate this Hessian estimator. The two algorithms differ primarily in the manner in which the Hessian estimate is used. Both our algorithms do not compute the inverse Hessian explicitly, thereby saving on computational effort. While our first algorithm directly obtains the product of the inverse Hessian with the gradient of the objective, our second algorithm makes use of the Sherman-Morrison matrix inversion lemma to recursively estimate the inverse Hessian. We provide proofs of convergence for both our algorithms. Next, we consider an interesting application of our algorithms on a problem of road traffic control. Our algorithms are seen to exhibit better performance than two Newton algorithms from a recent prior work.

Ancient Chinese algorithm: The Ying Buzu Shu (method of surplus and deficiency) vs Newton iteration method

Air exploratory discussion of an ancient Chinese algorithm, the Ying Buzu Shu, in about 2nd century BC, known as the rule of double false position in the West is given. In addition to pointing out that the rule of double false position is actually a translation version of the ancient Chinese algorithm, a comparison with well-known Newton iteration method is also made. If derivative is introduced, the ancient Chinese algorithm reduces to the Newton method. A modification of the ancient Chinese algorithm is also proposed, and some of applications to nonlinear oscillators are illustrated.

Avaliação dos algoritmos de Picard-Krylov e Newton-Krylov na solução da equação de Richards

A engenharia geotécnica é uma das grandes áreas da engenharia civil que estuda a interação entre as construções realizadas pelo homem ou de fenômenos naturais com o ambiente geológico, que na grande maioria das vezes trata-se de solos parcialmente saturados. Neste sentido, o desempenho de obras como estabilização, contenção de barragens, muros de contenção, fundações e estradas estão condicionados a uma correta predição do fluxo de água no interior dos solos. Porém, como a área das regiões a serem estudas com relação à predição do fluxo de água são comumente da ordem de quilômetros quadrados, as soluções dos modelos matemáticos exigem malhas computacionais de grandes proporções, ocasionando sérias limitações associadas aos requisitos de memória computacional e tempo de processamento. A fim de contornar estas limitações, métodos numéricos eficientes devem ser empregados na solução do problema em análise. Portanto, métodos iterativos para solução de sistemas não lineares e lineares esparsos de grande porte devem ser utilizados neste tipo de aplicação. Em suma, visto a relevância do tema, esta pesquisa aproximou uma solução para a equação diferencial parcial de Richards pelo método dos volumes finitos em duas dimensões, empregando o método de Picard e Newton com maior eficiência computacional. Para tanto, foram utilizadas técnicas iterativas de resolução de sistemas lineares baseados no espaço de Krylov com matrizes pré-condicionadoras com a biblioteca numérica Portable, Extensible Toolkit for Scientific Computation (PETSc). Os resultados indicam que quando se resolve a equação de Richards considerando-se o método de PICARD-KRYLOV, não importando o modelo de avaliação do solo, a melhor combinação para resolução dos sistemas lineares é o método dos gradientes biconjugados estabilizado mais o pré-condicionador SOR. Por outro lado, quando se utiliza as equações de van Genuchten deve ser optar pela combinação do método dos gradientes conjugados em conjunto com pré-condicionador SOR. Quando se adota o método de NEWTON-KRYLOV, o método gradientes biconjugados estabilizado é o mais eficiente na resolução do sistema linear do passo de Newton, com relação ao pré-condicionador deve-se dar preferência ao bloco Jacobi. Por fim, há evidências que apontam que o método PICARD-KRYLOV pode ser mais vantajoso que o método de NEWTON-KRYLOV, quando empregados na resolução da equação diferencial parcial de Richards.

A Newton algorithm for invariant subspace computation with large basins of attraction

We study the global behaviour of a Newton algorithm on the Grassmann manifold for invariant subspace computation. It is shown that the basins of attraction of the invariant subspaces may collapse in case of small eigenvalue gaps. A Levenberg-Marquardt-like modification of the algorithm with low numerical cost is proposed. A simple strategy for choosing the parameter is shown to dramatically enlarge the basins of attraction of the invariant subspaces while preserving the fast local convergence.

Four-dimensional Newton's constant in brane world with a sloping extra dimension

We show the four-dimensional Newton's constant obtained naturally from five-dimensional brane world with a tinily sloping extra dimension, which is independent of the bulk Weyl tensor. The corresponding universe is stiff fluid dominated when the slope of extra dimension is very small. Otherwise, the universe may be undergoing a self-acceleration at present epoch and have a decelerated phase in very recent past.

Newton's aerodynamic problem in media of chaotically moving particles

Plakhov, A.Y.; Torres, D., (2005) 'Newton's aerodynamic problem in media of chaotically moving particles', Sbornik: Mathematics 196(6) pp.885-933 RAE2008

An application of quasi-Newton methods for the numerical solution of interface problems

Quasi-Newton methods are applied to solve interface problems which arise from domain decomposition methods. These interface problems are usually sparse systems of linear or nonlinear equations. We are interested in applying these methods to systems of linear equations where we are not able or willing to calculate the Jacobian matrices as well as to systems of nonlinear equations resulting from nonlinear elliptic problems in the context of domain decomposition. Suitability for parallel implementation of these algorithms on coarse-grained parallel computers is discussed.