Ir para o conteúdo

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

Origem: Wikilivros, livros abertos por um mundo aberto.


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 hi(x)=0,i=1,…,p. No contexto do exemplo anterior, se procura um modelo linear para os dados, ou seja, uma função y=mx+n que os descreva da melhor forma possível. Assim, os parâmetros a considerar são m e n. Os valores ideais para essas variáveis seriam aqueles que verificassem as seguintes equações:

{2002m+n=177342003m+n=196692004m+n=209432005m+n=24083

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

h1(m,n)=2002m+n−17734
h2(m,n)=2003m+n−19669
h3(m,n)=2004m+n−20943
h4(m,n)=2005m+n−24083

É 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 p de equações bem maior que o número n de parâmetros a identificar. Em particular, quando todas as equações hi são lineares em suas n 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 hi em uma solução exata x 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 hi, para i=1,…,p 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 hi. Em símbolos, o problema passaria a ser:

minx∈ℝn∑i=1p[hi(x)]2

O caso linear

[editar | editar código]

Neste caso, para cada índice i=1,…,p, a função hi é afim linear, ou seja:

hi:ℝn↦ℝ
hi(x)=ai⊤x+bi

onde ai∈ℝn e bi∈ℝ para cada i=1,…,p. Deste modo, pode-se definir uma função H como

H:ℝn↦ℝp de modo que
H(x)=[h1(x)⋮hp(x)]=[a1⊤x+b1⋮ap⊤x+bp]=[a1⊤⋮ap⊤]x+[b1⋮bp]

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

A=[a1⊤⋮ap⊤],b=[b1⋮bp]

Assim,

H(x)=Ax+b

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

Ax=−b

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

minx∈ℝn12‖Ax+b‖2
Exercício

Verifique que se houver uma solução exata, ela também será um minimizador de ∑i=1p[hi(x)]2. A recíproca é verdadeira?

Resolução
Primeiramente, observe que para qualquer x tem-se
∑i=1p[hi(x¯)]2≥0

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

hi(x¯)=0

e consequentemente

∑i=1p[hi(x¯)]2=∑i=1p02=0

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

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

∑i=1p[hi(x¯)]2=ϵ>0 implica que existe algum i tal que hi(x~)>0

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

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

f(x)=12‖Ax+b‖2=12⟨Ax+b,Ax+b⟩=12x⊤A⊤Ax+b⊤Ax+12b⊤b

Logo, como B=A⊤A é simétrica e semi-definida positiva, tem-se f convexa. Isso implica que a condição necessária de primeira ordem é também suficiente. Assim, qualquer ponto x∈ℝn tal que ∇f(x)=0 é solução do problema aproximado.

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

0=∇f(x)=A⊤Ax+A⊤b

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

A⊤Ax=−A⊤b

Observe também que isso implica A⊤(Ax+b)=0, ou seja, Ax+b∈ker⁡(A⊤).


Exemplo de aplicação

[editar | editar código]

Considere dado um conjunto de pontos do plano ℝ2, por exemplo {(xi,yi)}i=1p, 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 mx+b. Então os parâmetros a identificar são m e b.

Como são as funções hi? Lembrando que tais funções teriam imagem igual a zero em uma solução exata, pode-se tomar hi(m,b)=mxi+b−yi

Assim,

H(x)=[h1(x)⋮hp(x)]=[mx1+b−y1⋮mxp+b−yp]=[mx1+b⋮mxp+b]+[−y1⋮−yp]=[x11⋮⋮xp1][mb]+[−y1⋮−yp]

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

A=[x11⋮⋮xp1],x=[mc],c=[−y1⋮−yp]

De fato, nesses termos tem-se

H(x)=Ax+c
2. Qual é a função quadrática que melhor se aproxima dos dados experimentais?
Resolução
As funções quadráticas possuem a forma ax2+bx+c. Então os parâmetros a identificar são a, b e c.

Pode-se tomar hi(a,b,c)=axi2+bxi+c−yi.

Procedendo como antes, tem-se

H(x)=Ax+c

onde

A=[x12x11⋮⋮⋮xp2xp1],x=[abc],c=[−y1⋮−yp]
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 A têm elementos elevados a potências cada vez maiores, fazendo com que os autovalores de A⊤A sejam cada vez mais dispersos. Com isso, A⊤A 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 | editar código]

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 | editar código]

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

(P){min⁡f(x)x∈ℝn

sendo hj:ℝn→ℝ, e portanto f=12∑j=1p[hj]2 de classe 𝒞2(ℝn). A idéia de Newton é usar o desenvolvimento até segunda ordem da série de Taylor da função f em cada ponto iterado. Isto é, se o iterado é x¯, então:

Q(x)=f(x¯)+∇f(x¯)⊤(x−x¯)+12(x−x¯)∇2f(x¯)(x−x¯)


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

Calculando o gradiente da função Q, segue:

∇Q(x)=∇f(x¯)+∇2f(x¯)(x−x¯)

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

0=∇Q(x∗)=∇f(x¯)+∇2f(x¯)(x∗−x¯)

donde

∇2f(x¯)(x∗−x¯)=−∇f(x¯)

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

x∗=x¯−[∇2f(x¯)]−1∇f(x¯)

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

xk+1=xk−[∇2f(xk)]−1∇f(xk)

Algoritmo de Newton (puro)

[editar | editar código]
Início: Tome x0∈ℝn
  Se ∇f(x0)=0, pare: x0 é ponto crítico.
  Senão, Calcule d0, solução de
    ∇2f(x0)d0=−∇f(x0)
    Faça x1=x0+d0 e k=1
Iteração: Se ∇f(xk)=0, pare: xk é ponto crítico.
  Senão, calcular dk, solução de
    ∇2f(xk)dk=−∇f(xk)
    Faça xk+1=xk+dk e k=k+1

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

f(x)=12∑i=1p[hi(x)]2

Calculando o gradiente desta função, resulta:

∇f(x)=∑i=1phi(x)∇hi(x)

Considera-se H:ℝn↦ℝp definida por

H(x)=[h1(x)⋮hp(x)]

Deste modo, a Jacobiana de H verifica:

∇f(x)=[JH(x)]H(x)

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

∇2f(x)=∑i=1phi(x)∇2hi(x)+∑i=1p∇hi(x)∇hi(x)⊤

Seja

B(x)=∑i=1p∇hi(x)∇hi(x)⊤=JH(x)JH(x)⊤

Sabe-se que uma matriz D é definida positiva se xtDx>0 para qualquer x≠0. Fazendo D=∇hi(x)∇hi(x)⊤, tem-se:

x⊤∇hi(x)∇hi(x)⊤x=[∇hi(x)⊤x]2≥0

Para que D seja definida positiva, é necessário que SP(∇hi(x))=ℝn ( deve gerar todo o espaço), neste caso, se diz que JH(x) é de posto máximo.

Algoritmo de Gauss-Newton

[editar | editar código]
Início: Tome x0∈ℝn
  Se ∇f(x0)=0, pare: x0 é ponto crítico.
  Senão, Calcule d0, solução de
    B(x0)d0=−∇f(x0), onde B(x)=∑i=1p∇hi(x)∇hi(x)⊤
    Faça x1=x0+d0 e k=1
Iteração: Se ∇f(xk)=0, pare: xk é ponto crítico.
  Senão, calcular dk, solução de
    B(xk)dk=−∇f(xk)
    Faça xk+1=xk+dk e k=k+1

Algoritmo de Levemberg-Marquardt

[editar | editar código]

A idéia de Levemberg-Marquardt foi perturbar a matriz B(x), considerando B(x)+ρI, para algum ρ>0 pequeno.

Início: Tome x0∈ℝn
  Se ∇f(x0)=0, pare: x0 é ponto crítico.
  Senão, Calcule d0, solução de
    (B(x0)+ρI)d0=−∇f(x0), onde B(x)=∑i=1p∇hi(x)∇hi(x)⊤
    Faça x1=x0+d0 e k=1
Iteração: Se ∇f(xk)=0, pare: xk é ponto crítico.
  Senão, calcular dk, solução de
    (B(x0)+ρI)dk=−∇f(xk)
    Faça xk+1=xk+dk e k=k+1
Exercício

Enumere as diferenças que existem nos seguintes algoritmos:

  • Newton
  • Gauss-Newton
  • Levenberg-Marquardt

Resolução
Newton

Desenvolvendo f em série de Taylor e exigindo que a matriz hessiana de f seja definida positiva o método de Newton usa dk=−[∇2f(xk)]−1∇f(xk).

Gauss-Newton

Em alguns casos a matriz hessiana de f 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

f(x)=12∑i=1p[hi(x)]2=12‖h(x)‖2=12h(x)⊤h(x).

Usando Taylor em h temos:

h(x¯)=h(x)+J(x)(x¯−x) onde J(x) é a jacobiana de h.

Substituindo h(x¯) na f temos


f(x¯)=12h(x¯)⊤h(x¯)=12(h(x)+J(x)(x¯−x))⊤(h(x)+J(x)(x¯−x))=12[(h(x)⊤h(x)+2h(x)⊤(J(x)(x¯−x))+(J(x)(x¯−x))⊤(J(x)(x¯−x))]=f(x)+h(x)⊤(J(x)(x¯−x))+(J(x)(x¯−x))⊤(J(x)(x¯−x))

Calculando o gradiente e depois a segunda derivada temos:

∇f(x¯)=J(x)⊤h(x)+J(x)⊤(J(x)(x¯−x)) e

∇2f(x¯)=J(x)⊤J(x)

Denotando B(x)=J(x)⊤J(x), então o método de Gauss-Newton escolhe dk tal que

B(xk)dk=−∇f(xk).


Levenberg-Marquardt

A idéia do método de Levenberg-Marquardt é pertubar a matriz B(x) um pouco, considerando B(x)+ρI com ρ>0 pequeno.

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

(B(xk)+ρI)dk=−∇f(xk).