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


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 ArmijoEditar

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.

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étodoEditar

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çaEditar

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 melhoradoEditar

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áticoEditar

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.