Funções objetivo gradientes e mínimos

O que um otimizador procura

Um problema de otimização tem um número a tornar pequeno, o objetivo $f(\mathbf w)$ , e variáveis $\mathbf w$ que podemos mudar. O objetivo pode ser uma perda de mínimos quadrados, a variância $\mathbf w^{T}\Sigma\mathbf w$ de uma carteira ou a diferença entre preços do modelo e do mercado numa calibração. Tornar algo grande é o mesmo problema com o sinal trocado, pois maximizar $f$ é minimizar $-f$ .

\nabla f(\mathbf w)=\Big(\frac{\partial f}{\partial w_1},\dots,\frac{\partial f}{\partial w_n}\Big),\qquad H_{ij}=\frac{\partial^{2} f}{\partial w_i\,\partial w_j}

(1)

O gradiente aponta na direção em que $f$ cresce mais depressa, então $-\nabla f$ é a direção de descida mais íngreme. Num mínimo o gradiente é zero, a condição de primeira ordem. Gradiente zero sozinho não basta, porque máximos e pontos de sela também o têm. A hessiana $H$ os distingue: se $H$ é definida positiva (todos os autovalores positivos) o ponto é mínimo local, se é definida negativa é máximo, e se tem autovalores de ambos os sinais o ponto é uma sela.

Um exemplo com duas variáveisTome

f(x,y)=(x-1)^2+2(y+2)^2

. Então

\nabla f=(2(x-1),\,4(y+2))

. No ponto

(3,0)

o gradiente é

(4,8)

, então andar no sentido oposto reduz

f

. O gradiente só se anula em

(1,-2)

. Ali

H=\mathrm{diag}(2,4)

tem autovalores positivos:

(1,-2)

é o mínimo e

f=0

nele.

Ponto estacionário: $\nabla f=0$ . Necessário para um mínimo, não suficiente.
Classificação: $H$ definida positiva dá mínimo local, $H$ indefinida uma sela.
Em uma variável: $f'(x)=0$ com $f''(x)>0$ é um mínimo.

Confira seu gradiente numericamenteA maioria dos bugs de otimização são gradientes errados. Compare sua fórmula com a diferença central

\big(f(x+h)-f(x-h)\big)/(2h)

para um

h

pequeno como

10^{-5}

: as duas devem coincidir em vários dígitos. Faça isso uma vez para cada objetivo novo antes de confiar num solver que o use.

Lab: o que é avaliado

Uma derivada parcial15 pts
O comprimento do gradiente15 pts
O mínimo de um cúbico15 pts
Classificar um ponto estacionário15 pts
Associar o vocabulário15 pts
Achar um mínimo à mão10 pts
Por que andar contra o gradiente15 pts

O que um otimizador procura

\nabla f(\mathbf w)=\Big(\frac{\partial f}{\partial w_1},\dots,\frac{\partial f}{\partial w_n}\Big),\qquad H_{ij}=\frac{\partial^{2} f}{\partial w_i\,\partial w_j}

(1)

Um exemplo com duas variáveisTome

f(x,y)=(x-1)^2+2(y+2)^2

. Então

\nabla f=(2(x-1),\,4(y+2))

. No ponto

(3,0)

o gradiente é

(4,8)

, então andar no sentido oposto reduz

f

. O gradiente só se anula em

(1,-2)

. Ali

H=\mathrm{diag}(2,4)

tem autovalores positivos:

(1,-2)

é o mínimo e

f=0

nele.

Ponto estacionário: $\nabla f=0$ . Necessário para um mínimo, não suficiente.
Classificação: $H$ definida positiva dá mínimo local, $H$ indefinida uma sela.
Em uma variável: $f'(x)=0$ com $f''(x)>0$ é um mínimo.

Confira seu gradiente numericamenteA maioria dos bugs de otimização são gradientes errados. Compare sua fórmula com a diferença central

\big(f(x+h)-f(x-h)\big)/(2h)

para um

h

pequeno como

10^{-5}

: as duas devem coincidir em vários dígitos. Faça isso uma vez para cada objetivo novo antes de confiar num solver que o use.

Lab: o que é avaliado

Uma derivada parcial15 pts
O comprimento do gradiente15 pts
O mínimo de um cúbico15 pts
Classificar um ponto estacionário15 pts
Associar o vocabulário15 pts
Achar um mínimo à mão10 pts
Por que andar contra o gradiente15 pts

Funções objetivo gradientes e mínimos

O que um otimizador procura

Lab: o que é avaliado

Entre para executar o seu código.

Funções objetivo gradientes e mínimos

O que um otimizador procura

Lab: o que é avaliado

Entre para executar o seu código.