|
Esta é a versão para impressão de Otimização
- Se você for imprimir esta página, escolha "Visualizar impressão" no seu navegador, ou clique em Versão para impressão, você irá ver esta página sem esse aviso, sem os elementos de navegação a esquerda ou acima, e sem as TOC's de cada página.
- Atualize esta página para ter certeza de que está imprimindo a versão mais atual.
- Para maiores informações sobre a versão para impressão, incluindo como fazer arquivos PDF realmente adequados para a impressão, veja Wikilivros:Versões para impressão.
|
|
Otimização
|
|
|
Este material está sendo elaborado com base nas notas de aula da disciplina Otimização II, do curso de Matemática Industrial oferecido pela UFPR, ministrada pelo professor Wilfredo, no segundo semestre letivo do ano de 2008.
O conteúdo do livro não precisa (nem deve) se limitar àquele que consta atualmente no índice. Sendo assim, a qualquer momento o livro pode ser revisto e ampliado.
Sinta-se a vontade para ler este ou quaisquer outros livros do projeto, melhorando-os conforme lhe for possível. Com isso estará ajudando a aumentar a quantidade e a qualidade dos textos didáticos disponíveis em língua portuguesa, ao mesmo tempo em que colaborará com o crescimento projeto Wikilivros como um todo.
Se tiver dúvidas ou sugestões sobre páginas específicas, utilize as páginas de discussão correspondentes para deixar um comentário a respeito.
Ainda há muito por fazer, mas cada um daqueles que contribuem acredita estar fazendo o possível para oferecer o melhor a todos.
- Este método foi originalmente proposto por Hestenes e Stiefel, em 1952.
- Seu objetivo inicial foi a resolução de problemas quadráticos sem restrições, mas logo o mesmo foi estendido para casos mais gerais.
Este método pode ser considerado sob dois pontos de vista:
- Como um método de descida, com busca linear exata;
- Como um método de resolução de sistema linear, baseado em um processo de ortogonalização.
Este é um conjunto convexo, pois todo segmento com extremidades no conjunto está totalmente contido no conjunto.
Este é um conjunto côncavo, pois existe um segmento com extremidades no conjunto que não está totalmente contido no conjunto.
Nota: Uma matriz é definida positiva se, e somente se, todos os seus autovalores são positivos.
Tem-se:


Sendo
, segue em particular que
e
, onde
é uma matriz diagonal cujos elementos da diagonal são os autovalores de
e
é uma matriz onde as colunas são os autovetores correspondentes aos autovalores.
Note que
é uma matriz simétrica, pois é a matriz Hessiana de uma função com segundas derivadas parciais contínuas, e consequentemente vale
.
Para introduzir o método de direções conjugadas, serão consideradas somente funções quadráticas.
Uma condição necessária de primeira ordem para que
seja um ponto de mínimo para a função
é que
. Para o presente caso, a função
é convexa, então, a condição necessária
também é suficiente.
No caso de uma função quadrática, tem-se
, ou seja,
é solução do sistema linear
.
A resolução de um sistema linear nem sempre pode ser feita numericamente de forma eficiente. Por exemplo, se a matriz do sistema é:

A solução do sistema linear corresponde à interseção entre duas retas quase paralelas, e os erros de truncamento podem causar imprecisão na solução obtida computacionalmente.
Analiticamente, o sistema
tem
como solução. Então alguém poderia se perguntar: qual o problema em resolver esse sistema linear, se basta calcular a inversa da matriz
e multiplicar pelo vetor
? A resposta é que o calculo da inversa de uma matriz em geral é impraticável computacionalmente, por ter custo muito alto. Por isso, nas situações práticas, onde as matrizes tem ordem bem maior do que 2 (digamos 1000), o cálculo de matrizes inversas não é uma opção.
Assim, com o intuito de desenvolver um método computacional para o cálculo de minimizadores, é preciso utilizar outras técnicas. Considere o seguinte:
Em um método de descida tem-se sempre uma sequencia
, com
e
é um minimizador de

e

Logo,
e multiplicando por
obtem-se
. Consequentemente, o valor de
é dado por

Deste modo, o método consistirá de escolher em cada etapa
uma direção
, e calcular o coeficiente
pela fórmula anterior, para gerar o próximo ponto
. Mas como escolher a direção
?
Dado
e escolhido
, defina
como
, ou seja,
é a restrição da função
à reta que passa pelo ponto
e que tem direção
. Logo, derivando a expressão de
em relação a
, obtem-se

Então, no ponto de mínimo,
, tem-se

Ou seja, a direção
a ser seguida a partir do ponto
é ortogonal ao gradiente da função
, no ponto
.

Seja
o minimizador da função
. Tem-se

Mas
implica que
, logo

e consequentemente

Donde
. Portanto
.
Usando o resultado desse exercício, tem-se ainda que
Fazendo
, o método do gradiente conjugado escolhe as direções de descida tais que
. Mas quando
, tem-se na expressão apresentada anteriormente apenas
Finalmente, tem-se o algoritmo para este método.
Uma comparação da convergência do método de descida do gradiente com tamanho de passo ótimo (em verde) e o método do gradiente conjugado (em vermelho) para a minimização da forma quadrática com um sistema linear dado. O gradiente conjugado, assumindo aritmética exata, converge em no máximo
n passos onde
n é o tamanho da matriz do sistema (no exemplo,
n=2).
Primeiro passo: Escolha
Se
, então pare:
Senão:
Calcular
Passo iterativo
: Dado
Se
, então pare:
Senão:
Pode-se verificar facilmente que
. De fato, como
, tem-se
. Logo,
.
- Exercício
Provar que se
então
.
Considere
definida por
.
Em outros termos, tomando
, tem-se
, onde
.
Pode-se aplicar o método de direções conjugadas ao seguinte problema

Note, desde já, que o conjunto solução é
.
- Inicio
- Toma-se
arbitrário, por exemplo,
.
- Avalia-se o gradiente da função
neste ponto inicial: 
- Iteração 1



A seguir, verifica-se se o gradiente se anula no novo ponto
:

Como o gradiente já é nulo, não é preciso fazer a segunda iteração, e o ponto
é o (único) minimizador global de
.
Em um caso mais geral, considerando
definida por
, tem-se cálculos muito parecidos em cada passo.
O conjunto solução continua sendo
.
- Inicio
- Considere
como no primeiro exemplo, ou seja,
.
- Avalia-se o gradiente da função
neste ponto inicial: 
- Iteração 1



A seguir, verifica-se se o gradiente se anula no novo ponto
:

Novamente, o gradiente se anula já na primeira iteração, de modo que
é o minimizador global de
.
Um terceiro exemplo pode ser dado tomando
e
definida por
. Observe que tal matriz é simétrica e definida positiva:

Logo, os autovalores de
são
e
. Isso também implica que a função é fortemente convexa.
Aplicando o método:
- Início
- Toma-se um ponto arbitrário no plano, por exemplo
;
- Verifica-se se tal ponto é o minimizador global, avaliando nele o gradiente da função:
.
- Já que o gradiente não se anulou no chute inicial, é preciso escolher uma direção e um comprimento de passo para determinar a próxima aproximação:
- Iteração 1


Feitos esses cálculos, o próximo ponto é dado por

Para saber se será necessária uma nova iteração, ou se o minimizador foi encontrado, calcula-se o gradiente da função no ponto:
.
Novamente, será preciso calcular uma nova direção e um novo comprimento de passo:
- Iteração 2

onde
, no algoritmo de Hestenes é dado por:

Portanto

Além disso, o tamanho do passo é dado por

Portanto

Obviamente, este é o minimizador procurado (pois o método tem a propriedade de convergência quadrática, ou seja utiliza no máximo
iterações para chegar a solução quando aplicado a funções quadráticas definidas em
)
- Exercício
Implementar o algoritmo de Hestenes-Stiefel em alguma linguagem de programação, por exemplo em Scilab, ou Matlab.
- Exercício
Seja
um função quadrática fortemente convexa. Verifique as seguintes igualdades:
Abaixo é apresentada uma implementação deste algoritmo na linguagem de programação utilizada pelo Scilab.
A = [2 1; 1 2];
function [x] = min_gradiente_conjugado(xk)
//Entrada: xk em R^n, qualquer "chute inicial"
// Saída: x, o ponto em que f assume o valor mínimo
k = 0 //Indica quantos loops já foram feitos
epsilon = 0.01
n = size(xk,1)
g = df(xk)
seq = zeros(n,n+1)
seq(:,1) = xk
while (norm(g) > epsilon) & (k <= n)
if (k == 0)
d = -g
else
d = Hestenes(g,d,A)
end
t = busca_linear(g,d,A)
xk = xk + t*d
k = k+1
seq(:,k+1) = xk
g = df(xk)
end
plot(seq(1,:),seq(2,:))
x = xk
endfunction
function [fu] = f(u)
fu=(1/2)*(u'*A*u)
endfunction
function [grf] = df(u)
grf = A*u
endfunction
function [d] = Hestenes(g,d,A)
d=-g + ((g'*A*d)/(d'*A*d))*d
endfunction
function [t] = busca_linear(g,d,A)
t=(g'*g)/(d'*A*d)
endfunction
Para facilitar a compreensão do método, pode ser útil exibir as curvas de nível da função. Uma forma de implementar uma função com esse propósito é a seguinte:
function plotar_curvas
qtd=101
tam=max(seq)
x=linspace(-tam,tam,qtd)
y=x
z=zeros(qtd,qtd)
for i=1:qtd
for j=1:qtd
z(i,j)=f([x(i);y(j)])
end
end
contour2d(x,y,z,10)
a=gca();
a.x_location = "middle";
a.y_location = "middle";
endfunction
|
Um dos autores deste material sugeriu a adição de uma imagem para ilustrar o método de Fletcher-Reeves.
|
Esta versão é na verdade uma extensão do algoritmo anterior, permitindo a aplicação no caso de funções que não são quadráticas.
Primeiro passo: Escolha
Se
, então pare:
Senão:
(como em todo método de descida)
Calcular
, através de uma busca linear
Passo iterativo:
Se
, então pare:
Senão:
Calcular
, através de uma busca linear
|
Um dos autores deste material sugeriu a adição de uma implementação do algoritmo acima em SciLab.
|
|
Um dos autores deste material sugeriu a adição de uma imagem para ilustrar o método de Fletcher-Reeves.
|
Uma outra versão é a seguinte:
Primeiro passo: Tomar
Se
, então pare:
Senão:
(como em todo método de descida)
Calcular
, através de uma busca linear
Passo iterativo:
Se
, então pare:
Senão:
Calcular
, através de uma busca linear
|
Um dos autores deste material sugeriu a adição de uma implementação do algoritmo acima em SciLab.
|
- Exercício
Verificar que, no caso de uma função
quadrática e fortemente convexa, os algoritmos de Hestenes-Stiefel, de Fletcher-Reeves e de Polak-Ribière são os mesmos.
Para o caso de funções não quadráticas, é preciso usar algum método de busca linear para a implementação do método dos gradientes conjugados, seja a versão de Fletcher-Reeves ou a de Polak-Ribière. Uma possibilidade é a busca de linear de Armijo (ver Izmailov & Solodov (2007), vol 2, pag. 65), cujo algoritmo é esboçado a seguir:
function busca_linear_Armijo (f, theta, alpha, delta, t0)
while (alpha * pred > ared)
t = d * t
end
endfunction
com:



|
Implementar a regra de Armijo e corrigir o esboço acima.
|
Os métodos que recebem este nome fazem parte de uma família de métodos baseados em:
- Simplicidade conceitual;
- Eficiência prática;
Algumas das primeiras funções de penalidade foram desenvolvidas por:
- Courant (1943)
- Ablate Brighham (1955) (qual o artigo?)
- AV Fiacco, GP McCormick (1968) (qual o artigo?)
Para compreender este tipo de método, será considerado o seguinte problema:
Adicionalmente, se for considerado o conjunto de pontos
, o problema (P) se escreve ainda como
Uma primeira idéia para a resolução desse tipo de problema é fazer uso de funções indicadoras, conforme é definido a seguir:
- Definição
Dado um conjunto não vazio
, define-se a função indicadora
por:

Notas: A função indicadora
é às vezes denotada por
.
Para transformar um conjunto (P) em um problema sem restrições, pode-se proceder da seguinte maneira: Considerar o problema (PD), dado por:
Considerando
definida por:

Tem-se ainda o problema (PP), dado por:
Comentários:
- A grande vantagem desta idéia é que ela transforma um problema com restrições em um problema irrestrito.
- A principal desvantagem é que a função
definida a seguir é descontínua em cada ponto
:


Para contornar a desvantagem da descontinuidade da função apresentada anteriormente, surgem outras funções, como por exemplo:
Gráfico de uma função de penalidade


|
Um dos autores deste material sugeriu a adição de uma imagem para comparar uma função e sua correspondente .
|
Resolução
|
De fato, dada qualquer função , segue da própria definição de que

Mas

implica que

Portanto, . Como pode ser tomada arbitrariamente, tem-se em particular que .
|
|
Um dos autores deste material sugeriu conferir o enunciado do exercício anterior. A afirmação parece ser falsa nos casos em que .
|
A idéia de aplicar penalizações aos pontos que não pertencem ao conjunto viável é formalizada na seguinte definição:
- Definição
Seja
. A função
é chamada de função de penalidade exterior se possui as seguintes propriedades:
Nota: Lembre-se que
é o conjunto viável do problema (P).
Em particular, as funções
são funções de penalidade exterior.
|
Um dos autores deste material sugeriu a adição de exemplos de funções de penalidade, juntamente com algumas imagens ilustrando os seus gráficos.
|
Nota: Conforme o Wikcionário, o termo coercivo significa: que coage; que reprime; que impõe pena; coercitivo. Nesse sentido, esse é um termo adequado ao tratar do conceito anterior, no contexto dos métodos de penalidade.
|
Um dos autores deste material sugeriu a adição de uma imagem que ilustre geometricamente a relação entre coercividade e conjuntos de nível.
|
Resolução
|
Primeiramente, é uma função não negativa, pois o quadrado de qualquer número real é não negativo, assim como a soma de números reais não negativos.
Em segundo lugar, tem-se se, e somente se, para cada índice e cada índice vale e . Como , tem-se
Finalmente, como a soma e o produto de funções contínuas resulta em uma função contínua, segue que é contínua, pois são contínuas.
|
Resolução
|
Considere um ponto arbitrário . Tome . Nestas condições, é limitado (conforme um dos exercícios anteriores) e fechado (pois é pré-imagem de um conjunto fechado por uma função contínua), portanto compacto. Neste caso, conforme o teorema de Weierstrass, a função possui algum ponto de mínimo no conjunto , ou seja, existe tal que .
Ne verdade, tal ponto é também um minimizador global da função , pois se então (pela definição do conjunto ).
|
|
Um dos autores deste material sugeriu a adição de uma imagem ilustrando a existência de minimizadores globais para funções coercivas.
|
Em algumas situações, é interessante ter em mente que certos conceitos definidos no contexto da Otimização são, na verdade, instanciações de conceitos mais gerais, muitos deles provenientes da topologia. Alguns exemplos são apresentados a seguir.
- Exemplos


Em outras palavras, a topologia euclideana é a coleção de todos os conjuntos abertos contidos em
. Pode-se verificar com facilidade que de fato são satizfeitas as três propriedades que definem uma topologia.
Outro exemplo muito comum é o seguinte:
- Topologia euclideana estendida:

![{\displaystyle \Gamma =\Gamma _{1}\cup \left\{A\subset \mathbb {R} \cup \{\infty \}:\exists a\in \mathbb {R} ,A=\left]a,\infty \right]\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1714b9f65c53fef59fd69fcaa4fdb0428af11dd2)
Em geral, a noção de limite seria caracterizada topologicamente da seguinte forma:
- Definição

Uma vez apresentados os conceitos iniciais, pode-se provar o seguinte teorema:
- Teorema
Considere:
uma função de penalidade exterior;
uma função contínua;
um conjunto fechado;
uma sequência de termos positivos tal que
.
Suponha que é válida uma das seguintes propriedades:
é coerciva.
é limitado e
é coerciva.
Se, para cada

, for escolhido

,então:
possui algum ponto de acumulação;
- Todo ponto de acumulação de
é solução do problema (P);
.
|
Um dos autores deste material sugeriu a adição de uma imagem que ilustre geometricamente o significado do teorema acima.
|
Demonstração
|
Se (1) acontece, então é coerciva, pois

A desigualdade é válida pois é uma função de penalidade, portanto não negativa, e a igualdade se deve à hipotese sobre . Além de coerciva, tal função é contínua (pois é combinação linear de funções contínuas). Logo, a função possui um ponto de mínimo global, ou seja, existe tal que

, para qualquer .
Mas é contínua e coerciva, então também existe tal que

Por outro lado, se vale (2), então é contínua e C compacto. Analogamente, é contínua e compacto, donde tem-se algum tal que

Em ambos os casos, dada uma sequência tal que e , defina-se por . Logo,

Sendo que a primeira desigualdade se deve ao fato de ser um minimizador, por construção, e a segunda segue por que é decrescente. Portanto, .
Além disso, tem-se as seguintes desigualdades:


Logo, somando os membros correspondentes, obtem-se:

ou seja,

Portanto,

Por outro lado, , sendo primeira desigualdade válida por ser não negativa e positivo, e a segunda devida à própria definição de . Logo, .
Se a primeira das hipóteses acontece, segue da coercividade e dessa última desigualdade que . Então é uma sequência limitada.
Se ocorre a segunda, então é coerciva, mas foi mostrado que , consequentemente . Sendo coerciva, conclui-se novamente que é uma sequência limitada.
Portanto, em qualquer caso, possui algum ponto de acumulação.
Seja um ponto de acumulação de . Então existe tal que . Logicamente, . Pela continuidade de e sabendo que , se deduz que . Mas já havia sido verificado que , então segue a igualdade .
A sequência é crescente. Seja (por que razão ele existe?). Como , tem-se . Portanto, . Logo , ou seja, .
Como é contínua, , e este valor é nulo se, e somente se, .
Logo, , donde . Assim, tem-se , ou seja, é solução de (P).
|
- Exercício
Dado o problema (P), considere
(isso não quer dizer que o problema tenha solução). suponha-se que
e
são funções contínuas e que
seja não vazio, ou seja, que
é factível. Tome
como
, onde
denota a parte positiva de
, como de costume. Considere ainda
dada por
e, para cada
, seja
Nessas condições, provar que:
é uma função de penalidade exterior


- Se
então 
- Se
são covexas, então
é convexa.
- Se
são diferenciáveis, então
é diferenciável em
, e 
- Se
e
e se
é uma sequência tal que
e
então
é solução de (P).
Primeiro passo: Escolha
,
e
Passo iterativo
: Calcular
, solução global de
Escolha
tal que
Nota: Neste algoritmo,
é uma função de penalidade exterior.
Resolução
|
Esboço: Pode-se tomar , onde:



Tem-se então o problema irrestrito:
,
onde pode ser aplicado o método de gradientes conjugados.
|
Implementação do algoritmo de penalidade exterior em SciLab[editar | editar código-fonte]
Considerando o problema

com
uma função quadrática,
simétrica positiva definida,
lineares, e a função de penalidade,
, dada por:

Pode-se usar o método dos gradientes conjugados para resolver o seguinte problema:

onde
terá sua matriz Hessiana definida positiva.
|
Incluir o código para uma implementação do método em SciLab.
|
Este método também é conhecido como método de barreira. Ele consiste em trabalhar com funções de penalidade tais que
e qualquer que seja a sequência
para a qual
, se tem que a função de penalidade tende a
.
|
Um dos autores deste material sugeriu a adição de uma imagem para ilustrar uma sequência de pontos que tende a um ponto da fronteira de um conjunto C, de preferência junto com o gráfico de uma função de penalidade deste novo tipo.
|
Mas como conseguir esse tipo de função?
Considere o caso em que
.
Lembrando que a função logarítmica tem a propriedade:

pode-se tomar
, pois

implica que

Analogamente, tem-se

então, uma outra função com a propriedade desejada é
.
O problema a ser resolvido quando se quer aplicar o método de barreira é o seguinte:

onde
é tal que
Observação:
não é necessariamente igual ao interior do conjunto
. Por exemplo:
|
Um dos autores deste material sugeriu a adição de uma imagem para ilustrar um conjunto C cujo correspondente C0 seja diferente do interior de C.
|
Primeiro passo: Escolha
,
e
Passo iterativo
: Calcular
, solução global de
Escolha
tal que
Observação: Neste método os termos da sequência
estão sempre em
.
Implementação do algoritmo de barreira em SciLab[editar | editar código-fonte]
Considerando o problema

pode-se usar o método de barreira no conjunto:

Pode-se usar qualquer das funções de penalidade interior apresentadas, por exemplo:

ou ainda

Como
, o problema passa a ser:

Observação: Note que é necessário conhecer um ponto inicial
, para servir de primeira aproximação, ou ponto de partida para o algoritmo.
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.
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 na versão online deste material.
|
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
.
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.
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.
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
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.
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:
![{\displaystyle \min _{x\in \mathbb {R} ^{n}}\sum _{i=1}^{p}\left[h_{i}(x)\right]^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31c65c0dccda26b6c814e23c07fe3feb3edbe0eb)
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?