Extremo local
É melhor que os pontos suficientemente próximos, mas outra região pode conter um resultado superior.
f(x*) ≤ f(x), para x próximo de x*FUNDAMENTOS DE OTIMIZAÇÃO · SUBTÓPICO 04
O melhor ponto pode ser local ou global.
Uma paisagem pode conter vários picos e vales. A otimização precisa distinguir uma solução melhor que suas vizinhas daquela que é a melhor em todo o espaço de busca.
PAISAGEM MULTIMODALf(x)
comparação na vizinhançacomparação em todo o domínio
01 · ESCALA DA COMPARAÇÃO
“Melhor” sempre precisa indicar em relação a quê.
Os termos local e global descrevem o conjunto usado na comparação.
ampliar
a comparação→
a comparação→
Extremo global
É melhor que todos os candidatos permitidos no espaço considerado.
f(x*) ≤ f(x), para todo x ∈ S02 · INCLINAÇÃO E PONTOS CRÍTICOS
A derivada informa para qual lado a função cresce.
Em funções suaves de uma variável, a inclinação ajuda a localizar candidatos a máximos e mínimos.
Função decrescente
Aumentar x reduz o valor de f(x).
Ponto crítico
A reta tangente é horizontal. O ponto precisa ser classificado.
Função crescente
Aumentar x eleva o valor de f(x).
∪
Mínimo localA curva possui concavidade voltada para cima.
∩
Máximo localA curva possui concavidade voltada para baixo.
?
Teste inconclusivoOutras análises ou derivadas de ordem maior podem ser necessárias.
03 · INTERIOR E FRONTEIRA
O melhor valor também pode estar no limite do domínio.
INTERIOR
Pontos críticos
f′(x) = 0Procure pontos estacionários dentro do intervalo.
FRONTEIRA
Extremos do intervalo
x = a e x = bAvalie os limites definidos pelo domínio ou pelas restrições.
COMPARAÇÃO
Valores da função
f(a), f(x₁*), …, f(b)O menor e o maior valor identificam os extremos globais.
ab
Em um intervalo fechado, compare pontos críticos e extremidades.
04 · LABORATÓRIO INTERATIVO
Desça para um vale ou suba para um pico.
Escolha a direção da busca e observe como a inclinação local conduz o candidato pela paisagem.
Paisagem e trajetória
Os rastros mostram os pontos visitados. O movimento usa apenas a inclinação atual.
mínimo globaloutros extremosposição atualtrajetória
Atualização do próximo passo:
x novo = −0,80 − 0,08(1,79) = −0,9405 · POR QUE A BUSCA GLOBAL É DIFÍCIL?
Informação local não revela toda a paisagem.
Múltiplos vales
O resultado pode depender fortemente do ponto em que a busca começa.
Platôs
Regiões quase planas oferecem pouca indicação sobre a direção útil.
Ruído
Pequenas oscilações podem criar falsos extremos e avaliações instáveis.
Alta dimensão
O número de direções cresce e impede uma inspeção completa do espaço.
BUSCA LOCALexplora bem uma região
+DIVERSIDADEvisita regiões diferentes
=METAHEURÍSTICAequilibra intensificação e exploração
06 · NO CÓDIGO
O sinal escolhe entre descer e subir.
function derivada(x) {
return 0.72 * x ** 3 - 2.8 * x + 0.22;
}
function passo(x, taxa, modo) {
const inclinacao = derivada(x);
const direcao = modo === 'min' ? -1 : 1;
return x + direcao * taxa * inclinacao;
}
// mínimo: x ← x − ηf′(x)
// máximo: x ← x + ηf′(x)Medir a inclinação
A derivada informa a variação local da função.
Escolher o sinal
Subtraímos para descer e somamos para subir.
Controlar o passo
A taxa η define o tamanho de cada deslocamento.
Parar
A busca termina quando a inclinação ou a mudança fica pequena.
PRÓXIMO SUBTÓPICO
Otimização contínua e combinatória.
O tipo das variáveis muda a geometria do espaço e a forma como novas soluções são construídas.
Continuar estudo →