Encontre o valor mínimo de
começando em
e
, usando o método do declive máximo, com o critério de parada de
. Explique seus resultados.
Passo 1
O enunciado pede para encontrar o valor mínimo de
começando em
, usando o método do declive máximo (steepest descent), com critério de parada
. Dados relevantes fornecidos:
- função:
; - ponto inicial:
; - critério de parada: erro relativo aproximado
(usarei a definição usual do erro aproximado relativo entre iterações: para cada componente e tomarei o máximo sobre componentes); - método: declive máximo (atualização pela direção negativa do gradiente).
Passo 2
Vou explicar como funciona o método e as fórmulas que vou usar (passo a passo e sem pular nada).
- Gradiente: o gradiente de
é o vetor das derivadas parciais, que indica a direção de subida mais rápida. Para a nossa função:
Então o gradiente é
Significado das variáveis:
e
são as coordenadas do ponto atual;
aponta para onde
aumenta mais rápido.
- Regra de atualização do declive máximo: a cada iteração
atualizamos o ponto na direção negativa do gradiente:
onde
e
é o tamanho do passo (learning rate). Aqui precisamos escolher
.
- Escolha ótima de
(linha de busca exata) para uma função quadrática: se escrevermos na forma quadrática centralizada , a escolha exata de que minimiza é
No nosso caso
pode ser vista com matriz hessiana
(onde
é a identidade
); portanto
Conclusão: para esta função quadrática específica a linha de busca exata dá sempre
(independente de
). Isso simplifica muito as contas e é um ponto importante a entender: a hessiana constante e proporcional a identidade faz com que o passo ótimo seja constante.]
Passo 3
Primeira iteração (a partir de
) — vou calcular tudo detalhadamente.
- Gradiente no ponto inicial:
- Usando
, a atualização é
- Valores da função:
Observação: já no primeiro passo obtivemos
, que é o valor mínimo absoluto possível (soma de quadrados não-negativa).
- Verificação do critério
: calculo o erro aproximado relativo entre iterações (componente a componente) e tomo o máximo:
O erro aproximado usado é o máximo, então
Como
, o critério de parada ainda não é satisfeito se eu parar aqui imediatamente.]
Passo 4
Segunda iteração — necessário porque o critério de parada relativo ainda não foi satisfeito pelo procedimento de verificação após a primeira atualização.
- Calculo o gradiente no ponto
:
- Atualização com
:
Ou seja, o ponto não muda (já estamos exatamente no minimizador).
- Calculo do erro aproximado relativo entre iterações 1 e 2:
Assim
, ou seja, o critério de parada é satisfeito aqui.
- Interpretação: chegamos exatamente ao minimizador
na primeira atualização; a segunda iteração apenas confirma que o gradiente é nulo e não há alteração. Portanto o algoritmo convergiu em prática com duas avaliações (a avaliação inicial e a que verificou mudança nula), e o valor mínimo é .]
Passo 5
Explicação final, intuitiva e motivacional:
- A função é uma soma de quadrados com centro em
. Seus contornos são círculos centrados em . O gradiente aponta radialmente para fora do centro; o declive máximo (direção negativa do gradiente) aponta diretamente para o centro. Com a linha de busca exata numa quadrática com hessiana , o passo ótimo é em qualquer ponto, então a atualização leva diretamente ao centro em um único passo a partir de qualquer ponto — é por isso que aqui a convergência foi tão rápida. - Na prova: calcule sempre o gradiente, escreva a regra de atualização, verifique se consegue uma linha de busca exata (para quadráticas simples isso dá
), faça as contas aritméticas e depois verifique o critério de parada (erro relativo entre iterações). Mesmo que o critério não seja satisfeiro imediatamente, se o gradiente for zero o ponto já é minimizador. - Fica a dica: quando a hessiana for
com , o passo ótimo será . Aqui , daí .
Resposta
Ponto mínimo:
Valor mínimo:
Número de iterações até satisfazer : 2 (primeira atualização chega ao minimizador; segunda iteração confirma erro zero).
Valor mínimo:
Número de iterações até satisfazer