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):
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
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}.
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}.
(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.)
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.]