Programação Não linear - OTIMIZAÇÃO IRRESTRITA E RESTRITA (Métodos e resoluções)

Prévia do material em texto

Problema de Programação Não Linear: A função objetivo e/ou pelo menos uma das
restrições não são funções lineares das variáveis de decisão.
Formato:
Aplicações:
● Problemas de Mix de Produtos em que o “lucro” obtido por produto varia com a
quantidade vendida.
● Problemas de Transporte com custos variáveis de transporte em relação à
quantidade enviada.
A solução ótima numa PNL pode ser qualquer valor de conjunto das soluções viáveis, ao
invés de ser apenas aqueles conjuntos de interseção.
O principal conceito envolvido em Programação Não-Linear é o de taxa de variação ⇒
derivadas e gradientes. O grande problema que dificulta a obtenção da solução ótima nos
problemas de Programação Não-Linear são os mínimos e máximos (extremos) locais da
função objetivo.
Os métodos para resolução de problemas de Programação Não-Linear podem ser divididos
em 2 grupos:
1) Modelos sem restrições
2) Modelos com restrições
O principal conceito envolvido em Programação Não-Linear é o de taxa de variação ⇒
derivadas e gradientes. O grande problema que dificulta a obtenção da solução ótima nos
problemas de Programação Não-Linear são os mínimos e máximos (extremos) locais da
função objetivo.
Modelo Sem Restrições
(variáveis irrestritas)
Problemas de otimização irrestrita são aqueles que não possuem restrições, de modo que o
objetivo seja simplesmente ao longo de todos os valores de x.
Importante saber!
• Na programação não linear sem restrições e uma função objetivo côncava, o
máximo local é o máximo global.
Função Côncava: A f(x) é côncava se e só se o segmento unindo dois pontos
quaisquer da curva nunca está acima dela. PROBLEMA DE MAXIMIZAÇÃO
•Na programação não linear sem restrições e uma função objetivo convexa, o
mínimo local é o mínimo global.
Função Convexa: A f(x) é convexa se e só se o segmento unindo dois pontos
quaisquer da curva nunca está abaixo dela. PROBLEMA DE MINIMIZAÇÃO
maximizar f é equivalente a Minimizar (-f)
Um conjunto é convexo se, dados dois pontos quaisquer x1 e x2 do conjunto, o segmento
que os une também pertence ao conjunto.
Método de Minimização de funções muito simples
Consiste nos seguintes passos:
1)“chutar” 3 pontos (a,b,c).
2)Escolher um ponto x entre a e b ou entre b e c.
supondo que escolhemos entre b e c:
3)Se f(b) < f(x)⇒ 3 novos pontos são (a,b,x).
4)Senão⇒ 3 novos pontos são (b,x,c).
5)Repetir processo até precisão desejada.
- Problema deste Método: Extremamente dependente
da inicialização (problema comum aos Métodos
determinísticos).
- Função precisa ser avaliada em muitos pontos⇒ alto custo computacional.
- Informação da derivada da função permite alcançar o extremo com menor número de
avaliações da função⇒ melhor eficiência computacional.
Modelo com restrição:
Então mais uma condição vai fornecer essa garantia, ou seja, de que a região de soluções
viáveis é um conjunto convexo.
Um conjunto convexo é simplesmente um conjunto de pontos de modo que, para cada par de
pontos no conjunto, o segmento de reta inteiro que une esses dois pontos também se encontra
nesse conjunto.
Métodos de Resolução
- OTIMIZAÇÃO IRRESTRITA COM UMA VARIÁVEL
Em que a função diferenciável.f{x) a ser maximizada é côncava.
Método da Forma Direta: Portanto, a condição necessária e suficiente para determinada
solução x = x* ser a solução ótima (um máximo global) é df/dx=0.
Aplicado primordialmente as funções de uma única variável estritamente
unimodais(unidimensional). O objetivo é identificar o intervalo de incerteza no qual está incluído o
ponto de solução ótima.
A metodologia desses procedimentos de busca é encontrar uma seqüência de soluções
experimentais que levem a uma solução ótima. A cada iteração, começamos com a solução
experimental atual para conduzir uma busca sistemática que culmine com a identificação de
uma nova solução experimental aperfeiçoada. O procedimento prossegue até que as
soluções experimentais tenham convergido para uma solução ótima, supondo-se que exista
uma.
Método dicotômico (intervalos)
Seja Ii+1=( xL, xR ) o intervalo de incerteza atual na iteração 0, escolhido através de observação da
função. Delta é a mesma coisa que E( tolerancia)
O algoritmo termina na iteração k, onde Ik<=E.
Método da seção de Ouro
Seja Ii+1=( xL, xR ) o intervalo de incerteza atual na iteração 0, escolhido através de observação da
função.
A definição do próximo intervalo é igual ao método anterior.
O algoritmo termina na iteração k, onde Ik<=E.
Exemplo:
Se continuado, o intervalo será
reduzido a E
Método da Bissecção:
Esse procedimento de busca sempre pode ser aplicado quando f(x) for côncava (de modo
que a segunda derivada seja negativa ou zero para todo x).
A idéia por trás do método da bissecção é muito intuitiva, isto é, seja a inclinação (derivada)
positiva ou negativa em uma solução experimental indica definitivamente se a melhoria se
encontra imediatamente à direita ou à esquerda, respectivamente.
Logo, se a derivada calculada em dado valor de x for positiva, então x* deve ser maior que
esse x e, portanto, esse x se toma um limite inferior para as soluções experimentais que
precisam ser consideradas daí em diante. Ao contrário, se a derivada for negativa, então x*
tem de ser menor que esse x e, por isso, x se tomaria um limite superior. Por essa razão,
após ambos os tipos de limites terem sido identificados, cada nova solução experimental
selecionada entre os limites atuais fornece um novo limite mais
apertado de um tipo e, assim, limitando mais a busca. É
normalmente usada a regra do ponto médio (tradicionalmente
conhecida como plano de busca de Bolzano ), que diz
simplesmente para selecionar o ponto médio entre os dois limites
atuais .
Método de Newton:
O conceito básico do método de Newton é aproximar f(x) dentro das vizinhanças da solução
experimental atual por meio de uma função quadrática e depois maximizar (ou minimizar) a
função aproximada exatamente para obter a nova solução experimental para iniciar a iteração
seguinte.
- OTIMIZAÇÃO IRRESTRITA COM VÁRIAS VARIÁVEIS
Considere agora o problema de maximização de uma função côncava .f(x) com variáveis
múltiplas x = (xi. xi, ... , xn) quando não existe nenhuma restrição sobre os valores viáveis.
Método do gradiente
Uma metodologia natural seria usar os valores das derivadas parciais para selecionar a direção
específica na qual se movimentar.
Otimiza funções que são duas vezes diferenciais continuamente. A ideia é gerar pontos
sucessivos na direção do gradiente da função. O gradiente em um ponto específico x = x' é o
vetor cujos elementos são as respectivas derivadas parciais calculadas em x = x'. Portanto,
pode-se dizer que a taxa na qual f(x) aumenta é maximizada se mudanças (infinitesimais) em x
estiverem na direção do gradiente de f(x). O término do método se dá no ponto em que o vetor
gradiente se torna nulo.
A importância do gradiente reside no fato de que a mudança (infinitesimal) em x que
maximiza a taxa na qual f(x) aumenta é a mudança que é proporcional a Vf(x). Portanto,
pode-se dizer que a taxa na qual f(x) aumenta é maximizada se mudanças (infinitesimais)
em x estiverem na direção do gradiente V.f(x). Uma vez que o objetivo é encontrar a
solução viável que maximiza.f(x), pareceria oportuno tentar se mover na direção do
gradiente o máximo possível.
Já que o problema atual não possui nenhuma restrição, essa interpretação do gradiente
sugere que um procedimento de busca eficiente seria continuar movimentando-se na
direção do gradiente até que ele atinja (essencialmente) uma solução ótima x*, em que
Vf(x*) = O.
Se, ao contrário, o objetivo fosse o de minimizar f (x), uma alteração no procedimento
seria mover-se na direção oposta do gradiente a cada iteração. Em outras palavras, a regra
para obter o ponto seguinte seria
Método de Newton adaptado
A idéia básica é a mesma do Método de Newton para uma variavel, ou seja, trabalhar com uma
aproximação quadrática da função objetivo f(x), nesse caso, x = (xi. x2, ••• , xn). Essa função
quadrática aproximada é obtida truncando-se série de Taylor emtorno da solução experimental
atual após o termo da segunda derivada. Essa função aproximada é então maximizada (ou
minimizada) exatamente para obter a nova solução experimental de onde partirá a iteração
seguinte.
Taylor fornece uma aproximação polinomial local cada vez melhor de uma função (muitas vezes)
diferenciável à medida que calculamos as suas derivadas
Matriz Hessiana:
A "Matriz Hessiana" de uma função de
várias variáveis f(x,y,z,…) organiza
todas as derivadas parciais de
segunda ordem em uma matriz:
O algoritmo termina quando o gradiente de f(x’) for nulo.
Os pontos estacionários de uma superfície são geralmente classificados como:
I Máximo - que pode ser interpretado como o topo de uma montanha; I Mínimo - que pode ser
interpretado como o fundo de um vale; I Ponto de Sela - que pode ser interpretado como uma
passagem entre montanhas.
Teorema de Hessiana:
Se todos os auto-valores de H(a) são positivos, f tem um mínimo relativo em a.
Se todos os auto-valores de H(a) são negativos, f tem um máximo relativo em a.
Se H(a) tem auto-valores positivos e negativos, a é um ponto de sela de f.
Dada uma função f(x), a condição necessária pra que
um determinado ponto x* seja um ponto crítico é que
todas as derivadas parciais, calculadas naquele ponto
específico, sejam iguais a zero. No entanto, para
definir se este ponto crítico é um ponto de máximo,
mínimo ou de sela, é preciso calcular o determinante
da matriz hessiana:
1- Calcular as "n" derivadas de primeira ordem da
função f. O resultado serão "n" funções das
variáveis do vetor nX1
2- Igualar cada uma das "n" funções do passo 1 a
zero. Com isso, serão descobertos valores para cada
uma das variáveis x. Fazer um vetor de x1*, x2*...
3 - A partir das derivadas de primeira ordem
calculadas no item 1, calcular as derivadas de
segunda ordem da função f e montar a matriz
hessiana nXn.
4- Substitua as variáveis presentes na matriz hessiana
montada no item 3, pelos valores correspondentes do
ponto crítico, ou seja, pelos valores do vetor x*
(encontrado em 2). presentes na matriz hessiana montada no item 3, pelos valores correspondentes
do ponto crítico, ou seja, pelos valores do vetor
5 - A partir da matriz resultante do item 4, calcular o det de H1, H2…
6 - verificar os sinais:
https://pt.wikibooks.org/w/index.php?title=Ponto_cr%C3%ADtico&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Ponto&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Zero&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Ponto_cr%C3%ADtico&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Determinante&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Fun%C3%A7%C3%A3o&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Vetor&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Zero&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Derivada&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Derivada&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Fun%C3%A7%C3%A3o&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Matriz&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Matriz&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Ponto_cr%C3%ADtico&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Vetor&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Matriz&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Ponto_cr%C3%ADtico&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Vetor&action=edit&redlink=1
https://pt.wikibooks.org/w/index.php?title=Matriz&action=edit&redlink=1
AS CONDIÇÕES DE KARUSH-KUHN-TUCKER (KKT) PARA OTIMIZAÇÃO RESTRITA
Quais são as condições necessárias e (talvez) suficientes que uma solução ótima tem de
satisfazer?
Condição de achar candidatos a pontos mínimos da função, ou seja, encontrar funções que estão
dentro dessas condições de otimalidade.
1: gradiente da função avaliado naquele ponto x* + somatório do gradiente das funções de
restrição naquele ponto x* multiplicados pelos seus respectivos multiplicadores de Lagrange.
2: o multiplicador de Lagrange daquela função multiplicado pela sua restrição no ponto x*.
3: os multiplicadores de lagrange devem ser maiores que zero
4: a função restrição no ponto x* deve ser menor ou igual a zero.
- A solução ótima local é um ponto de
KKT se todas as restrições são
lineares e os gradientes das restrições ativas (<=0 ou >=0) no ponto ótimo local são
LI.
- OTIMIZAÇÃO RESTRITA
Programação Convexa
A programação convexa cobre ampla gama de problemas
que, na verdade, engloba como casos especiais todos os
tipos precedentes quando f(x) é uma função côncava a ser
maximizada. Continuando a supor a forma de problema
genérico (inclusive a maximização) apresentada no início do
capítulo, as hipóteses são de que
1. f(x) seja uma função côncava.
2. Cada g;(x) seja a função convexa
Se o objetivo fosse minimizar f(x), a primeira hipótese seria
fazer uma modificação para que f(x) seja uma função
convexa, já que isso é o necessário para garantir que um
mínimo local seja um mínimo global.
- Restrição de igualdade
Considere agora o problema de se encontrar o mínimo ou máximo de uma função f(x), sujeita à
restrição que x deve satisfazer todas as equações
Método de Lagrange
Exemplo:
Consiste em pegar a modelagem com a FO e suas restrições (que são igualadas aos bi) e
substituir na função de Lagrange. Utilizado quando se tem restrições de igualdade e há mais
variáveis que restrições. Depois, é feito o gradiente (vetor das derivadas parciais) de cada
função, da FO que é chamada de f(x) e das restrições que são os gi(x). Você iguala o gradiente
da f(x) com a multiplicação do vi (multiplicador de lagrange) com o gradiente de cada restrição
feito no passo anterior: grad f(x) = v1 . grad g1(x); grad f(x) = v2 . grad g2(x). É como se estivesse
criando mais restrições ao problema, mantendo-se as restrições dadas inicialmente, ou seja,
temos restrições de apenas x e outras com v. Assim, é possível criar relações entre elas, em
forma de sistema, e assim, resolver cada x e cada v. Os valores encontrados para cada um é
chamado de ótimo.
Interpretação:
vi = variação valor ótimo f quando bi aumenta de 1 unidade
vi = variável dual
Limitações
–condições de estacionariedade difíceis de resolver
– restrições de desigualdade aumenta a complexidade
– soluções ótimas globais somente para modelos tratáveis
Em relação às variáveis de folga complementares:
UTILIZANDO O SOLVER NA SOLUÇÃO DE PROBLEMAS
O Excel utiliza o algoritmo GRG (generalized reduced gradient) para chegar à solução para
um dado problema.
O Solver às vezes tem dificuldades de achar soluções para problemas que tenham
condições iniciais para as variáveis iguais a zero. Uma boa medida é começar a otimização
com valores diferentes de zero para as variáveis de decisão.
Uma maneira prática para tentar minorar o problema de máximos e mínimos locais é
começar a otimização de diversos pontos iniciais, gerados aleatoriamente.
Se todas as otimizações gerarem o mesmo resultado, você pode ter maior confiança, não a
certeza, de ter atingido um ponto global.
- Controle de estoque: modelo do lote econômico
Esse tipo de modelo assume as seguintes hipóteses
– A demanda (ou uso) do produto a ser pedido é praticamente constante durante o ano.
– Cada novo pedido do produto deve chegar de uma vez no exato instante em que este
chegar a zero.
Determinar o tamanho do pedido e a sua periodicidade dado os seguintes custos:
– Manutenção de Estoque – Custo por se manter o capital no estoque e não em outra
aplicação, rendendo benefícios financeiros para a empresa.
– Custo do Pedido – Associado a trabalho de efetuar o pedido de um determinado produto.
– Custo de Falta – Associado a perdas que venham a decorrer da interrupção da produção
por falta do produto.
● Método das direções factíveis
1- Escolher solução inicial factível
2- Determinar uma direçãoque:
2.1 – o pequeno movimento nesta direção não viola as restrições (viável)
2.2 – valor da função objetivo melhora nesta direção (usável)
-> Algoritimo do gradiente projetado de Rosen:
1. calcular∇f (xk)
Gradiente da função objetivo: vetor composto por n equações (linhas), onde cada linha
responde por uma variável. São derivadas parciais.
2. associar à xk as restrições ativas (planos que passam) em xk
3. projetar –∇f (xk) na intersecção dos planos que passam em xk se xk é um ponto interior,
então a projeção é o própio –∇f (xk)
4. se a projeção não é nula, então minimizar ao longo da projeção, sujeitas às restrições;
fazer k = k + 1 e ir para o passo 1
5. Se a projeção é nula, então∇f (xk) pode ser escrito como∇f (xk) = ∑i uiai
5.1 se ui ≥ 0∀i, então é solução ótima (satisfaz KKT); senão
Condições de KKT • necessárias problemas convexos e não convexos • supõem
função objetivo e restrições diferenciáveis
5.2 definir novo conjunto de planos associado à xk, removendo do conjunto corrente
de planos aqueles com ui < 0; ir para passo 3.
-> Univariacional
Estratégia de caminhar morro acima. Consiste em escolher um ponto (x1,x2) aleatório e
definir um sentido inicial de busca. Dessa forma, sendo univariacional, o sentido vai manter
constante uma das variáveis, enquanto a outra vai variando de acordo com a busca. Se o
sentido arbitrado não encontrar uma função objetivo melhor, ele vai voltar ao ponto anterior
e mudar de sentido. Pode começar indo para cima ou para baixo e, depois de perceber que
nenhum deles dará mais uma FO melhor, vai para os lados direito e esquerdo, até encontrar
a FO otimizada. Esse é o ponto de máximo ou mínimo.
1- Início: determinar um ponto de coordenadas aleatórias com x1 (entre a e b) e x2 (entre
c e d)
2- Escolher um sentido para o próximo ponto de coordenadas:
2.1 – Fazer o calculo da FO e verificar se ela melhorou ou não.
Se melhorou, continua o processo no mesmo sentido.
Senão, muda o sentido da busca.
Exemplo: Use o método univariacional para encontrar o máximo da função abaixo, a partir
do ponto inicial: x1 = -10, x2 = -10
f(x1,x2) = x1² + 8 (x1-x2) +x1.x2 + x2²
-> Método de Rosenbrock: método mais eficiente
É um método de busca multivariável parecido com a fase de exploração do método de
Hooke & Jeeves . Entretanto, ao invés de continuamente explorar nas direções dos eixos
coordenados, são construídas novas direções ortogonais, usando o procedimento de
Gram-Schmidt, baseadas nos tamanhos dos passos das direções bem sucedidas. A direção
da busca é a que dará maior incremento na FO, muito utilizado para calibração automática
de modelos hidrológicos.
1) Selecionar o ponto base inicial x o , fazer k = 0, e i i d = e 0 (direção dos eixos)
2) Selecionar os incrementos iniciais di e as respectivas tolerâncias ei (i = 1,2,...,n)
3) Calcular S0 = S(x o ) , escolher a direção m =1 e fazer 0 0 Di = (i = 1,2,...,n)
4) Fazer x 1 = x o + dm k dm e calcular S1 = S(x 1 )
5) Se S1 > S0 então insucesso e fazer dm ¬ -dm / 2 senão sucesso e fazer x o ¬ x 1 , S0 ¬
S1 , m k m k Dm ¬ D + d , dm ¬ 3 dm
6) Se alguma direção ainda não teve insucesso, fazer m ¬ (m < n ? m+1 : 1)
(ir para 4)
7) Se d e i i £ "i então FIM.
8) Calcular a nova direção ortogonal e fazer k ¬ k + 1 (ir para 4).
● Método das funções de penalização
-> Modelo Dual de Wolfe
1. se primal tem solução x, então∃u tal que (x, u) resolve o dual
2. valores das funções objetivos primal e dual são iguais
3. para cada x primal factível e (x, u) dual factível f (x) ≥ L(x, u)
4. f (x) limitante superior e L(x, u) limitante inferior
Penalização:
Se
1. se interior conjunto restrição não vazio
2. funções f e gi são 2×continuamente diferenciáveis
3. conjunto ponto no conjunto restrição tal que f (x) ≤ k é limitado∀k < ∞
4. f (x) limitada inferiormente para x no conjunto restrição
5. f (x) convexa
6. gi côncavas
7. P(x, r) estritamente convexa no interior do conjunto restrição∀r > 0 então:
Vo: P-mínimo
{(x(rk), u(rk))} converge para a solução dual (x, u)