Algoritmos de otimização contínua univariada

Abstract

Nesta dissertação são estudados alguns métodos numéricos de otimização de funções reais contínuas de uma variável real. Nesse sentido, e antes desta abordagem, são analisadas as técnicas clássicas de otimiza ção, sendo feito um estudo de condições de otimalidade de funções convexas e de funções contínuas. O estudo dos métodos numéricos é dividido em três categorias: métodos intervalares de eliminação (mé- todo de busca dicotómica, método de busca por bissecção, método de Fibonacci e método da secção áurea), métodos de aproximação polinomial (método de interpolação quadrática, método de interpolação cúbica e algoritmo de Davies, Swann e Campey) e busca linear inexata. Os métodos aplicam-se a funções unimodais, razão pela qual este conceito é introduzido e é discutida a sua utilização na redução de intervalos de incerteza. No final do estudo de cada método, são apresentados problemas resolvidos, com indicação de todos os passos de cada iteração ou aplicando rotinas em MATLAB, cujos códigos são explicitados ao longo do texto. Estudamos também propriedades dos números de Fibonacci para a verificação de que, em certo sentido, o método de Fibonacci é o método ideal para a contração do intervalo. Essas propriedades permitem também verificar a estreita inter-relação entre este método e o método da secção áurea.

In this dissertation some numerical methods for optimization of continuous real functions of a single real variable are studied. In this sense, and before this approach, the classical optimization techniques are analyzed and a study of optimality conditions for convex functions and continuous ones is made. The study of numerical methods is divided into three categories: interval methods of elimination (dichotomous search method, interval halving method, Fibonacci's method and golden section method), polynomial approximation methods (quadratic interpolation method, cubic interpolation method and Davies, Swann and Campey's algorithm) and inexact line search. The methods are applied to unimodal functions, that is why this concept is introduced and its use in reducing uncertainty intervals is discussed. For each method, solved problems are presented, showing all steps of each iteration or applying routines in MATLAB, whose codes are speci ed throughout the text. Properties of Fibonacci numbers are also studied showing that, in a sense, the Fibonacci method is the optimal method for contraction of the interval. These properties allow us also check the close interrelationship between this method and the method of golden section.