Universidade Federal de Itajubá – UNIFEI
Instituto de Recursos Naturais - IRN
Programação Não-Linear
por
Prof. Benedito C. Silva
Programação Não-Linear
Programação Não-Linear
Programação Não-Linear
Programação Não-Linear
Métodos de solução:
• Substituição
• Gráfico
• Multiplicadores de Lagrange
• Método do Gradiente
• Programação Quadrática
• Condições de Karush-Kuhn Tucker
• Método de Newton
• Método de variações nas Coordenadas
• Linearização de funções separáveis
Programação Não-Linear
Solução Gráfica
Solução Gráfica
Solução Gráfica
Solução Gráfica
MaxZ  54x1  9x12  78x2  13x22
Importante!
Otimização Unidimensional
Busca pela Razão Áurea
Válida para um intervalo que contenha uma única resposta (máximo)
f(x)
Xl é o limite inferior do intervalo
Máximo
XU é o limite superior do intervalo
Xl
X1
X2
XU
X1 e X2 são pontos intermediários usados na busca do máximo
Otimização Unidimensional
Busca pela Razão Áurea
A escolha dos pontos internos pode ser feita de acordo com os
seguintes critérios
f(x)
Máximo
𝑙0 = 𝑙1 + 𝑙2
(a)
𝑙1 𝑙2
=
𝑙0 𝑙1
(b)
(a) em (b)
Xl
X2
𝑙1
𝑙0
X1
XU
𝑙2
𝑙1
𝑙2
=
𝑙1 + 𝑙2 𝑙1
𝑙1 + 𝑙2 𝑙1
=
𝑙1
𝑙2
Ou,
Otimização Unidimensional
Busca pela Razão Áurea
𝑅=
Fazendo
1+𝑅 =
1
𝑅
𝑙2
𝑙1
chega-se a:
ou,
𝑅2 + 𝑅 − 1 = 0
A raiz positiva será dada por:
−1 + 1 − 4. (−1)
5−1
𝑅=
=
= 0,61803 …
2
2
𝟎, 𝟔𝟏𝟖𝟎𝟑 …
𝟏
Razão Áurea
Otimização Unidimensional
Busca pela Razão Áurea
Encontrando o ponto ótimo usando a razão áurea:
1. Escolhe-se os pontos Xl e XU, que definem o intervalo de busca
2. Os pontos interiores são escolhidos usando-se a razão áurea, da
seguinte forma:
5−1
𝑑=
(𝑋𝑢 − 𝑋𝑙 )
2
𝑋1 = 𝑋𝑙 + 𝑑)
𝑋2 = 𝑋𝑢 − 𝑑)
3. Calcula-se f(X1) e f(X2)
4. Se f(X1) > f(X2), então:
O domínio a esquerda de X2 deve ser eliminado. Ou seja, X2
passa a ser Xl, X1 passa a ser X2 e
𝑋1 = 𝑋𝑙 +
5−1
(𝑋𝑢 − 𝑋𝑙 )
2
Otimização Unidimensional
Busca pela Razão Áurea
Encontrando o ponto ótimo usando a razão áurea:
Se f(X2) > f(X1), então:
O domínio a direita de X1 deve ser eliminado. Ou seja, X1
passa a ser XU, X2 passa a ser X1 e
5−1
𝑋2 = 𝑋𝑢 −
(𝑋𝑢 − 𝑋𝑙 )
2
Exemplo:
Usar o método de busca pela seção áurea para encontrar o
máximo da função abaixo, no intervalo de X entre 0 e 4.
𝑓 𝑋 = 2. sen 𝑋
𝑋2
− 10
Otimização Unidimensional
Interpolação Quadrática
Este método parte do princípio que um polinômio do segundo grau fornece
uma boa aproximação para a forma da função objetivo, f(x), nas
proximidades do ponto ótimo.
Existe apenas uma parábola ligando 3 pontos. Portanto, se existem 3 pontos
que delimitem um ponto ótimo, pode-se ajustar uma parábola aos 3 pontos,
derivá-la e igualar o resultado a zero, para estimar o valor ótimo de X.
f(x)
Ótimo aproximado
Ótimo verdadeiro
Função verdadeira
Função quadrática
X0
X1
X3
X2
Otimização Unidimensional
Interpolação Quadrática
O valor de X3 pode ser obtido pela seguinte equação:
𝑋3
=
𝑓 𝑋0 . 𝑋12 −𝑋22 +𝑓 𝑋1 . 𝑋22 −𝑋02 +𝑓 𝑋2 . 𝑋02 −𝑋12
2.𝑓 𝑋0 . 𝑋1 −𝑋2 +2.𝑓 𝑋1 . 𝑋2 −𝑋0 +2.𝑓 𝑋2 . 𝑋0 −𝑋1
Onde, X0, X1 e X2 são aproximações iniciais e X3 é o valor de X que
corresponde ao máximo valor da função quadrática ajustada às
aproximações.
Realizam-se iterações. Em cada uma delas, avaliam os valores da função
para os pontos escolhidos e descarta-se um deles , reduzindo-se o espaço
de busca.
Exemplo:
Usar a interpolação quadrática para encontrar o máximo da função abaixo,
com as aproximações iniciais X0 = 0, X1 = 1 e X2 = 4.
𝑓 𝑋 = 2. sen 𝑋
𝑋2
− 10
Otimização Unidimensional
Método de Newton
Utiliza a seguinte equação para uma busca iterativa do ótimo da função:
𝑓′(𝑋)
𝑋𝑖+1 = 𝑋𝑖− 𝑓"(𝑋)
Exemplo:
Usar o Método de Newton para encontrar o máximo da função abaixo, com
aproximação inicial X0 = 2,5.
𝑓 𝑋 = 2. sen 𝑋
𝑋2
− 10
MÉTODOS DE BUSCA DIRETA
Busca Aleatória
Método do tipo “força bruta”
Consiste em calcular repetidamente a função objetivo a partir de valores
das variáveis independentes escolhidos aleatoriamente.
Se um número suficiente de amostras for estudado, o valor ótimo será
eventualmente localizado
Exemplo:
Use a função de geração de números aleatórios do MSExcel (aleatório)
para encontrar o máximo da função abaixo, no domínio limitado por x=-2
a 2 e y=-1 a 1,5
f(x,y) = y – x – 2x2 - 2xy – y2
Método Univariacional
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Estratégia de caminhar “morro acima”
Função objetivo: F(x1,x2)
5
4.5
4
3.5
3
x2
2.5
2
1.5
Máximo local
1
Máximo global
0.5
0
0
0.5
1
1.5
2
x1
2.5
3
3.5
4
4.5
5
Início: ponto coordenadas (parâmetros) aleatórias
5
4.5
X2=valor
aleatório entre
ced
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
X1=valor aleatório entre a e b
Determina direção de busca: exemplo x2=x2+0,3; x1=x1
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Função objetivo melhorou? Não, então tenta no outro sentido.
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Não, então volta para o ponto anterior...
...e muda a direção de busca.
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
E assim segue até encontrar um ponto em que não existe
direção de busca que melhore o valor da FO
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Exemplo:
Use o método univariacional para encontrar o máximo da função abaixo,
a partir do ponto inicial (X1=-10 e X2=-10
f(X1,X2) = X12 + 8.(X1-X2) + X1.X2 + X22
Rosenbrock: Método um pouco mais eficiente
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Direção de busca é a que potencialmente dará maior incremento da FO
Muito utilizado para calibração automática de modelos hidrológicos