Métodos de máximo declive para minimização quadrática

Abstract

Neste trabalho apresentamos uma descrição detalhada do método de máximo declive para problemas quadráticos com busca unidirecional exata (método de Cauchy). Esse método é globalmente convergente, porém é ineficiente, pois é lento e apresenta um comportamento oscilatório, convergindo para uma busca no espaço gerado pelos autovetores associados ao maior e ao menor autovalor da matriz Hessiana do problema quadrático. Analisamos o comportamento oscilatório do gradiente da função objetivo no caso quadrático, bem como da sequência de passos gerados pelo método de Cauchy. Apresentamos o método de Barzilai-Borwein que, experimentalmente, exibe um desempenho melhor do que o método de Cauchy, e, também, algumas variantes do método de Barzilai-Borwein. Analisamos o comportamento do gradiente causado pela escolha de outros tamanhos de passos no método de máximo declive, o que nos permitiu propor uma nova escolha para o tamanho de passo. Com isso, propomos alguns novos algoritmos Cauchy-short, alternated Cauchy-short e outros) que alternam o tamanho de passo entre passos de Cauchy e passos curtos. Adotamos, ainda, uma nova proposta que utiliza passos de tamanhos dados por raízes de um polinômio de Chebyshev de ordem adequada. Experimentalmente, os novos métodos apresentam um bom desempenho, superando inclusive o método de Barzilai-Borwein. Além do bom desempenho, os novos métodos têm a vantagem de gerar sequências monotonicamente decrescentes de valores da função objetivo.<br>

Abstract : In this thesis we show a detailed description of the steepest descent method for quadratic problems with exact line searches (Cauchy Method). Although this method is globally convergent, it is inefficient because it is slow and it shows an oscillatory behavior, converging to a search in the space spanned by the eigenvectors associated with the largest and the smallest eigenvalue of the Hessian matrix of the quadratic objective. We analyze the oscillatory behavior of the gradient of the objective function in the quadratic case as well as the sequence of steps generated by the Cauchy method. We describe the Barzilai-Borwein method, which experimentally shows a better performance than the Cauchy method, and also some of its variations. We analyzed the behavior of the gradients due to the choice of different step sizes in the steepest descent method, which allowed us to come up with a new choice for the step size. Thus, we introduce a few new algorithms (Cauchy-short, alternated Cauchy-short and others) which alternate the step sizes between Cauchy steps and short steps. We also describe a new strategy based on step sizes given by the roots of a Chebyshev polynomial with suitable order. Experimentally, the new algorithms show a good enough performance, even better than the Barzilai-Borwein method. Besides the good performance, the new methods have the advantage of generating monotonically decreasing objective function values.