Algoritmo de procura com escolha dinâmica das coordenadas para programação não linear com restrições

Abstract

Neste trabalho desenvolvemos um algoritmo geral estocástico de filtro, para resolver pro-blemas de otimização não lineares e não convexos com restrições gerais. A generalidade deste algoritmo está no fato de que a análise de sua convergência quase certamente é garan-tida desde que a distribuição de probabilidade utilizada no cálculo dos iterandos satisfaça algumas hipóteses. O controle da inviabilidade é feito através da estratégia dos métodos de filtro. Baseados nesse algoritmo geral, desenvolvemos o Algoritmo FDDS, que baseia-se na ideia de busca com escolha dinâmica das coordenadas do Algoritmo DDS, para gerar os seus iterandos, e no método de filtro para controlar a inviabilidade. No FDDS os ite-randos são calculados adicionando-se perturbações aleatórias com distribuição normal nas coordenadas, escolhidas de forma dinâmica, do melhor ponto corrente. No entanto, com a estratégia de gerar múltiplos pontos tentativos em cada iteração, o gasto com avaliações da função objetivo pode ser bastante elevado. Com o intuito de reduzir o número de ava-liações de função, propomos o Algoritmo FDDSRBF, que também se encaixa na estrutura do algoritmo geral e cujos múltiplos pontos tentativos são gerados da mesma maneira que no FDDS. No entanto, o FDDSRBF utiliza um modelo cúbico de funções de base radial, para aproximar a função objetivo, na seleção do melhor ponto tentativo. Os algoritmos propostos não calculam ou aproximam quaisquer derivadas da função objetivo e das res-trições. Resultados teóricos acerca das condições suficientes para a convergência quase certamente dos algoritmos foram apresentados. Resultados computacionais promissores, comparando-se o desempenho dos algoritmos propostos com alguns algoritmos existentes na literatura ao resolverem 42 problemas de três conjuntos diferentes, foram apresentados. O Algoritmo FDDSRBF mostrou-se bastante eficiente e robusto, com uma significativa redução do número de avaliações de função.

In this work we present an stochastic lter algorithm for solving nonlinear and nonconvex constrained global optimization problems. The generality of this algorithm lies in the fact that the analysis of its convergence is almost always guaranteed once the probability distribution used in the calculation of the iterates satis es some hypotheses. The control of infeasibility is done through the strategy of the lter methods. Based on this general algorithm, we developed the FDDS algorithm, which combines the lter method with the dynamically dimensioned search algorithm. In the FDDS the iterates are calculated by adding random perturbations with normal distribution in the dynamically chosen coordinates of the best current point. However, with the strategy of generating multiple trial points in each iteration, the cost with objective function evaluations can be quite high. In order to reduce the number of function evaluations, we propose the FDDSRBF algorithm, which has the same general algorithm structure and whose multiple trial points are generated in the same way as in the FDDS. The FDDSRBF uses a cubic model of radial basis functions, to approximate the objective function, in the selection of the best trial point. The proposed algorithms do not compute or approximate any derivatives of the objective and constraint functions. Theoretical results concerning the su cient conditions for the almost surely convergence of the proposed algorithms were presented. Promising computational results, in comparison to performance of the proposed algorithms with other algorithms in the literature when solving 42 problems of three di erent sets, were obtained. The FDDSRBF Algorithm provided competitive results when compared to the other methods.