Otimização/Métodos de região de confiança

Origem: Wikilivros, livros abertos por um mundo aberto.
Saltar para a navegação Saltar para a pesquisa


Considere o seguinte problema de programação diferenciável não linear sem restrições:

onde é de classe .

Observação: Como não é necessariamente convexa, a matriz pode não ser definida positiva, apesar de ser simétrica. Neste caso, o método de Newton ou suas variantes (direções conjugadas, quase Newton, etc) não servem.

O primeiro método de região de confiança (em inglês, Trust region method), foi introduzido por Powel em 1970 (qual artigo?) mas oficialmente introduzido por Dennis em 1978 (artigo?). Ele consiste no seguinte:

A cada iteração, se constrói um modelo quadrático e uma região de confiança

este princípio pode ser considerado como uma extensão da busca de Armijo unidimensional.

Breve revisão da busca de Armijo[editar | editar código-fonte]

Para entender a geometria do método de região de confiança, é bom lembrar a geometria da busca de Armijo unidimensional.

Seja uma direção de descida de uma função a partir do ponto . Então . Agora, considerando , definida por , tem-se:

. Assim, . Se , então .
Exercício

Mostrar que sempre existe tal que .

Resolução
A resolução deste exercício é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

A busca de Armijo consiste em tomar .

Se

Mas como , então existe algum tal que vale . A tal ponto, chama-se ponto de Armijo.

Busca de Armijo.svg

Introduzindo as seguinte notação

(modelo linear para a função )
(redução predita por este modelo)
(redução real no valor da função)

a pergunta é:

Quando um ponto vai ser ponto de Armijo com essa notação?

Tem-se:

Logo, se segue que é um ponto de Armijo.

Observações: Note que a essência da busca linear de Armijo é construir um modelo linear e um intervalo compacto , sendo e o ponto inicial da busca e logo procurar o ponto de Armijo em .

De volta ao método[editar | editar código-fonte]

O método de região de confiança será uma generalização da busca de Armijo, consistindo da construção de um modelo quadrático e uma região , chamada de região de confiança, e nessa região calcular o novo iterando.

Algoritmo da região de confiança[editar | editar código-fonte]

Primeiro passo: Escolha , , ,  e .

Passo iterativo : Enquanto , construa o modelo quadrático:
 
Calcule , solução de
 
Tome  e 
Se , fazer 
Senão ,  e 

Comentários: No algoritmo anterior, quando se tem um passo falho, a região de confiança sempre diminui. Seria bom incluir casos bons, onde a região deve crescer.

Algoritmo da região de confiança melhorado[editar | editar código-fonte]

Primeiro passo: Escolha , , , , ,  e .

Passo iterativo : Enquanto , construa o modelo quadrático:
 
Continue = 1
Enquanto (Continue = 1)
  Calcule , solução de
   
  Tome  e 
  Se , fazer 
    Se , ; Continue = 0
    k = k+1
  Senão 


O subproblema quadrático[editar | editar código-fonte]

Conforme foi explicado, o método das regiões de confiança constrói um modelo quadrático da forma:

onde, no método, e . Em tal modelo, tem-se

  • um vetor não nulo;
  • uma matriz simétrica (que pode não ser definida positiva)

O problema quadrático é

com .

Este é o problema que será tratado a seguir.

Exercício

Provar que sempre tem solução.

Resolução
Esboço: Como é uma função contínua e o conjunto onde se quer minimizar tal função é uma bola, em dimensão finita, trata-se de minimizar uma função contínua em um compacto. Esse é um problema que tem solução, pelo teorema de Weierstrass.

O exercício anterior garante que o método está bem definido, quer dizer, todas as etapas podem ser realizadas.