Defina uma função objetivo qualquer dependente de pelo menos duas variáveis e faça pelo menos quatro iterações usando o método de busca linear ou da região de confiança.

Passo 1

Enunciado (o que temos e o que se pede):
  • Definir uma função objetivo que dependa de pelo menos duas variáveis.
  • Escolher um ponto inicial e realizar pelo menos quatro iterações de um método de busca linear (ou da região de confiança) aplicadas a essa função.
  • Entregar as iterações passo a passo, mostrando os cálculos de gradiente, direção e paso de linha em cada iteração.
Dados que vou usar (já definidos aqui, sem pedir nada a você):
  • Função objetivo escolhida:
f(x,y)=2x^{2}+xy+y^{2}-8x-3y.
  • Vou trabalhar no espaço vetorial com x=(x,y)^{T}. Para essa função podemos escrever em forma matricial padrão (muito útil para cálculos):
f(x)=\tfrac{1}{2}x^{T}A x - b^{T}x,
onde
A=\begin{pmatrix}4 & 1 \\[4pt] 1 & 2\end{pmatrix},\qquad b=\begin{pmatrix}8\\[2pt]3\end{pmatrix}.
  • Ponto inicial escolhido: \;x_{0}=(0,0)^{T}.
  • O pedido: efetuar, passo a passo, pelo menos quatro iterações do método de busca linear (aqui: gradiente descendente pela direção de maior descida, com busca linear exata em cada iteração), mostrando todos os cálculos.]

Passo 2

Explicação didática do método que vou usar (passo a passo teórico, bem mastigado). Não se preocupe com nomes técnicos — vou explicar como usar isto na prova.
  • Ideia geral: a cada iteração k temos um ponto x_{k}. Calculamos o gradiente \nabla f(x_{k}) — que indica a direção de subida mais íngreme; a direção de descida mais rápida é -\nabla f(x_{k}). Tomamos essa direção como direção de busca p_{k}=-\nabla f(x_{k}). Em seguida escolhemos um comprimento de passo \alpha_{k}>0 (a “busca linear”) que minimiza f(x_{k}+\alpha p_{k}) ao longo da reta. Finalmente atualizamos x_{k+1}=x_{k}+\alpha_{k}p_{k}.
  • Para uma função quadrática convexa como a nossa, com f(x)=\tfrac{1}{2}x^{T}A x - b^{T}x e A simétrica definida positiva, o gradiente é
\nabla f(x)=Ax-b.
A direção de descida escolhida é
p_{k}=-\nabla f(x_{k}).
  • A escolha ótima (exata) de \alpha_{k} para essa linha reta pode ser obtida resolvendo a minimização unidimensional
\alpha_{k}=\arg\min_{\alpha\in\mathbb{R}} f(x_{k}+\alpha p_{k}).
Para quadráticas essa \alpha_{k} tem fórmula fechada (não precisa derivar cada vez): com g_{k}=\nabla f(x_{k}) e p_{k}=-g_{k},
\alpha_{k}=\frac{g_{k}^{T}g_{k}}{g_{k}^{T}A g_{k}}.
Essa fórmula é muito prática: no denominador aparece A (a matriz da quadrática) e no numerador o quadrado da norma do gradiente.
  • Atualização final:
x_{k+1}=x_{k}-\alpha_{k} g_{k}.
Vou aplicar exatamente esse procedimento: calcular g_{k}, calcular \alpha_{k} pela fórmula acima e obter x_{k+1}. Em cada passo explico como calculei números e mostro o valor aproximado (com vírgula decimal, para você poder anotar na prova sem depender de notação diferente).

Passo 3

Iteração 0 → cálculo de \;x_{1} a partir de \;x_{0}=(0,0)^{T}.
  • Gradiente em \;x_{0}:
g_{0}=\nabla f(x_{0})=A x_{0}-b = \begin{pmatrix}4 & 1\\[2pt]1 & 2\end{pmatrix}\begin{pmatrix}0\\[2pt]0\end{pmatrix}-\begin{pmatrix}8\\[2pt]3\end{pmatrix}=\begin{pmatrix}-8\\[2pt]-3\end{pmatrix}.
  • Direção de descida: p_{0}=-g_{0}=\begin{pmatrix}8\\[2pt]3\end{pmatrix}.
  • Cálculo de \alpha_{0} pela fórmula exata:
\alpha_{0}=\frac{g_{0}^{T}g_{0}}{g_{0}^{T}A g_{0}}.
Calculemos numericamente:
g_{0}^{T}g_{0}=(-8)^{2}+(-3)^{2}=64+9=73,
A g_{0}=\begin{pmatrix}4 & 1\\[2pt]1 & 2\end{pmatrix}\begin{pmatrix}-8\\[2pt]-3\end{pmatrix}=\begin{pmatrix}-35\\[2pt]-14\end{pmatrix},
g_{0}^{T}A g_{0}=(-8)(-35)+(-3)(-14)=280+42=322.
Logo
\alpha_{0}=\frac{73}{322}\approx 0,226708.
  • Atualização:
x_{1}=x_{0}-\alpha_{0}g_{0}= \alpha_{0}\begin{pmatrix}8\\[2pt]3\end{pmatrix} =\begin{pmatrix}\dfrac{584}{322}\\[6pt]\dfrac{219}{322}\end{pmatrix} \approx\begin{pmatrix}1,813665\\[2pt]0,680124\end{pmatrix}.
Observação amigável: já na primeira iteração damos um salto na direção do minimizador; repare que x_{1} está bem mais perto do ponto ótimo que x_{0}.]

Passo 4

Iteração 1 → cálculo de \;x_{2} a partir de \;x_{1}.
  • Gradiente em x_{1}:
g_{1}=A x_{1}-b.
Usando os valores exatos que obtivemos para x_{1} (frações) é fácil ver que
g_{1}=\begin{pmatrix}-\dfrac{21}{322}\\[6pt]\dfrac{56}{322}\end{pmatrix} \approx\begin{pmatrix}-0,065217\\[2pt]0,173913\end{pmatrix}.
  • Cálculo de \alpha_{1}:
\alpha_{1}=\frac{g_{1}^{T}g_{1}}{g_{1}^{T}A g_{1}}.
Fazendo as multiplicações (os termos cancelam convenientemente porque usamos forma matricial) obtemos, exata e simplificada,
\alpha_{1}=\frac{3577}{5684}\approx 0,629343.
  • Atualização:
x_{2}=x_{1}-\alpha_{1}g_{1}.
Numéricamente,
x_{2}\approx\begin{pmatrix}1,813665\\[2pt]0,680124\end{pmatrix} - 0,629343\begin{pmatrix}-0,065217\\[2pt]0,173913\end{pmatrix} \approx\begin{pmatrix}1,854675\\[2pt]0,570773\end{pmatrix}.
Comentário didático: observe a propriedade da busca exata em quadráticas — os gradientes sucessivos ficam ortogonais entre si (propriedade útil para análise), e o método frequentemente aproxima muito rápido o ponto ótimo, embora não garanta convergência em número finito de passos como o método dos conjugados (este último teria convergência em no máximo n passos para matrizes n\times n).]

Passo 5

Iteração 2 → cálculo de \;x_{3} a partir de \;x_{2}.
  • Gradiente em x_{2}:
g_{2}=A x_{2}-b\approx\begin{pmatrix}-0,010527\\[2pt]-0,003779\end{pmatrix}.
(estes valores são obtidos multiplicando A por x_{2} e subtraindo b; mostrei o procedimento antes — aqui apresento o resultado numérico preciso suficiente para a prova.)
  • Cálculo de \alpha_{2}:
\alpha_{2}=\frac{g_{2}^{T}g_{2}}{g_{2}^{T}A g_{2}} \approx 0,2267\quad(\text{aprox.}).
  • Atualização:
x_{3}=x_{2}-\alpha_{2}g_{2} \approx\begin{pmatrix}1,854675\\[2pt]0,570773\end{pmatrix} - 0,2267\begin{pmatrix}-0,010527\\[2pt]-0,003779\end{pmatrix} \approx\begin{pmatrix}1,857062\\[2pt]0,571629\end{pmatrix}.
Didaticamente: já estamos muito próximos do minimizador real; a cada iteração o resíduo (gradiente) reduz bastante.]

Passo 6

Iteração 3 → cálculo de \;x_{4} a partir de \;x_{3}.
  • Gradiente em x_{3}:
g_{3}=A x_{3}-b\approx\begin{pmatrix}-0,000123\\[2pt]0,000320\end{pmatrix}.
  • Cálculo de \alpha_{3}:
\alpha_{3}=\frac{g_{3}^{T}g_{3}}{g_{3}^{T}A g_{3}}\approx 0,6296\quad(\text{aprox.}).
  • Atualização:
x_{4}=x_{3}-\alpha_{3}g_{3} \approx\begin{pmatrix}1,857062\\[2pt]0,571629\end{pmatrix} - 0,6296\begin{pmatrix}-0,000123\\[2pt]0,000320\end{pmatrix} \approx\begin{pmatrix}1,857139\\[2pt]0,571427\end{pmatrix}.
Comentário de encorajamento: vê como o procedimento é mecânico? Gradiente → passo ótimo → atualizar. Com prática dá para fazer a conta de cabeça (ou com poucas operações) em quadráticas simples na prova.]

Passo 7

Comparação com a solução exata (para você ver onde estamos chegando):
  • Resolver Ax=b\) dá o minimizador exato (pelo fato de \(\nabla f(x)=Ax-b\), o mínimo ocorre em \(Ax=b\)): \[\begin{cases} 4x+y=8,\\[4pt] x+2y=3, \end{cases} \quad\Rightarrow\quad x^{*}=\begin{pmatrix}\dfrac{13}{7}\\[6pt]\dfrac{4}{7}\end{pmatrix} \approx\begin{pmatrix}1,857142\\[2pt]0,571429\end{pmatrix}.
  • Compare os iterados: já em (x_{4}] estamos praticamente à frente do valor exato até as casas decimais mostradas. Isso mostra que a busca linear exata no gradiente é muito eficaz para quadráticas.]

Resposta

x_{0}=(0,0)^{T}
x_{1}\approx\begin{pmatrix}1,813665\\[2pt]0,680124\end{pmatrix}
x_{2}\approx\begin{pmatrix}1,854675\\[2pt]0,570773\end{pmatrix}
x_{3}\approx\begin{pmatrix}1,857062\\[2pt]0,571629\end{pmatrix}
x_{4}\approx\begin{pmatrix}1,857139\\[2pt]0,571427\end{pmatrix}]

Exercícios relacionados