Reformulação de um algoritmo de otimização global para uma classe de problemas não convexos e contínuos

Abstract

Resumo: Neste trabalho, reformulamos o algoritmo de otimização global GOP para uma classe de problemas que satisfaz determinadas condições. Essas condições impõe que o problema seja bilinear e que as variáveis que determinam diferentes termos bilineares sejam únicas. Além disso, através de exemplos didáticos, mostramos que a partir de manipulações algébricas estas condições se aplicam a classe de problemas mais gerais, como quadráticos e polinomiais. A partir da reformulação do algoritmo GOP, garantimos uma redução no número de restrições que se acumulam ao longo das iterações, apresentamos novos significados para algumas propriedades já conhecidas do algoritmo GOP. Consequentemente, uma nova formulação para os problemas duais relaxados é fornecida. Por fim, testes numéricos foram realizados para comparar o tempo computacional entre o algoritmo GOP da literatura e o algoritmo GOP com as modificações propostas neste trabalho. Nos testes, o modelo proposto proporciona uma redução média de até 70% no tempo computacional. Além disso, com o intuito de destacar a importância da otimização global em comparação com a local, foram confrontados os valores ótimos obtidos entre o algoritmo de otimização global e o solver fmincon disponível no Matlab. Com o uso da otimização global, quando comparada com a local, obtemos uma redução do valor ótimo de até 2417,26%.

Abstract: In this thesis, we reformulate the GOP global optimization algorithm for a class of problems that satisfy certain conditions. These conditions impose that the problem be bilinear and that the variables determining the bilinear terms be unique. Furthermore, through didactic examples, we show that from algebraic manipulations these conditions apply to a more general class of problems, such as quadratic and polynomial problems. Based on the reformulation of the GOP algorithm, we guarantee a reduction in the number of constraints that accumulate over iterations, we present new meanings for some already known properties of the GOP algorithm. Consequently, a new formulation for the relaxed dual problems is provided. Finally, numerical tests were performed to compare the computational time between the GOP algorithm from the literature and the GOP algorithm with the modifications proposed in this thesis. In the tests, the proposed model provides an average reduction of up to 70% in computational time. Moreover, with the objective of highlighting the importance of the global optimization in comparison with the local one, the optimal values obtained between the global optimization algorithm and the fmincon solver available in Matlab were compared. With the use of the global optimization, when compared to the local one, we obtain a reduction of the optimal value of up to 2417.26%.