Extremos

Sumário

19.1 INTRODUÇÃO
19.2 AULA
19.3 EXEMPLOS
EXERCÍCIOS

19.1 INTRODUÇÃO

19.1.1 Explorando a Aprendizagem como um Processo de Otimização

Aprendizagem é um processo de otimização com o objetivo de aumentar conhecimento, habilidades e poder criativo. Isso se aplica tanto à educação quanto ao aprendizado de máquina. Para acompanhar o processo de aprendizagem, precisamos de uma função que meça o progresso. Uma métrica antiquada é o GPA, que calcula a média de algumas notas em um sistema educacional, ou os escores de QI medidos por meio de testes. Outro exemplo de métrica em um ambiente de pesquisa é uma pontuação de rede social, como o número de citações ou o índice h. Para um carro dirigindo autonomamente, poderia ser $f (x) = 100 / (1 + N (x))$ onde $N (x)$ é o número de acidentes produzidos usando a configuração de parâmetros $x$ em um período fixo.

**Figura 1.** A imagem Klondike de David Perkins ilustra a busca por soluções em uma paisagem de dimensão superior definida por uma função altura $f$ . O cálculo sugere seguir o gradiente $\nabla f$ , pois isso leva a **máximos locais**. Para encontrar máximos globais (que podem ser ideias inovadoras), precisamos pesquisar mais e fazer uma lista de todos os máximos. O processo recebeu o nome da região de Klondike, no Canadá, que se tornou famosa durante a Corrida do Ouro.

19.1.2 A IA Conquistará Todos os Domínios?

Uma vez que a estrutura e a função $f$ estão fixadas, a questão é como aumentar $f$ de forma mais eficaz. Essa imagem simplista é bastante eficaz tanto para a inteligência humana quanto para a inteligência artificial. Para muitas funções que foram consideradas (vencer em jogos de xadrez, poder computacional, retenção de dados, detecção de características, dirigir carros ou pilotar aviões), as máquinas progrediram rapidamente. Quase ninguém duvida seriamente que os humanos eventualmente perderão a batalha por qualquer função $f$ que possa ser considerada. Ainda existem domínios onde as máquinas não assumiram o controle. Exemplos são a arte ou a redação de artigos científicos.¹

19.1.3 A Vantagem do Aprendizado de Máquina na Otimização Baseada em Gradiente

Uma vez que uma máquina conhece a função $f$ , ela pode determinar confortavelmente, a partir de uma posição $x$ , em qual direção mudar para aumentar $f$ mais rapidamente. A direção do aumento mais rápido é a direção do gradiente $\nabla f$ de $f$ . No cálculo, analisamos situações em que a posição consiste em apenas algumas variáveis. O cálculo de uma variável trata da situação com uma variável. Aqui, analisamos a situação com $n$ variáveis, mas trabalharemos principalmente com $2$ variáveis, pois isso já fornece a ideia principal. O princípio é que atingimos um ótimo onde nenhuma mudança pode mais aumentar a função $f$ . Isso significa matematicamente que a derivada $d f$ de $f$ é zero. Chamamos tais pontos de "pontos críticos".

19.1.4 Usando Gradientes para Encontrar a Direção de Melhoria

Vamos primeiro analisar a taxa de variação de uma função ao longo de uma direção $v$ . Considere uma curva $r (t) = x + t v$ onde $v$ é um vetor unitário. Pela regra da cadeia, a taxa de variação em $x$ é dada por f(r(t))=\nabla f(r(t)) \cdot r^{\prime}(0)=\nabla f(x) \cdot v. Sabemos, para o produto escalar, que isso é igual a $| \nabla f (x) | | v | \cos (α) = | \nabla f (x) | \cos (α) .$ Isso é maximizado para $\cos (α) = 1$ , o que significa que $v$ aponta na mesma direção que $\nabla f$ . Portanto, o gradiente aponta na direção do aumento máximo. É importante lembrar disso. Se você estiver em uma paisagem dada pela altura $f (x)$ , deverá seguir a direção de $\nabla f (x) / | \nabla f (x) |$ para aumentar ao máximo. É claro que isso não faz sentido se $\nabla f (x) = 0$ , mas essa é a situação em que você está em um máximo e não pode mais aumentar $f$ .

19.2 AULA

19.2.1 Encontrando Ótimos com Gradientes

Todas as funções são consideradas aqui como sendo de classe $C^{2}$ , o que significa que são duas vezes continuamente diferenciáveis. Tudo começa com uma observação que remonta a Pierre de Fermat:

Teorema 1. Se $x_{0}$ é um máximo de $f : ℝ^{m} \to ℝ$ , então $\nabla f (x_{0}) = 0$ .

Prova. Provamos isso por contradição. Suponha que $\nabla f (x_{0}) \neq 0$ , defina o vetor $v =$ $\nabla f (x_{0})$ e considere $g (t) = f (x_{0} + t v)$ , que é uma função de uma variável. Pela regra da cadeia, ela satisfaz g^{\prime}(0)=\nabla f(x_{0}+0 v) \cdot v=|\nabla f|^{2}>0. Isso significa que $f (x_{0} + t v) > 0$ para $t > 0$ pequeno. O ponto $x_{0}$ não pode ter sido máximo. Isso é uma contradição. ◻

19.2.2 Revelando Pontos Críticos

Um ponto $x$ com $\nabla f (x) = 0$ é chamado de ponto crítico de $f$ . Pela fórmula de Taylor, temos em um ponto crítico $x_{0}$ a aproximação quadrática $Q (x) = f (x_{0}) + (x - x_{0})^{T} H (x_{0}) (x - x_{0}) / 2,$ onde $H (x_{0})$ é a matriz Hessiana $H (x_{0}) = [\begin{array}{llll} f_{x_{1} x_{1}} & f_{x_{1} x_{2}} & \dots & f_{x_{1} x_{m}} \\ f_{x_{2} x_{1}} & f_{x_{2} x_{2}} & \dots & f_{x_{2} x_{m}} \\ \dots & \dots & \dots & \dots \\ f_{x_{m} x_{1}} & f_{x_{m} x_{2}} & \dots & f_{x_{m} x_{m}} \end{array}] .$

19.2.3 O Teste da Segunda Derivada Entra em Cena

Assim como em uma dimensão, ter um ponto crítico não garante que o ponto seja um máximo ou mínimo local. O teste da segunda derivada no cálculo de uma variável garante que, se f^{\prime}(x_{0})=0, f^{\prime \prime}(x_{0})>0, temos um mínimo local e, se f^{\prime}(x_{0})=0, f^{\prime \prime}(x_{0})<0, temos um máximo local. Se f^{\prime \prime}(x_{0})=0, não podemos afirmar nada sem analisar derivadas de ordem superior.

19.2.4 Matrizes Definidas Positivas e Negativas

Uma matriz $A$ é chamada de definida positiva se $v \cdot A v > 0$ para todos os vetores $v \neq 0$ . É chamada de definida negativa se $v \cdot A v < 0$ para todos os vetores $v \neq 0$ . Uma matriz diagonal com entradas diagonais positivas é definida positiva. Nas afirmações a seguir, assumimos que $x_{0}$ é um ponto crítico.

19.2.5 Revelando o Papel das Hessianas Definidas Positivas

Dizemos que $x_{0}$ é um máximo local de $f$ se existe $r > 0$ tal que $f (x) \leq f (x_{0})$ para todo $| x - x_{0} | < r$ . Dizemos que é um mínimo local de $f$ se $f (x) \geq f (x_{0})$ para todo $| x - x_{0} | < r$ . Como podemos verificar se um ponto é um máximo ou mínimo local?

Teorema 2. Suponha que $\nabla f (x_{0}) = 0$ . Se $H (x_{0})$ é definida positiva, então $x_{0}$ é um mínimo local. Se $H (x_{0})$ é definida negativa, então $x_{0}$ é um máximo local.

Prova. Como $\nabla f (x_{0}) = 0$ , a aproximação quadrática em $x_{0}$ é $Q (x) = f (x_{0}) + H (x_{0}) v \cdot v / 2 > f (x_{0})$ para $v = x - x_{0}$ pequeno e não nulo, e Hessiana $H$ . A afirmação análoga para o mínimo pode ser deduzida substituindo $f$ por $- f$ . ◻

19.2.6 Classificando Extremos em Duas Dimensões

Vamos analisar o caso em que $f (x, y)$ é uma função de duas variáveis tal que $f_{x} (x_{0}, y_{0}) = 0$ e $g_{x} (x_{0}, y_{0}) = 0$ . A matriz Hessiana é

$H (x_{0}, y_{0}) = [\begin{array}{ll} f_{x x} & f_{x y} \\ f_{y x} & f_{y y} \end{array}]$

Neste caso bidimensional, podemos classificar os pontos críticos se o determinante $D = \det (H) = f_{x x} f_{y y} - f_{x y}^{2}$ de $H$ for diferente de zero. O número $D$ também é chamado de discriminante em um ponto crítico.

**Figura 2.** $f = x^{2} + y^{2}$ fornece um mínimo, $f = - x^{2} - y^{2}$ um máximo e $f = x^{2} - y^{2}$ uma sela. O caso $f = x^{2} y - y x^{2}$ não é Morse.

19.2.7 Funções de Morse e o Teste da Segunda Derivada

Dizemos que $(x_{0}, y_{0})$ é um ponto de Morse se $(x_{0}, y_{0})$ é um ponto crítico e o determinante é diferente de zero. Uma função de classe $C^{2}$ é uma função de Morse se todo ponto crítico é de Morse. Exemplos de funções de Morse são $f (x, y) = x^{2} + y^{2}$ , $f (x, y) = - x^{2} - y^{2}$ e $f (x, y) = x^{2} - y^{2}$ . O último caso é chamado de sela hiperbólica. Em geral, um ponto crítico é uma sela hiperbólica se $D \neq 0$ e se não é nem máximo nem mínimo. Aqui está o teste da segunda derivada em dimensão $2$ :

Teorema 3. Suponha que $f \in C^{2}$ tenha um ponto crítico $(x_{0}, y_{0})$ com $D \neq 0$ .

Se $D > 0$ e $f_{x x} > 0$ , então $(x_{0}, y_{0})$ é um mínimo local.
Se $D > 0$ e $f_{x x} < 0$ , então $(x_{0}, y_{0})$ é um máximo local.
Se $D < 0$ , então $(x_{0}, y_{0})$ é uma sela hiperbólica.

Prova. Após a translação $(x, y) \to (x - x_{0}, y - y_{0})$ e substituindo $f$ por $f -$ $f (x_{0}, y_{0})$ , temos $(x_{0}, y_{0}) = (0, 0)$ e $f (0, 0) = 0$ . No ponto crítico, a aproximação quadrática agora é $Q (x, y) = a x^{2} + 2 b x y + c y^{2} .$ Isso pode ser reescrito como $a (x + \frac{b}{a} y)^{2} + (c - \frac{b^{2}}{a}) y^{2} = a (A^{2} + D B^{2})$ com $A = (x + \frac{b}{a} y), B = b^{2} / a^{2}$ e discriminante $D$ . Se $a = f_{x x} > 0$ e $D > 0$ , então $c - b^{2} / a > 0$ e a função assume valores positivos para todo $(x, y) \neq (0, 0)$ . O ponto $(0, 0)$ é então um mínimo. Se $a = f_{x x} < 0$ e $D > 0$ , então $c - b^{2} / a < 0$ e a função assume valores negativos para todo $(x, y) \neq (0, 0)$ e o ponto $(x, y)$ é um máximo local. Se $D < 0$ , então $f$ assume tanto valores negativos quanto positivos perto de $(0, 0)$ . ◻

19.2.8 Da Hessiana à Curvatura de Gauss

Pode-se perguntar por que $f_{x x}$ é escolhido e não $f_{y y}$ . Não importa, porque se $D > 0$ , então ambos $f_{x x}$ e $f_{y y}$ precisam ser diferentes de zero e ter o mesmo sinal. Em vez de $f_{x x}$ , também se poderia escolher o mais natural traço $tr (H)$ . Ele é invariante sob mudanças de coordenadas, assim como o determinante $D$ . O discriminante $D$ também é a curvatura de Gauss da superfície no ponto.

19.2.9 O Lema de Morse

Em dimensões mais altas, a situação é descrita pelo lema de Morse. Ele diz que perto de um ponto crítico há uma mudança de coordenadas $ϕ$ tal que $g (x) = f (ϕ (x))$ é uma função quadrática $f (x) = B (x - x_{0}) \cdot (x - x_{0})$ onde $B$ é diagonal com entradas $+ 1$ ou $- 1$ . O ponto crítico pode então receber um índice de Morse, o número de entradas $- 1$ em $B$ . O lema de Morse é na verdade um teorema (teoremas são mais importantes que lemas=teoremas auxiliares)

Teorema 4. Perto de um ponto crítico de Morse $x_{0}$ de uma função $C^{2}$ $f$ , existe uma mudança de coordenadas $ϕ : ℝ^{m} \to ℝ^{m}$ tal que $g (x) = f (ϕ (x)) - f (x_{0})$ é $g (x) = - x_{1}^{2} - \dots - x_{k}^{2} + x_{k + 1}^{2} + \dots + x_{m}^{2} .$

Prova. Usamos indução em relação a $m$ .

Base da indução: Para $m = 1$ , o resultado diz que para um ponto crítico de Morse, a função se parece com $y = x^{2}$ ou $y = - x^{2}$ . Primeiro mostre que se f(0)=f^{\prime}(0)=0, f^{\prime \prime}(0) \neq 0, então $f (x) = x^{2} h (x)$ ou $f (x) = - x^{2} h (x)$ para alguma função $C^{2}$ positiva $h$ . Prova. Por uma mudança linear de coordenadas assumimos $x_{0} = 0$ e $f (0) = 0$ . Existe então $g (x)$ tal que $f (x) = x g (x)$ : é $g (x) = f (x) / x$ para $x \neq 0$ e no limite $x \to 0$ o valor de $lim_{x \to 0} (f (x) -$ f(0)) / x=f^{\prime}(0). Pela regra do produto, f^{\prime}(x)=g(x)+x g^{\prime}(x) com $g (0) = 0$ . Como f^{\prime}(0)=g(0)=0 podemos definir $f (x) / x^{2}$ para $x \neq 0$ e tomar o limite $x \to 0$ , porque aplicando Hôpital duas vezes, o limite é f^{\prime \prime}(0). A mudança de coordenadas é agora dada por uma função $y = ϕ (x)$ satisfazendo $g (x, y) = y \sqrt{h (y)} = x$ . A diferenciação implícita dá $g_{y} (0, 0) = \sqrt{h (y)} \neq 0$ de modo que pelo teorema da função implícita $y (x)$ existe.
Passo de indução $𝒎 \to 𝒎 + 1$ : primeiro notamos que Taylor para $C^{2}$ com termo restante implica que $f (x_{1}, \dots, x_{n}) = \sum_{i, j} x_{i} x_{j} h_{i j} (x_{1}, \dots, x_{n})$ com algumas funções contínuas $h_{i j}$ . Além disso, o valor da função $h_{i j} (0) = f_{x_{i} x_{j}} (0) = H_{i j} (0)$ são as coordenadas da Hessiana. Aplique primeiro uma rotação de modo que $h_{11} \neq 0$ . Agora olhe para $x_{1}$ e mantenha as outras coordenadas constantes. Como em (i), encontre uma mudança de coordenadas $ϕ$ tal que $f (ϕ (x)) = \pm x_{1}^{2} + g (x_{2}, \dots, x_{m})$ , onde $g$ herda as propriedades de mas é de uma dimensão a menos. Por hipótese de indução, existe uma segunda mudança de coordenadas tal que $g (ψ (x)) = x_{2}^{2} - \dots - x_{l}^{2} + x_{l + 1}^{2} + \dots + x_{m}^{2} .$ Combinando $ϕ$ e $ψ$ produz a forma normal de Morse.

◻

19.3 EXEMPLOS

Exemplo 1. P: Classifique os pontos críticos de $f (x, y) = x^{3} - 3 x - y^{3} - 3 y$ .
R: Como $\nabla f (x, y) = {[3 x^{2} - 3, - 3 y^{2} + 3]}^{T},$ os pontos críticos são $(1, 1)$ , $(- 1, 1)$ , $(1, - 1)$ e $(- 1, - 1)$ . Calculamos $H (x, y) = [\begin{array}{cc} 2 x & 0 \\ 0 & - 2 y \end{array}] .$ Para $(1, 1)$ e $(- 1, - 1)$ temos $D = - 4$ e portanto pontos de sela. Para $(- 1, 1)$ , temos $D = 4$ , $f_{x x} = - 2$ , um máximo local. Para $(1, - 1)$ onde $D = 4$ , $f_{x x} = 2$ temos um mínimo local.

EXERCÍCIOS

Exercício 1.

Classifique os pontos críticos da função $f (x, y) = x^{2} + y^{3} - x y .$ (Máximos, mínimos ou pontos de sela).
Agora faça o mesmo para $f (x, y, z) = x^{2} + y^{3} - x y + z^{2}$ e encontre o índice de Morse em cada ponto crítico.

Exercício 2. Encontre todos os pontos críticos da função $3$ D área $51$ $f (x, y, z) = x^{51} - 51 x + y^{51} - 51 y + z^{51} - 51 z .$ Calcule a Hessiana $H = d^{2} f$ em cada ponto crítico e determine os máximos (todos os autovalores são negativos) e mínimos (todos os autovalores são positivos).
P.S. Área $51$ é algo antigo. Mas a Área $3$ D $51$ ainda é altamente classificada e há rumores de que fica perto do lado escuro da lua.

Exercício 3. Onde na superfície parametrizada $r (u, v) = [u^{2}, v^{3}, u v]$ a temperatura $T (x, y, z) = 12 x + y - 12 z$ é mínima. Classifique todos os pontos críticos da função $f (u, v) = T (r (u, v))$ . [Se você encontrou a função $f (u, v)$ , pode substituir $u$ , $v$ novamente por $x$ , $y$ se preferir trabalhar com uma função $f (x, y)$ .]

Exercício 4. Encontre todos os pontos críticos da função $f (x, y, z) = (x - 1)^{2} - y^{2} + x z^{2} .$ Em cada um dos casos, encontre a matriz Hessiana. Aqui também calcule os autovalores. Estes são números $λ$ tais que $H v = λ v$ para algum vetor não nulo. Pode-se encontrá-los procurando as raízes do polinômio característico $χ_{H} (λ) = \det (L - λ)$ . Você pode calculá-los em um computador. Encontre em cada caso os autovalores.

Exercício 5.

Encontre uma função $f (x, y)$ com $3$ máximos e $3$ pontos de sela e um mínimo.
Você vê abaixo um mapa de contorno de uma função de duas variáveis. Quantos pontos críticos existem? A função é uma função de Morse?

Pode haver resistência: os humanos podem decidir não citar descobertas científicas feitas por máquinas. Por outro lado, quem não gostaria de aprender uma "teoria de tudo" mesmo que seja descoberta por uma máquina?↩︎