Author(s):
Cruz, João Pedro Antunes Ferreira da 
Date: 2005
Persistent ID: http://hdl.handle.net/10773/4594
Origin: RIA - Repositório Institucional da Universidade de Aveiro
Subject(s): Matemática; Processos estocásticos; Teoria de aproximação; Algoritmos; Optimização combinatória; Controlo adaptativo - Modelos matemáticos
Description
Consideram-se os algoritmos iterativos de aproximação estocástica (AE) do
zero de uma função dada quando o valor da função é perturbado
aleatoriamente. A teoria da AE está bem desenvolvida para o caso em que o
valor do passo do algoritmo é determinístico, dependendo apenas do número
da iteração do algoritmo; em particular, foram elaborados algoritmos
assimptoticamente optimais.
No entanto, em muitos problemas práticos abordados de forma heurística
(em particular redes neuronais), verifica-se que são mais efectivos, num
periodo transitório, os algoritmos cujo valor do passo é aleatório, sendo
determinado através dos parâmetros correntes do algoritmo.
A tese concentra-se nos algoritmos onde o valor do passo aumenta caso os
incrementos de aproximações consecutivas mantenham o sentido (indicando
que o algoritmo está na "zona determinística"), e diminui no caso contrário
(estando o algoritmo na "zona estocástica").
No algoritmo de Kesten, o passo mantém-se caso hajam dois incrementos
com o mesmo sinal, e em caso oposto, o passo é decrementado. Na tese, o
algoritmo é generalizado podendo o passo aumentar caso duas iterações
ocorram no mesmo sentido. É demonstrada a convergência para o zero com
probabilidade 1 para o caso de funções unidimensionais e multidimensionais
com um único zero. É também demonstrada a normalidade assimptótica das
estimativas.
Podem encontrar-se na literatura, algoritmos heurísticos de variação
multiplicativa do passo para redes neuronais. Na tese, e para o caso de
funções unidimensionais com vários zeros, é demonstrado com probabilidade
1 que estes algoritmos podem divergir ou convergir para uma vizinhança de
um dos zeros. A adaptação do passo depende de dois parâmetros que
determinam a precisão da vizinhança. Além desta regulação foi observado em
simulações que para uma maior precisão é necessário um aumento do número
de iterações.
São apresentados inúmeros exemplos numéricos que ilustram a vantagem
dos novos algoritmos para o caso unidimensional. Para o caso
multidimensional os algoritmos propostos não se mostraram efectivos. We consider iterative algorithms of Stochastic Approximation (SA) of the
zero of a function when the value of the function is randomly perturbated. SA
theory is well established when the step-value is deterministic, depending only
on the iteration number. In particular, asymptotical optimal algorithms were
developed.
However, in many practical problems, the use of random step-value
becomes more efective in a transitory stage, being determined by current
iterations measures. This thesis concentrate on algorithms where step can
increase if consecutive increments have the same sign (called `deterministic
zone') and decrease otherwise (called `stochastic zone'). Algorithms of this
kind were treated heuristically in several publications (particularly in neural
networks literature).
In Kesten's algorithm, step is kept if two consecutive iterations have the
same direction, and decreases otherwise. The thesis makes a generalization
allowing the step to increase if successive increments have same sign and
decrease otherwise. Almost sure convergence is demonstrated for the case of
unidimensional and multidimensional functions with one zero. The asymptotic
normality of estimations is also proved.
Algorithms with multiplicative step variation were tested for neural networks.
In this thesis, and for the case of unidimensional functions of many zeros, is
demonstrated that divergence or convergence to a neighborhood of some zero
can occur depending on algorithm parameters. In case of convergence more
precision of the neighborhood can be reached at the expense of more
iterations.
Many numerical examples are presented showing the advantage of the new
algorithms for the unidimensional case. For the multidimensional case of these
algorithms no benefit was observed. Doutoramento em Matemática
