Métodos convergentes de otimização global baseados no vetor q-gradiente

• Ano de defesa: 2016
• Autor(a) principal: Érica Josiane Coelho Gouvêa
• Orientador(a): Fernando Manuel Ramos, Aline Cristina Soterroni
• Banca de defesa: Stephan Stephany, Erwin Doescher, Luiz Leduino de Salles Neto
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Instituto Nacional de Pesquisas Espaciais (INPE)
• Programa de Pós-Graduação: Programa de Pós-Graduação do INPE em Computação Aplicada
• País: BR
• Resumo em Inglês: The q-gradient vector is a q-analogue of the classical gradient vector based on the Jackson's derivative with the property of reducing the classical gradient when the parameter q tends to 1. The first method based on these concepts is the q-G method, a generalization of the steepest descent method to continuous global optimization problems, and it returns to its classical version when q $\rightarrow$ 1. The proposal of the q-G method is to define the search direction from the q-gradient vector of the objective function. This direction to- gether with appropriate strategies for obtaining the parameter q necessary for calculating the q-gradient vector, and the step length provide the q-G method mechanisms to escape local minima by a smooth transition between global search and local search during the iterative procedure. This work presents an extension of this study, with the development of the new q-versions where the limit q $\rightarrow$ 1, returns its classical versions. We developed a q-version of the Fletcher-Reeves conjugate gradient method, called q-CG method and two q-versions of the quasi-Newton methods, called q-BFGS and q-DFP methods, generalizations of the methods of Broyden-Fletcher-Goldfarb-Shanno and Davidon-Fletcher- Powell, respectively. As the q-G method, the methods are implemented such that the search process gradually shifts from global search at the beginning of the iterative procedure to the local search at the end of the iterative procedure. Moreover, gaussian perturbations are used in some iteration to guarantee the convergence of the methods to the global minimum in a probabilistic sense. We compare the convergent q-versions with their classical versions and with other methods, including CMA-ES, a variant of Controlled Random Search, Controlled Random Search with Local Mutation (CRS2-LM), an inte- rior point algorithm (IPOPT), another evolution strategy (ISRES), and the Nelder-Mead direct search method, amounting 13 different methods. The comparisons were performed to 27 well-known test problems in the literature. In general, the methods based on the q-gradient vector are competitive and promising, especially when applied to multimodal optimization problems. Moreover, the methods were applied to two complex optimization problems and the results showed the feasibility of their use in to solve hard problems.
• Link de acesso: http://urlib.net/sid.inpe.br/mtc-m21b/2016/04.25.17.23

O vetor q-gradiente é um q-análogo do vetor gradiente clássico baseado na derivada de Jackson, com a propriedade de reduzir ao gradiente clássico quando o parâmetro q tende a 1. O primeiro método baseado nesses conceitos é o método q-G, uma generalização do método da máxima descida para problemas de otimização global contínuos, e que retorna a sua versão clássica quando q $\rightarrow$ 1. A proposta do método q-G é definir a sua direção de busca a partir do vetor q-gradiente da função objetivo. Essa direção juntamente com estratégias apropriadas para a obtenção do parâmetro q, necessário para calcular o vetor q-gradiente, e o tamanho do passo fornecem ao método q-G mecanismos para escapar de mínimos locais por meio de uma transição suave entre busca global e busca local ao longo do procedimento iterativo. Este trabalho apresenta uma extensão desse estudo, com o desenvolvimento de novas q-versões, onde no limite, q $\rightarrow$ 1, retomem suas versões clássicas. Foram desenvolvidas uma q-versão do método dos gradientes conjugados de Fletcher e Reeves, denominado método q-GC e duas q-versões dos métodos quase-Newton, método q-BFGS e método q-DFP, generalizações dos métodos de Broyden-Fletcher-Goldfarb-Shanno e Davidon-Fletcher-Powell, respectivamente. Assim como o método q-G, esses métodos são implementados de tal forma que o processo de busca muda gradualmente de busca global no início do procedimento iterativo, para busca local no final do procedimento iterativo. Além disso, perturbações gaussianas são usadas em algumas iterações para garantir a convergência desses métodos para o extremo global em um sentindo probabilístico. As q-versões com prova de convergência foram comparadas com as suas versões clássicas e com outros métodos, incluindo uma estratégia evolutiva com matriz de covariância adaptada (CMA-ES), uma variação da busca aleatória controlada (CRS2-LM), um método de ponto interior que usa derivadas por diferenças finitas (IPOPT), um método de busca direta de Nelder-Mead e outra estratégia evolutiva (ISRES), totalizando 13 métodos diferentes. As comparações foram realizadas para 27 funções testes de 10 dimensões bem conhecidas na literatura. No geral, os resultados mostraram que os métodos baseados no vetor q-gradiente são competitivos e promissores, especialmente quando aplicados aos problemas de otimização multimodal. Além disso, os métodos também foram aplicados em dois problemas complexos de otimização e os resultados mostraram a viabilidade de seu uso em problemas de difícil solução.