INTRODUÇÃO À OTIMIZAÇÃO PARA

ENGENHARIA

Professor: Murilo Reolon Scuzziato

OTIMIZAÇÃO NÃO LINEAR
UNIDIMENSIONAL
OTIMIZAÇÃO UNIDIMENSIONAL

 Em geral, os métodos de otimização

não linear irrestrita multidimensionais
utilizam várias vezes os algoritmos de
busca unidimensional

 Considere o problema min1 𝑓 𝑥 em que f(x) seja uma função

𝑥∈ℝ
não linear em uma única variável com limites [a,b]

 Para encontrar o valor ótimo aplicam-se as condições de

otimalidade
 Isso fornece todos os pontos em que f’(x) = 0, o menor valor de f(x)
para esses pontos é o mínimo global

3
DIFICULDADES PARA ENCONTRAR O MÍN. GLOBAL
f ( x)
f ( x  0)

Mínimo
Global

Primeiro Primeiro
x
Ponto Mínimo
Estacionário Local

 f’(x) = 0 em geral é um sistema não linear

 O mínimo global só é garantido após conhecido todos os mínimos
locais
OTIMIZAÇÃO UNIDIMENSIONAL

 Idealmente: mínimo global de f(x), mas isso pode ser muito

oneroso computacionalmente

 Na prática: o algoritmo unidimensional é parte de um algoritmo de

otimização mais amplo, sendo usado como ferramenta, assim uma
solução aproximada ou ligeiramente melhor que a anterior pode ser
usada

 Solução: realizar uma busca linear inexata que reduza f(x)

adequadamente (para uma tolerância especificada) à um mínimo
custo computacional conhecendo f(x) e os limites da busca: x ∈ [a,
b]
OTIMIZAÇÃO UNIDIMENSIONAL

 A maneira mais simples de se encontrar o seu ótimo é

calculando o valor da função para vários pontos entre a e b e o
menor valor encontrado seria a solução (busca exaustiva)

 Existem vários métodos para encontrar o mínimo de uma

função unidimensional, dentre eles os métodos diretos,
baseados em reduções sucessivas de intervalos (não sendo
necessário sua diferenciabilidade)

 Os métodos diretos (busca dicotômica e da seção áurea) exigem

menos esforço e convergem com maior rapidez (para uma
precisão Δ desejada) que a busca exaustiva

6
ALGORITMOS

 Busca exaustiva
 Métodos diretos
 Métodos baseados em reduções sucessivas de intervalos (usam apenas
o valor da função, não exigem diferenciabilidade)
 Busca dicotômica
 Método da seção áurea
 Métodos por aproximação da função
 Interpolação Quadrática

 Em todos os métodos supõe-se um mínimo local no intervalo de

busca [a,b], caso contrário o mínimo do intervalo é min{f(a),f(b)}
BUSCA EXAUSTIVA

 Versão elementar:
 Calculam-se todos os valores de f(x) no intervalo a ≤ x ≤ b

 Determina-se uma sequência de pontos xk+1 = xk + d

 Armazena-se somente o menor valor de f(x) e x entre as iterações

 O passo usado, d, deve ser pequeno em relação à precisão desejada

 Limitação: pode exigir elevado número de avaliações de f(x) se o

intervalo [a,b] for grande e d for pequeno

9
MÉTODOS BASEADOS EM REDUÇÕES SUCESSIVAS DE
INTERVALOS

 Objetivo: identificar o intervalo de certeza na qual se sabe estar

incluído o ponto de solução ótima

 Estratégia: reduzir iterativamente o intervalo de incerteza a

qualquer nível de precisão (Δ) desejado

 Minimização de uma função univariável f(x) no intervalo a ≤ x ≤ b,

no qual sabe-se que o ponto ótimo x* está incluído

10
BUSCA DICOTÔMICA

 0. Definir I0 = (a,b) como intervalo de incerteza inicial e a

tolerancia Δ
 1. Seja Ik = (xL, xR) o intervalo de incerteza atual (iteração k),
calcule:
 x1= ½ ∙(xR + xL – Δ)
 x2= ½ ∙(xR + xL + Δ)
 2. Atualize os limites do intervalo de incerteza

11
BUSCA DICOTÔMICA

 0. Definir I0 = (a,b) como intervalo de incerteza inicial e a

tolerancia Δ
 1. Seja Ik = (xL, xR) o intervalo de incerteza atual (iteração k),
calcule:
 x1= ½ ∙(xR + xL – Δ)
 x2= ½ ∙(xR + xL + Δ)
 2. Atualize os limites do intervalo de incerteza
 Se f(x1) < f(x2) então xL < x* < x2 → faça xR= x2

f(x2)

f(x1)

a xL x1 x2 xR b
12
BUSCA DICOTÔMICA

 0. Definir I0 = (a,b) como intervalo de incerteza inicial e a

tolerancia Δ
 1. Seja Ik = (xL, xR) o intervalo de incerteza atual (iteração k),
calcule:
 x1= ½ ∙(xR + xL – Δ)
 x2= ½ ∙(xR + xL + Δ)
 2. Atualize os limites do intervalo de incerteza
 Se f(x1) < f(x2) então xL < x* < x2 → faça xR= x2
 Se f(x1) > f(x2) então x1 < x* < xR → faça xL= x1

f(x1)
f(x2)

a xL x1 x2 x13
R b
BUSCA DICOTÔMICA

 0. Definir I0 = (a,b) como intervalo de incerteza inicial e a

tolerancia Δ
 1. Seja Ik = (xL, xR) o intervalo de incerteza atual (iteração k),
calcule:
 x1= ½ ∙(xR + xL – Δ)
 x2= ½ ∙(xR + xL + Δ)
 2. Atualize os limites do intervalo de incerteza
 Se f(x1) < f(x2) então xL < x* < x2 → faça xR= x2
 Se f(x1) > f(x2) então x1 < x* < xR → faça xL= x1
 Se f(x1) = f(x2) então x1 < x* < x2 → faça xL= x1 e xR= x2
 3. Teste a convergência:
 Se (xR – xL) ≤ Δ, pare e a solução é dada por x* = (xR + xL)/2, caso
contrário retorne para o passo 1.
14
BUSCA DICOTÔMICA

 0. Definir I0 = (a,b) como intervalo de incerteza inicial e a

tolerancia Δ
 1. Seja Ik = (xL, xR) o intervalo de incerteza atual (iteração k),
calcule:
 x1= ½ ∙(xR + xL – Δ)
 x2= ½ ∙(xR + xL + Δ)
 2. Atualize os limites do intervalo de incerteza
 Se f(x1) < f(x2) então xL < x* < x2 → faça xR= x2
 Se f(x1) > f(x2) então x1 < x* < xR → faça xL= x1
 Se f(x1) = f(x2) então x1 < x* < x2 → faça xL= x1 e xR= x2
 3. Teste a convergência:
 Se (xR – xL) ≤ Δ, pare e a solução é dada por x* = (xR + xL)/2, caso
contrário retorne para o passo 1.
15
SEÇÃO ÁUREA

 Mesmo algoritmo da busca Dicotômica, porém no passo 1:

 x1= xR – ½ ∙ (√5 – 1)∙(xR – xL)
 x2= xL + ½ ∙ (√5 – 1)∙(xR – xL)
 Essa estratégia propõe economizar cálculos reutilizando o valor
descartado na iteração imediatamente sucessiva:
 Se x2 foi descartado na iteração k-1: x1k = x2k-1 ou
 Se x1 foi descartado na iteração k-1: x2k = x1k-1
 Isso resulta na definição das equações para se determinar x1 e
x2 a cada iteração , fazendo menos avaliações de f(x) para
chegar na solução. Em geral, isso torna a convergência mais
rápida por economizar cálculos e por fazer o intervalo de
incerteza diminuir mais rapidamente com as iterações
5−1
 A estrutura dos cálculos da seção áurea garante uma redução ≈
2
0,618 no intervalo de incerteza em iterações consecutivas
16
SEÇÃO ÁUREA

 0. Definir I0 = (a,b) como intervalo de incerteza inicial e a

tolerancia Δ
 1. Seja Ik = (xL, xR) o intervalo de incerteza atual (iteração k),
calcule:
 x1= xR – ½ ∙ (√5 – 1)∙(xR – xL)
 x2= xL + ½ ∙ (√5 – 1)∙(xR – xL)
 2. Atualize os limites do intervalo de incerteza
 Se f(x1) < f(x2) então xL < x* < x2 → faça xR= x2
 Se f(x1) > f(x2) então x1 < x* < xR → faça xL= x1
 Se f(x1) = f(x2) então x1 < x* < x2 → faça xL= x1 e xR= x2
 3. Teste a convergência:
 Se (xR – xL) ≤ Δ, pare e a solução é dada por x* = (xR + xL)/2, caso
contrário retorne para o passo 1.
17
EXEMPLO

−3𝑥 0≤𝑥≤2
 min f 𝑥 = 1
𝑥 − 20 2≤𝑥≤3 2
3

 A solução é x* = 2
-6

 Considerando Δ = 0,1 determinar a solução por meio do método

Dicotômico e Seção Áurea

18
EXEMPLO
Dicotômico Seção Áurea
 Iteração 1  Iteração 1
I0 = (0,3)=(xL,xR) I0 = (0,3)=(xL,xR)
x1 = 0,5*(3+0-0,1)=1,45 x1 = 3-0,618*(3-0)=1,146
f(x1) = - 4,35 f(x1) = - 3,438
x2 = 0,5*(3+0+0,1)=1,55 x2 = 0+0,618*(3-0)=1,854
f(x2) = - 4,65 f(x2) = - 5,562
f(x1) > f(x2) → xL = 1,45, I1=(1,45;3) f(x1) > f(x2) → xL = 1,146, I1=(1,146;3)
 Iteração 2  Iteração 2
I1 = (1,45;3)=(xL,xR) I1 = (1,146;3)=(xL,xR)
x1 = 0,5*(3+1,45-0,1)=2,175 x1 = x2 da iteração anterior =1,854
f(x1) = - 5,942 f(x1) = - 5,562
x2 = 0,5*(3+1,45+0,1)=2,275 x2 = 1,146+0,618*(3-1,146)=2,292
f(x2) = - 5,908 f(x2) = - 5,903
f(x1) < f(x2) → xR = 2,275, I2=(1,45;2,275) f(x1) > f(x2) → xL = 1,854, I2=(1,854;3)
...

...
19
EXEMPLO
xL xR x1 x2 f(x1) f(x2)
0.000000 3.000000 1.450000 1.550000 4.350000 4.650000
1.450000 3.000000 2.175000 2.275000 5.941667 5.908333
1.450000 2.275000 1.812500 1.912500 5.437500 5.737500
1.812500 2.275000 1.993750 2.093750 5.981250 5.968750
1.812500 2.093750 1.903125 2.003125 5.709375 5.998958
1.903125 2.093750 1.948438 2.048438 5.845313 5.983854
1.948438 2.093750 1.971094 2.071094 5.913281 5.976302
1.971094 2.093750 1.982422 2.082422 5.947266 5.972526
Dicotômico
1.982422 2.093750 1.988086 2.088086 5.964258 5.970638
1.988086 2.093750 1.990918 2.090918 5.972754 5.969694
1.988086 2.090918 1.989502 2.089502 5.968506 5.970166
1.989502 2.090918 1.990210 2.090210 5.970630 5.969930
1.989502 2.090210 1.989856 2.089856 5.969568 5.970048
1.989856 2.090210 1.990033 2.090033 5.970099 5.969989
1.989856 2.090033 1.989944 2.089944 5.969833 5.970019
1.989944 2.090033 1.989989 2.089989 5.969966 5.970004
1.989989 2.090033 1.990011 2.090011 5.970033 5.969996
1.989989 2.090011 1.990000 2.090000 5.969999 5.970000
1.990000 2.090011 1.990005 2.090005 5.970016 5.969998
1.990000 2.090005 1.990003 2.090003 5.970008 5.969999
xL xR x1 x2 f(x1) f(x2)
0.000000 3.000000 1.145898 1.854102 3.437694 5.562306
1.145898 3.000000 1.854102 2.291796 5.562306 5.902735
1.854102 3.000000 2.291796 2.562306 5.902735 5.812565
1.854102 2.562306 2.124612 2.291796 5.958463 5.902735
Seção Áurea 1.854102 2.291796 2.021286 2.124612 5.992905 5.958463
1.854102 2.124612 1.957428 2.021286 5.872283 5.992905
1.957428 2.124612 2.021286 2.060753 5.992905 5.979749
1.957428 2.060753 1.996894 2.021286 5.990683 5.992905
1.996894 2.060753 2.021286 2.036361 5.992905 5.987880
20
EXEMPLO

xL - D xR - D xL - A xR - A

3,500000

3,000000

2,500000

2,000000

1,500000

1,000000

0,500000

0,000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

21
MÉTODOS BASEADOS EM APROXIMAÇÕES

 Aproximação quadrática
 f(x) é aproximada por um polinômio quadrático p(x) = a2x2 + a1x + a0
 em que a0, a1 e a2 são constantes, sendo a2 ≠ 0
 Considerando o intervalo de busca (que contenha o extremo) igual a
[xL, xR] e um ponto entre eles, por exemplo x1 = (xL+xR)/2
 p(x) deve interpolar f(x) nesses três pontos xL, x1 e xR, assim seus
coeficientes são dados por
𝑥𝐿2 𝑥𝐿 1 𝑎2 𝑓(𝑥𝐿 )
 𝑥12 𝑥1 1 × 𝑎1 = 𝑓(𝑥1 )
𝑥𝑅2 𝑥𝑅 1 𝑎0 𝑓(𝑥𝑅 )
 O minimizador 𝑥 de p(x) é dado por p’(x)=0
𝑎1
𝑥=−
2𝑎2

22
 MÉTODOS BASEADOS EM APROXIMAÇÕES

 Resolvendo o sistema linear e substituindo a1 e a2, o minimizador 𝑥 é dado por

2 2
𝑥12 −𝑥𝑅 𝑓 𝑥𝐿 + 𝑥𝑅 −𝑥𝐿2 𝑓 𝑥1 + 𝑥𝐿2 −𝑥12 𝑓(𝑥𝑅 )
 𝑥=
2 𝑥1 −𝑥𝑅 𝑓 𝑥𝐿 + 𝑥𝑅 −𝑥𝐿 𝑓 𝑥1 + 𝑥𝐿 −𝑥1 𝑓(𝑥𝑅 )
 A cada iteração calcula-se o valor de x2 = 𝑥 e reduz-se o intervalo de incerteza
[xL, xR]
 Se f(x2) ≤ f(x1), e
 xL < x2 < x1 faça xR = x1
 x1 < x2 < xR faça xL = x1
 Se f(x2) > f(x1), e
 xL < x2 < x1 faça xL = x2
 x1 < x2 < xR faça xR = x2

 Ao fim de um certo número de iterações,

os três pontos estarão na vizinhança de x*
𝑝 𝑥 −𝑓(𝑥)
 ≤∆ e x* = 𝑥 para uma tolerância Δ
𝑓(𝑥)
 O algoritmo implica uma avaliação da função objetivo por iteração, f(x2), exceto na
1ª iteração em que são necessárias três avaliações da função objetivo. 23
MÉTODOS BASEADOS EM APROXIMAÇÕES

 0. Definir I0 = (a,b) como intervalo de incerteza inicial e a tolerancia Δ

 1. Seja Ik = (xL, xR) o intervalo de incerteza atual (iteração k), calcule:
 x1 = (xL+xR)/2
2 2
𝑥12 −𝑥𝑅 𝑓 𝑥𝐿 + 𝑥𝑅 −𝑥𝐿2 𝑓 𝑥1 + 𝑥𝐿2 −𝑥12 𝑓(𝑥𝑅 )
 𝑥2 =
2 𝑥1 −𝑥𝑅 𝑓 𝑥𝐿 + 𝑥𝑅 −𝑥𝐿 𝑓 𝑥1 + 𝑥𝐿 −𝑥1 𝑓(𝑥𝑅 )

 2. Atualize os limites do intervalo de incerteza

 Se f(x2) ≤ f(x1), e
 xL < x2 < x1 faça xR = x1
 x1 < x2 < xR faça xL = x1
 Se f(x2) > f(x1), e
 xL < x2 < x1 faça xL = x2
 x1 < x2 < xR faça xR = x2
 3. Teste a convergência:
𝑝 𝑥2 −𝑓(𝑥2 )
 Se ≤ ∆, pare e a solução é dada por x* = x2, caso contrário
𝑓(𝑥2 )
retorne para o passo 1. 24
EXERCÍCIO

 Implemente a estratégia de otimização unidimensional

 a) com busca exaustiva (encontrar o mínimo global)
 b) de maneira inexata: Busca dicotômica
 c) de maneira inexata: Método da seção áurea
 d) de maneira inexata: Interpolação Quadrática

 Funções:
a. f(x) = (x – 3)2 x ∈ [-10;10]
b. f(x) = – x2/3 – (1 – x2)1/3 x ∈ [0,001;0,99]
c. f(x) = sen(x) + sen(10/3*x) x ∈ [2,7;7,5]
d. f(x) = – (16*x2 – 24*x + 5)*e-x x ∈ [1,9;3,9]
e. f(x) = – e-x * sen(2π*x) x ∈ [0;4]
f. f(x) = (x2 – 5*x + 6) / (x2 + 1) x ∈ [-5;5]
 Plotar funções e traçar pontos xk

26