Otimização/O problema de mínimos quadrados


Este tipo de problema é muito frequente em ciências experimentais. Para ter um exemplo em mente durante a discussão que será feita mais adiante, considere as seguintes informações:

Segundo dados disponibilizados pelo IBGE, o Produto Interno Bruto per capita na cidade de São Paulo, no período de 2002 a 2005, foi (em reais): 17734, 19669, 20943 e 24083, respectivamente.

Com base nessas informações, como poderia ser feita uma previsão do valor correspondente ao ano seguinte (2006)?

Uma escolha possível seria supor que a cada ano o PIB aumenta uma aproximadamente constante, ou seja, usar um modelo linear para obter tal estimativa (que possivelmente será bem grosseira). Intuitivamente, bastaria analisar os dados disponíveis e a partir deles deduzir qual é o aumento que ocorre a cada ano. Depois, a previsão para 2006 seria aproximadamente igual à de 2005 somada com aquele aumento anual.

Esta idéia poderia até funcionar para o caso deste exemplo, mas o que fazer se a quantidade de dados disponíveis sobre algum fenômeno (ou alguma situação) for significativamente maior?

A melhor escolha, sem dúvida, é fazer uso de um computador para obter o modelo que melhor descreve o "comportamento" dos dados experimentais.

Em geral, os problemas de mínimos quadrados consistem em identificar os valores de determinados parâmetros, de modo que se satisfaçam certas equações . No contexto do exemplo anterior, se procura um modelo linear para os dados, ou seja, uma função que os descreva da melhor forma possível. Assim, os parâmetros a considerar são e . Os valores ideais para essas variáveis seriam aqueles que verificassem as seguintes equações:

Note que a partir dessas equações poderiam ser definidas as funções como:

É de se esperar que o sistema de equações obtido a pouco não admitirá uma solução exata, pois se tem mais equações do que variáveis.

Isso geralmente acontece, pois é comum haver uma quantidade de equações bem maior que o número de parâmetros a identificar. Em particular, quando todas as equações são lineares em suas variáveis, dificilmente existirá uma solução exata para o sistema linear resultante, pois este terá mais equações do que incógnitas (como no exemplo). Em geral, não é possível encontrar parâmetros que satisfaçam exatamente todas as equações. Por isso, costuma-se tentar identificar os parâmetros que "melhor se aproximam" de uma solução exata, em algum sentido.

Uma forma de obter uma solução aproximada (uma "quase-solução") resulta da seguinte observação: o valor de cada função em uma solução exata deveria ser zero. Se tal exigência é restritiva demais, e com ela não é possível encontrar qualquer solução, uma possibilidade seria exigir um pouco menos. Por exemplo, poderia ser exigido apenas que o valor de , para seja, em geral, pequeno. Uma das formas de capturar essa idéia em termos mais precisos é dizer que se pretende minimizar a soma dos quadrados dos valores de cada . Em símbolos, o problema passaria a ser:

O caso linear

editar

Neste caso, para cada índice  , a função   é afim linear, ou seja:

 
 

onde   e   para cada  . Deste modo, pode-se definir uma função   como

  de modo que
 

Motivando a introdução da seguinte notação:

 

Assim,

 

Logo, buscar uma solução exata é o mesmo que procurar uma solução para o seguinte sistema linear:

 

E uma solução aproximada poderia ser buscada a partir do seguinte problema de minimização:

 
Exercício

Verifique que se houver uma solução exata, ela também será um minimizador de  . A recíproca é verdadeira?

Resolução
Primeiramente, observe que para qualquer   tem-se
 

Isso significa que   é uma cota inferior para os valores assumidos por esta soma de quadrados. Além disso, se   é uma solução exata, então para cada índice   tem-se:

 

e consequentemente

 

Então, em   a soma dos quadrados assume seu valor mínimo.

Não vale a recíproca, pois se para um certo   a soma dos quadrados assumir um valor positivo  , então

  implica que existe algum   tal que  

Isto significa que   não satisfaz a equação de índice  , e portanto não pode ser uma solução exata.

Analisando a função objetivo do problema de minimização anterior, tem-se:

 

Logo, como   é simétrica e semi-definida positiva, tem-se   convexa. Isso implica que a condição necessária de primeira ordem é também suficiente. Assim, qualquer ponto   tal que   é solução do problema aproximado.

Calculando o gradiente da função objetivo tem-se:

 

Deste modo, a solução do problema é obtida resolvendo o sistema

 

Observe também que isso implica  , ou seja,  .


Exemplo de aplicação

editar

Considere dado um conjunto de pontos do plano  , por exemplo  , representando dados obtidos experimentalmente.

Perguntas:

1. Qual é a função afim linear que melhor se aproxima dos dados experimentais?
Resolução
As funções afim lineares no plano são aquelas que possuem a forma  . Então os parâmetros a identificar são   e  .

Como são as funções  ? Lembrando que tais funções teriam imagem igual a zero em uma solução exata, pode-se tomar  

Assim,

 

A expressão final pode ser simplificada adotando a seguinte notação

 

De fato, nesses termos tem-se

 
2. Qual é a função quadrática que melhor se aproxima dos dados experimentais?
Resolução
As funções quadráticas possuem a forma  . Então os parâmetros a identificar são  ,   e  .

Pode-se tomar  .

Procedendo como antes, tem-se

 

onde

 
Exercício

Explorar o exemplo anterior com dados concretos, implementando um dos três métodos de gradientes conjugados.

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.
Observações

Conforme se aumenta o grau do polinômio que faz a aproximação dos dados, as colunas de   têm elementos elevados a potências cada vez maiores, fazendo com que os autovalores de   sejam cada vez mais dispersos. Com isso,   torna-se mal condicionada.

Exercício

É possível, usando o problema de mínimos quadrados, verificar o postulado de Euclides que diz que "por dois pontos distintos passa uma única reta"?

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.
Exercício

Usando o problema de mínimos quadrados, é possível inferir que "por três pontos distintos passa uma única curva quadrática"?

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.

O caso não linear

editar

Para esse tipo de problemas, há dois métodos:

  1. Gauss-Newton
  2. Levemberg-Marquardt

Ambos são métodos do tipo Newton. Então, para entender cada um deles é preciso entender o Método de Newton.

O método de Newton

editar

Para entender a essência do método de Newton, primeiro considere que o problema a ser resolvido é

 

sendo  , e portanto   de classe  . A idéia de Newton é usar o desenvolvimento até segunda ordem da série de Taylor da função   em cada ponto iterado. Isto é, se o iterado é  , então:

 


Então a condição de Newton é que em cada iteração a Hessiana   deve ser definida positiva.

Calculando o gradiente da função  , segue:

 

Se   é o (único) minimizador de  , então

 

donde

 

Sendo   definida positiva, tal matriz é também inversível. Portanto:

 

Assim, pode-se usar a seguinte iteração:

 

Algoritmo de Newton (puro)

editar
Início: Tome  
  Se  , pare:   é ponto crítico.
  Senão, Calcule  , solução de
     
    Faça   e  
Iteração: Se  , pare:   é ponto crítico.
  Senão, calcular  , solução de
     
    Faça   e  

Voltando ao problema original, de mínimos quadrados, se tinha:

 

Calculando o gradiente desta função, resulta:

 

Considera-se   definida por

 

Deste modo, a Jacobiana de   verifica:

 

pois o produto de uma matriz por um vetor tem como resultado um vetor que é a combinação linear das colunas da matriz, com coeficientes que são as coordenadas do vetor.

Além disso, tem-se

 

Seja

 

Sabe-se que uma matriz   é definida positiva se   para qualquer  . Fazendo  , tem-se:

 

Para que   seja definida positiva, é necessário que   ( deve gerar todo o espaço), neste caso, se diz que   é de posto máximo.

Algoritmo de Gauss-Newton

editar
Início: Tome  
  Se  , pare:   é ponto crítico.
  Senão, Calcule  , solução de
     , onde  
    Faça   e  
Iteração: Se  , pare:   é ponto crítico.
  Senão, calcular  , solução de
     
    Faça   e  

Algoritmo de Levemberg-Marquardt

editar

A idéia de Levemberg-Marquardt foi perturbar a matriz  , considerando  , para algum   pequeno.

Início: Tome  
  Se  , pare:   é ponto crítico.
  Senão, Calcule  , solução de
     , onde  
    Faça   e  
Iteração: Se  , pare:   é ponto crítico.
  Senão, calcular  , solução de
     
    Faça   e  
Exercício

Enumere as diferenças que existem nos seguintes algoritmos:

  • Newton
  • Gauss-Newton
  • Levenberg-Marquardt

Resolução
Newton

Desenvolvendo   em série de Taylor e exigindo que a matriz hessiana de   seja definida positiva o método de Newton usa  .

Gauss-Newton

Em alguns casos a matriz hessiana de   pode ser bem complicada. Nesses casos então a idéia do método de Gauss-Newton é usar uma boa aproximação para essa matriz. Podemos escrever

 .

Usando Taylor em   temos:

  onde   é a jacobiana de  .

Substituindo   na   temos


 

Calculando o gradiente e depois a segunda derivada temos:

  e

 

Denotando  , então o método de Gauss-Newton escolhe   tal que

 .


Levenberg-Marquardt

A idéia do método de Levenberg-Marquardt é pertubar a matriz   um pouco, considerando   com   pequeno.

Portanto o método de Levenberg-Marquardt escolhe   tal que

 .