O PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA TEORIA DE SISTEMAS LINEARES

[pic 1]

UNIVERSIDADE FEDERAL DO PARÁ – UFPA

INSTITUTO DE TECNOLOGIA – ITEC

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA

TEORIA DE SISTEMAS LINEARES

TRABALHO II

PROFESSORA: CAROLINA DE MATTOS AFFONSO

 RENAN LANDAU PAIVA DE MEDEIROS

BELÉM/PA

MAIO-2013

 

                                

---

OBJETIVOS:

Solucionar um problema não linear desenvolvendo um algoritmo computacional que minimize uma função. Objetivando minimizar esta função será utilizado dois métodos iterativos, o primeiro método será o método do gradiente (Steepest descet) juntamente com a busca dicotômica, o segundo método utilizado será o método do gradiente conjugado.

APRESENTAÇÃO DO PROBLEMA:

O problema de minimização utilizado para ser solucionado e analisado neste trabalho é mostrado abaixo:

[pic 2]

REFERÊNCIAL TEÓRICO:

1. MÉTODO DO GRADIENTE COM BUSCA DICOTOMICA

O método do gradiente utiliza-se de informações providas pelo vetor gradiente para encontrar a direção do valor ótimo de uma função.

Seja um vetor coluna [pic 3] que possua a dimensão [pic 4]e [pic 5]uma função objetivo de [pic 6] variáveis, tal que [pic 7] exista para [pic 8]. Combinando os valores obtidos para as derivadas parciais, compõe-se o que se chama de gradiente da função [pic 9], denotado por

[pic 10]

O vetor gradiente [pic 11] aponta na direção da máxima taxa de crescimento da função em cada ponto. Logo, o vetor [pic 12] aponta na direção do maior decaimento da mesma função. Para um dado ponto [pic 13], ao caminhar na direção oposta ao vetor gradiente, denotada por [pic 14], tende-se a encontrar valores cada vez menores da função em torno do ponto [pic 15]. Considerando a existência de um mínimo local dentro de um intervalo conhecido, tal caminhada levará à consecução do mínimo local.

O procedimento para implementação do método do gradiente é bem simples. Partindo de um ponto [pic 16], determina-se o valor de [pic 17] e a posição e um novo ponto [pic 18] pela expressão

[pic 19]

Este procedimento levará à determinação de pontos que obedecem à condição

[pic 20]

Esta condição garante que, quanto mais iterações foram realizadas, mais próximo do mínimo será a solução encontrada. No limite, quando o número de iterações tende ao infinito, o valor encontrado para a função objetivo [pic 21] será mínima, sendo, portanto, o ponto [pic 22] um mínimo local.

A variável [pic 23] determina a velocidade da descida durante a busca pelos próximos pontos. Quanto maior o valor de[pic 24], maior o deslocamento entre pontos de mínimo. Quanto menor o valor de[pic 25], menor o deslocamento.

Para minimizar a função [pic 26] o valor do gradiente será dado por

[pic 27]

Portanto, a expressão para determinação nos pontos pelo método do gradiente descendente é dada por

[pic 28]

Como ponto inicial, pode ser tomado as coordenadas localizadas no centro do intervalo, ou seja, [pic 29]. Entretanto, para este estudo utilizou-se os valores . [pic 30]

Com o intuito de minimizar o valor do parâmetro [pic 31] de acordo com a evolução do algoritmo, faz-se para cada ponto [pic 32], define-se uma reta na direção do vetor gradiente que passa por este ponto, consistindo esta reta uma função do parâmetro [pic 33], ou seja,

[pic 34]

Iniciando com [pic 35] e aumentando o seu valor de forma adaptativa, é possível encontrar um parâmetro ótimo [pic 36] que produz um mínimo para a função dentro do domínio estabelecido para o problema. Matematicamente, [pic 37] é determinado pela operação.

[pic 38]

Uma vez determinado o valor de[pic 39], determina-se o próximo ponto que irá aproximar o mínimo da função.

Um dos métodos para determinar o valor de [pic 40] é chamado de Busca Dicotômica. O uso da Busca Dicotômica reduz a quantidade de cálculo realizada para determinar o valor ótimo de [pic 41], esse método não utiliza derivadas e a idéia principal é a seguinte.

Dado um problema unidimensional, no qual se conhece um intervalo de incerteza [pic 42], que inclui a solução,

[pic 43]

o procedimento de busca consiste em sucessivamente excluir as partes do intervalo de incerteza que não contém o mínimo de [pic 44].

 Para redução do intervalo de incerteza [pic 45] particiona-se este intervalo em partes e avalia-se a função nas extremidades destas partes, sendo que a busca dicotômica realiza a redução do intervalo com duas avaliações da função objetivo. A partir do centro do intervalo de incerteza, a função é avaliada em dois pontos:

[pic 46]
[pic 47]

[pic 48]

Figura 1 – Gráfico da busca utilizada na busca dicotômica.

Quando [pic 49], sabe-se que o ponto de mínimo não se encontra no intervalo [pic 50]. O novo intervalo de incerteza será [pic 51].