Encontre o valor mínimo de
f(x, y)=(x-3)^{2}+(y-2)^{2}
começando em x=1 e y=1, usando o método do declive máximo, com o critério de parada de \varepsilon_{s}=1 \%. Explique seus resultados.

Passo 1

O enunciado pede para encontrar o valor mínimo de
f(x,y)=(x-3)^{2}+(y-2)^{2}
começando em (x,y)=(1,1), usando o método do declive máximo (steepest descent), com critério de parada \varepsilon_{s}=1\%. Dados relevantes fornecidos:
  • função: \;f(x,y)=(x-3)^{2}+(y-2)^{2};
  • ponto inicial: \;(x_{0},y_{0})=(1,1);
  • critério de parada: erro relativo aproximado \varepsilon_{s}=1\% (usarei a definição usual do erro aproximado relativo entre iterações: para cada componente \displaystyle \varepsilon_{\text{ap}}^{(i)}=\frac{|x_{k+1}^{(i)}-x_{k}^{(i)}|}{|x_{k+1}^{(i)}|}\times100\% 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).
  1. Gradiente: o gradiente de f é o vetor das derivadas parciais, que indica a direção de subida mais rápida. Para a nossa função:
\frac{\partial f}{\partial x}=2(x-3),\qquad \frac{\partial f}{\partial y}=2(y-2).
Então o gradiente é
\nabla f(x,y)=\begin{pmatrix}2(x-3)\\[4pt]2(y-2)\end{pmatrix}.
Significado das variáveis: x e y são as coordenadas do ponto atual; \nabla f(x,y) aponta para onde f aumenta mais rápido.
  1. Regra de atualização do declive máximo: a cada iteração k atualizamos o ponto na direção negativa do gradiente:
\mathbf{x}_{k+1}=\mathbf{x}_{k}-\alpha_{k}\,\nabla f(\mathbf{x}_{k}),
onde \mathbf{x}_{k}=(x_k,y_k)^{T} e \alpha_{k}>0 é o tamanho do passo (learning rate). Aqui precisamos escolher \alpha_k.
  1. Escolha ótima de \alpha_k (linha de busca exata) para uma função quadrática: se escrevermos f na forma quadrática centralizada f(\mathbf{x})=\tfrac{1}{2}\mathbf{x}^{T}A\mathbf{x}-\mathbf{b}^{T}\mathbf{x}+c, a escolha exata de \alpha_k que minimiza f(\mathbf{x}_k-\alpha \nabla f_k) é
\alpha_k=\frac{\nabla f_k^{T}\nabla f_k}{\nabla f_k^{T}A\nabla f_k}.
No nosso caso f(x,y)=(x-3)^2+(y-2)^2 pode ser vista com matriz hessiana A=2I (onde I é a identidade 2\times2); portanto
\alpha_k=\frac{\nabla f_k^{T}\nabla f_k}{\nabla f_k^{T}(2I)\nabla f_k}=\frac{\nabla f_k^{T}\nabla f_k}{2\,\nabla f_k^{T}\nabla f_k}=\frac{1}{2}.
Conclusão: para esta função quadrática específica a linha de busca exata dá sempre \alpha_k=\tfrac{1}{2} (independente de k). 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 (x_0,y_0)=(1,1)) — vou calcular tudo detalhadamente.
  1. Gradiente no ponto inicial:
\nabla f(x_0,y_0)=\begin{pmatrix}2(1-3)\\[4pt]2(1-2)\end{pmatrix}=\begin{pmatrix}-4\\[4pt]-2\end{pmatrix}.
  1. Usando \alpha_0=\tfrac{1}{2}, a atualização é
\begin{pmatrix}x_1\\[4pt]y_1\end{pmatrix}=\begin{pmatrix}1\\[4pt]1\end{pmatrix}-\tfrac{1}{2}\begin{pmatrix}-4\\[4pt]-2\end{pmatrix} =\begin{pmatrix}1\\[4pt]1\end{pmatrix}+\begin{pmatrix}2\\[4pt]1\end{pmatrix}=\begin{pmatrix}3\\[4pt]2\end{pmatrix}.
  1. Valores da função:
f(x_0,y_0)=(1-3)^2+(1-2)^2=4+1=5,
f(x_1,y_1)=(3-3)^2+(2-2)^2=0+0=0.
Observação: já no primeiro passo obtivemos f=0, que é o valor mínimo absoluto possível (soma de quadrados não-negativa).
  1. Verificação do critério \varepsilon_{s}=1\%: calculo o erro aproximado relativo entre iterações (componente a componente) e tomo o máximo:
\varepsilon_{\text{ap}}^{(x)}=\frac{|x_1-x_0|}{|x_1|}\times100\%=\frac{|3-1|}{|3|}\times100\%=\frac{2}{3}\times100\%\approx66{,}67\%,
\varepsilon_{\text{ap}}^{(y)}=\frac{|y_1-y_0|}{|y_1|}\times100\%=\frac{|2-1|}{|2|}\times100\%=\frac{1}{2}\times100\%=50\%.
O erro aproximado usado é o máximo, então \varepsilon_{\text{ap}}=\max(66{,}67\%,50\%)=66{,}67\%. Como 66{,}67\%>1\%, 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.
  1. Calculo o gradiente no ponto (x_1,y_1)=(3,2):
\nabla f(3,2)=\begin{pmatrix}2(3-3)\\[4pt]2(2-2)\end{pmatrix}=\begin{pmatrix}0\\[4pt]0\end{pmatrix}.
  1. Atualização com \alpha_1=\tfrac{1}{2}:
\begin{pmatrix}x_2\\[4pt]y_2\end{pmatrix}=\begin{pmatrix}3\\[4pt]2\end{pmatrix}-\tfrac{1}{2}\begin{pmatrix}0\\[4pt]0\end{pmatrix}=\begin{pmatrix}3\\[4pt]2\end{pmatrix}.
Ou seja, o ponto não muda (já estamos exatamente no minimizador).
  1. Calculo do erro aproximado relativo entre iterações 1 e 2:
\varepsilon_{\text{ap}}^{(x)}=\frac{|x_2-x_1|}{|x_2|}\times100\%=\frac{|3-3|}{3}\times100\%=0\%,
\varepsilon_{\text{ap}}^{(y)}=\frac{|y_2-y_1|}{|y_2|}\times100\%=\frac{|2-2|}{2}\times100\%=0\%.
Assim \varepsilon_{\text{ap}}=\max(0\%,0\%)=0\% \le 1\%, ou seja, o critério de parada é satisfeito aqui.
  1. Interpretação: chegamos exatamente ao minimizador (3,2) 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 é f_{\min}=0.]

Passo 5

Explicação final, intuitiva e motivacional:
  • A função é uma soma de quadrados com centro em (3,2). Seus contornos são círculos centrados em (3,2). 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 2I, o passo ótimo é \alpha=\tfrac{1}{2} 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á \alpha=\tfrac{1}{2}), 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 cI com c>0, o passo ótimo será \alpha=1/c. Aqui c=2, daí \alpha=1/2.

Resposta

Ponto mínimo: (3,2)
Valor mínimo: 0
Número de iterações até satisfazer \varepsilon_{s}=1\%: 2 (primeira atualização chega ao minimizador; segunda iteração confirma erro zero).

Exercícios relacionados