Otimização Não Restrita

O problema da otimização não restrita

Dada \(f:\mathbb{R}^n\to\mathbb{R}\) diferenciável, busca-se

\[x^{*} = \arg\min_{x\in\mathbb{R}^n} f(x)\]

sem restrições sobre \(x\) — diferente de zeros de funções (\(f(x)=0\)), aqui o alvo é um ponto de mínimo.

Condições de otimalidade

Para \(x^{*}\) ser um mínimo local de \(f\in C^2\):

\[\text{1ª ordem (necessária):}\quad \nabla f(x^{*}) = 0 \qquad \text{(ponto estacionário)}\]

\[\text{2ª ordem (suficiente):}\quad \nabla^2 f(x^{*}) \succ 0 \quad \text{(Hessiana positiva definida)}\]

Em 1D: \(f'(x^{*})=0\) e \(f''(x^{*})>0\).

Direção de máxima descida

Pela expansão de Taylor de 1ª ordem em torno de \(x_k\), para um passo \(d\) de norma fixa:

\[f(x_k + d) \approx f(x_k) + \nabla f(x_k)^\top d\]

Esse produto interno é minimizado (maior decréscimo) quando \(d\) aponta na direção oposta ao gradiente:

\[d_k = -\nabla f(x_k)\]

Método do gradiente (steepest descent)

Sequência de iterados que caminham na direção de máxima descida:

\[x_{k+1} = x_k - \alpha_k\, \nabla f(x_k)\]

• \(\alpha_k > 0\): tamanho do passo (learning rate);
• Repete-se até \(\|\nabla f(x_k)\|\) ser suficientemente pequeno;
• Converge para um ponto estacionário — mínimo local se \(f\) satisfaz as condições de 2ª ordem, mínimo global se \(f\) é convexa.

Gradiente descendente — implementação em Python

import numpy as np

def gradiente_descendente(grad_f, x0, alpha=0.1, tol=1e-6, nmax=1000):
    x = np.atleast_1d(np.asarray(x0, dtype=float))
    for n in range(1, nmax + 1):
        g = grad_f(x)
        if np.linalg.norm(g) < tol:
            return x, n
        x = x - alpha * g
    raise RuntimeError(f"não convergiu em {nmax} iterações")

Equivalente pronto no SciPy (Nelder-Mead, BFGS, CG, … — não exige implementar o laço manualmente):

from scipy.optimize import minimize

res = minimize(f, x0=x0, jac=grad_f, method='BFGS')

Exemplo — mínimo de uma parábola

\[f(x) = (x-3)^2 + 1, \qquad f'(x) = 2(x-3)\]

Mínimo exato: \(x^{*}=3\), \(f(x^{*})=1\). Partindo de \(x_0=0\), com \(\alpha=0{,}2\):

f  = lambda x: (x - 3)**2 + 1
df = lambda x: 2 * (x - 3)

x, n = gradiente_descendente(df, x0=0.0, alpha=0.2, tol=1e-6)
print(x, n)          # 3.0 (aprox.), poucas iterações

O erro \(|x_k - x^{*}|\) decai geometricamente: cada passo reduz a distância ao mínimo por um fator constante \(|1-2\alpha|\).

Passo ótimo para funções quadráticas

Para \(f(x) = \tfrac{1}{2}x^\top A x - b^\top x\) (\(A\) simétrica positiva definida), o passo exato que minimiza \(f\) ao longo da direção \(-\nabla f(x_k)\) tem fórmula fechada:

\[\alpha_k = \frac{r_k^\top r_k}{r_k^\top A\, r_k}, \qquad r_k = -\nabla f(x_k) = b - Ax_k\]

Para a parábola \(f(x)=(x-3)^2+1\): \(A=2\) (escalar), e \(\alpha_k = 1/2\) é o passo ótimo — converge em uma única iteração.

Múltiplas variáveis — paraboloide

\[f(x,y) = x^2 + 10y^2, \qquad \nabla f(x,y) = (2x,\ 20y)\]

Mínimo em \((0,0)\). Com \(A = \operatorname{diag}(2,20)\), a razão entre autovalores (\(\kappa = 20/2=10\)) determina o comportamento:

grad = lambda v: np.array([2*v[0], 20*v[1]])
x, n = gradiente_descendente(
    grad, x0=[8.0, 1.0], alpha=0.09, tol=1e-6)
print(x, n)

Taxa de convergência

Para \(f\) quadrática com Hessiana \(A\) de autovalores \(\lambda_{\min}, \lambda_{\max}\) e passo ótimo a cada iteração, o método do gradiente converge linearmente:

\[\|x_{k+1}-x^{*}\| \leq \left(\frac{\kappa-1}{\kappa+1}\right)\|x_k-x^{*}\|, \qquad \kappa = \frac{\lambda_{\max}}{\lambda_{\min}} \text{ (número de condição)}\]

Critérios de parada

Método de Newton para otimização

Usa a curvatura (\(\nabla^2 f\)) além da inclinação, aproximando \(f\) por uma quadrática em cada iterado:

\[x_{k+1} = x_k - \bigl[\nabla^2 f(x_k)\bigr]^{-1} \nabla f(x_k)\]

Em 1D: \(x_{k+1} = x_k - f'(x_k)/f''(x_k)\) — é exatamente o método de Newton para achar o zero de \(f'\).

Gradiente × Newton — resumo

Otimização com SciPy

import numpy as np
from scipy.optimize import minimize

f    = lambda v: v[0]**2 + 10*v[1]**2
grad = lambda v: np.array([2*v[0], 20*v[1]])

res = minimize(f, x0=[8.0, 1.0], jac=grad, method='BFGS')
print(res.x, res.fun, res.nit)   # ~[0,0], ~0, poucas iterações

minimize expõe diversos algoritmos ('Nelder-Mead', 'CG', 'BFGS', 'Newton-CG', …) sob interface única — raramente se implementa o laço manualmente em produção, assim como brentq/newton para zeros de funções.

Síntese da aula

• Otimização não restrita busca \(x^{*}\) com \(\nabla f(x^{*})=0\) e Hessiana positiva (semi)definida.
• Gradiente descendente: passo na direção \(-\nabla f(x_k)\), convergência linear, sensível ao número de condição da Hessiana.
• Newton: usa a Hessiana, convergência quadrática, custo maior por iteração.
• Para a parábola \(f(x)=(x-3)^2+1\), o método do gradiente converge ao mínimo exato \(x^{*}=3\); o passo ótimo leva a convergência em uma única iteração.

📓 Notebook complementar — gradiente descendente na parábola com derivada exata, com derivada aproximada (diferença finita) e via scipy.optimize.minimize.

Exercícios

1. Implemente gradiente_descendente e tabule \(x_k, f'(x_k)\) para \(f(x) = (x+2)^2 - 5\) a partir de \(x_0=4\), com \(\alpha = 0{,}3\).
2. Para a mesma função do Exercício 1, calcule o passo ótimo \(\alpha^{*}\) (fórmula fechada da quadrática) e confirme que a convergência ocorre em uma única iteração.
3. Aplique o gradiente descendente a \(f(x,y) = x^2 + 10y^2\) a partir de \((8,1)\) com \(\alpha = 0{,}09\) e \(\alpha = 0{,}045\); compare o número de iterações até \(\|\nabla f\| < 10^{-6}\).
4. Implemente o método de Newton para \(f(x) = (x-3)^2+1\) a partir de \(x_0=0\) e compare o número de iterações com o gradiente descendente (Exercício do slide “Exemplo — mínimo de uma parábola”).
5. Use scipy.optimize.minimize com method='BFGS' para minimizar \(f(x,y)=(x-1)^2+100(y-x^2)^2\) (função de Rosenbrock) a partir de \((-1,1)\), e compare o número de iterações com uma tentativa (manual) de gradiente descendente de passo fixo.