Otimização Não Linear - Introdução à Programação Não Linear

Otimização Não Linear Introdução à Programação Não Linear Problemas NãoLineares em uma Variável Ormeu Coelho da Silva Júnior DSc Departamento de Engenharia de Produção Revisão Breno dos Santos de Assis 052020 OTIMIZAÇÃO NÃO LINEAR Inúmeras aplicações de otimização envolvem a modelagem de sistemas com funções não lineares na definição do objetivo ou das restrições Um problema P deste tipo é usualmente denominado de problema de Programação Não Linear PNL Matematicamente podese definilo como min 𝑧 𝑓𝑥 s a 𝑔𝑖 𝑥 0 𝑖 1 𝑚 P ℎ𝑗 𝑥 0 𝑗 1 𝑝 𝑥 𝑋 ℝ𝑛 Se a função 𝑓 que define o objetivo ou ao menos uma das funções g𝑖 ou h𝑗 que definem restrições for não linear P será um problema de PNL 2 OTIMIZAÇÃO NÃO LINEAR Esta divisão do conjunto de restrições em dois subconjuntos disjuntos um contendo as restrições de desigualdade e outro as de igualdade leva em consideração certos métodos de solução que as tratam distintamente Por simplicidade deste ponto em diante assumese que o problema contém apenas restrições de desigualdade Quando necessário for as restrições de igualdade serão explicitamente tratadas Se na modelagem a única diferença em relação à Programação Linear e à Programação Inteira reside na presença de termos não lineares os métodos de solução usados são via de regra muito diferentes Nesta e nas próximas aulas será feito um estudo introdutório dos modelos de PNL suas propriedades e métodos de solução Como de praxe este estudo começará com a apresentação de conceitos e métodos para otimização irrestrita ou seja sem restrições de funções não lineares Antes alguns conceitos preliminares serão apresentados 3 DEFINIÇÕES E CONCEITOS PRELIMINARES Definição 1 Conjunto Convexo Um subconjunto 𝑋 ℝ𝑛 é convexo se dados 𝑥1 𝑥2 𝑋 e 0 𝜆 1 existe 𝑥 𝑋 tal que 𝑥 𝜆𝑥1 1 𝜆𝑥2 De acordo com a Definição 1 um conjunto 𝑋 é convexo se todas as combinações lineares convexas ou simplesmente clc de dois vetores 𝑥1 e 𝑥2 em 𝑋 resulta em um ponto 𝑥 que também pertence ao conjunto 𝑋 O lugar geométrico dos pontos pertencentes à clc destes vetores é o segmento de reta que une suas extremidades Na Figura 1 a clc de dois vetores 𝑥1 e 𝑥2 ℝ2 é ilustrada pela linha pontilhada Portanto podese dizer que um conjunto 𝑋 é convexo se o segmento de reta que une quaisquer dois vetores 𝑥1 𝑥2 𝑋 está inteiramente contido em 𝑋 As Figuras 2ab ilustram conjuntos convexos em ℝ2 Enquanto na primeira o conjunto é definido por desigualdades não lineares a segunda traz um poliedro conjunto viável de um PPL 4 DEFINIÇÕES E CONCEITOS PRELIMINARES 5 As Figuras 2cd mostram ilustrações de conjuntos não convexos em em ℝ2 Devese observar contudo que o conjunto solução na Figura 2c é compacto isto é fechado e limitado tendo sido obtido pela interseção de desigualdades não lineares Já o conjunto mostrado na Figura 2d é característico de um problema de Programação Inteira portanto discreto resultado da interseção do poliedro pontilhado em azul com o conjunto dos números inteiros Note que todas as clc obtidas com 0 𝜆 1 geram pontos 𝑥 fora do espaço de solução Definição 2 Função Convexa Uma função real 𝑓𝑥 definida em um conjunto convexo 𝑋 ℝ𝑛 é dita convexa se para todo 𝑥1 𝑥2 𝑋 e 0 𝜆 1 é válida a desigualdade 𝑓𝜆𝑥1 1 𝜆𝑥2 𝜆𝑓𝑥1 1 𝜆 𝑓𝑥2 DEFINIÇÕES E CONCEITOS PRELIMINARES 6 Figura 1 Lugar geométrico da clc de dois vetores em ℝ2 x2 x1 x1 x2 x1 x2 Se 𝑥 é clc de 𝑥1 e 𝑥2 então 𝑥 𝛼1𝑥1 𝛼2𝑥2 para 𝛼1 𝛼2 1 Logo 𝑥 𝛼𝑥1 1 𝛼 𝑥2 𝑥2 𝛼𝑥1 𝑥2 DEFINIÇÕES E CONCEITOS PRELIMINARES 7 x1 x2 x1 x2 Figura 2 Conjuntos convexos a e b e não convexos c e d em ℝ2 a x2 x1 c b d x1 x2 Conjuntos convexos Conjuntos não convexos DEFINIÇÕES E CONCEITOS PRELIMINARES Se a desigualdade na definição 2 nunca é atendida na igualdade fora dos extremos 𝑥1 e 𝑥2 isto é para 𝑥 𝑥1 𝑥2 dizse que a função é estritamente convexa Veja alguns exemplos em ℝ2 o A função linear 𝑓 𝑥 2𝑥 6 e a função módulo 𝑔 𝑥 𝑥 1 são convexas o A função quadrática 𝑓 𝑥 𝑥2 2𝑥 e a função 𝑔 𝑥 Τ 1 𝑥 para 𝑥 0 são estritamente convexas Se uma função 𝑓𝑥 é convexa então a 𝑓 𝑥 será dita côncava Esta definição poderia ser formalizada como a anterior bastando para isso inverter o sentido da desigualdade Por analogia estritamente côncavas são aquelas funções em que a desigualdade agora invertida não é atendida na igualdade para quaisquer dois pontos do conjunto convexo 𝑋 As Figuras 3a e 3b apresentam respectivamente os gráficos de uma função con 8 DEFINIÇÕES E CONCEITOS PRELIMINARES vexa e de outra côncava em ℝ2 enquanto as Figuras 4a e 4b ilustram funções que não são côncavas nem convexas Nestas é fácil verificar a definição 2 bastando tomar dois pontos sobre o eixo das abcissas 𝑥1 e 𝑥2 encontrar as ordenadas correspondentes Figura 3 Exemplos de funções em ℝ2 a função convexa b côncava 9 DEFINIÇÕES E CONCEITOS PRELIMINARES 𝑓𝑥1 e 𝑓𝑥2 e gerar a clc dos pontos 𝑥1 𝑓𝑥1 e 𝑥2 𝑓𝑥2 Se o segmento de reta assim gerado limitar superiormente inferiormente 𝑓 𝑥 para quaisquer 𝑥1 e 𝑥2 em seu domínio então ela será convexa côncava Figura 4 Exemplos de funções em ℝ2 que não são côncavas nem convexas 10 b x fx a x fx DEFINIÇÕES E CONCEITOS PRELIMINARES No caso de uma função em uma variável a derivada segunda de 𝑓𝑥 𝑓𝑥 caso exista e esteja definida no domínio 𝑋 ℝ fornece informação relevante para determinação da concavidade ou convexidade de 𝑓 conforme sintetiza o Teorema1 Teorema1 Considere que 𝑓𝑥 existe e está definida em 𝑋 Então 𝑓𝑥 é convexa côncava se e somente se 𝑓𝑥 0 𝑓𝑥 0 para todo 𝑥 𝑋 Para verificar a convexidade de uma função em ℝ𝑛 é preciso calcular os menores da Hessiana de 𝑓 𝑥 Do curso de cálculo diferencial lembrese que a Hessiana de 𝑓𝑥 aqui denotada por 𝐻𝑥 é uma matriz em que o elemento da linha 𝑖 e coluna 𝑗 é dado por 2𝑓𝑥 𝑥𝑖𝑥𝑗 11 DEFINIÇÕES E CONCEITOS PRELIMINARES Exemplo 1 A função 𝑓 𝑥 𝑥12 𝑥22 𝑥1𝑥2 tem como Hessiana 𝐻 𝑥 2 1 1 2 Exemplo 2 A função 𝑓 𝑥 log 𝑥1 𝑥23 2 𝑥1𝑥2 tem como Hessiana 𝐻 𝑥 1 ln 4 𝑥1 2 1 6𝑥2 No curso de Álgebra Linear você deve ter aprendido que o menor de uma matriz 𝐴 é o determinante de qualquer matriz quadrada obtida de 𝐴 pela eliminação de linhas ou colunas Mais precisamente o menor de ordem 𝑘 de uma matriz 𝐴𝑛𝑛 é o determinante da matriz que se obtém com a eliminação de 𝑛 𝑖 linhas e as correspondentes 𝑛 𝑖 12 DEFINIÇÕES E CONCEITOS PRELIMINARES colunas de 𝐴 Veja alguns exemplos Exemplo 3 Considere novamente a função apresentada no exemplo 1 e sua Hessiana Pela eliminação da primeira linha e da primeira coluna de 𝐻𝑥 obtémse o primeiro menor cujo valor é 2 Veja 2 1 1 2 Com a eliminação da segunda linha e da segunda coluna obtém o outro primeiro menor cujo valor também é 2 2 1 1 2 O segundo menor é igual ao determinante da própria matriz uma vez que nenhuma linha ou coluna é eliminada Ou seja o segundo menor é 3 22 11 13 DEFINIÇÕES E CONCEITOS PRELIMINARES Exemplo 4 Considere a função 𝑓 𝑥 3𝑥12 2𝑥22 𝑥32 𝑥1𝑥2 𝑥2 𝑥3 com Hessiana 𝐻 𝑥 6 1 0 1 4 1 0 1 2 Seus primeiros menores são obtidos com a eliminação de 2 3 1 linhas e 2 colunas da matriz As possíveis combinações de linhas colunas são mostradas abaixo 6 1 0 1 4 1 0 1 2 6 1 0 1 4 1 0 1 2 6 1 0 1 4 1 0 1 2 Os primeiros menores são portanto 2 4 e 6 14 DEFINIÇÕES E CONCEITOS PRELIMINARES Para calcular os menores de segunda ordem 1 3 2 linha e 1 coluna devem ser eliminadas da matriz para que então sejam calculados os seguintes determinantes 4 1 1 2 4 2 11 9 6 0 0 2 62 00 12 6 1 1 4 6 4 1 1 25 E por fim o menor de terceira ordem é dado pelo determinante da matriz original 15 6 1 0 1 4 1 0 1 2 111 6 4 1 1 2 1 12 1 1 1 0 2 1 12 0 1 4 0 1 56 DEFINIÇÕES E CONCEITOS PRELIMINARES Conforme foi dito anteriormente o cálculo dos menores de uma matriz é uma das formas de avaliar a convexidade concavidade de uma função 𝑓𝑥 definida em um conjunto convexo 𝑆 ℝ𝑛 conforme se vê nos Teoremas 3 e 4 enunciados a seguir Provas destes resultados são apresentadas por Bazarra Shetty 1993 Teorema2 Considere que 𝑓𝑥 possui derivadas parciais de segunda ordem definidas para todo 𝑥 𝑆 Então 𝑓𝑥 é convexa se e somente se todos os menores principais são nãonegativos Teorema3 Considere que 𝑓𝑥 possui derivadas parciais de segunda ordem definidas para todo 𝑥 𝑆 Então 𝑓𝑥 é côncava se e somente se todos os menores principais nãonulos de ordem 𝑘 têm sinal igual 1𝑘 16 DEFINIÇÕES E CONCEITOS PRELIMINARES A partir do Teorema2 vêse que a função apresentada no exemplo 3 é convexa pois todos os menores principais de 𝐻𝑥 são nãonegativos o que não acontece com a função do exemplo 4 Esta última também não é côncava porque possui menores principais que não atendem à condição expressa no Teorema3 Note por exemplo que os primeiros menores deveriam ser todos negativos pois 1𝑘 1 para 𝑘 1 condição violada pelo menor associado ao elemento da posição 𝑖 2 e 𝑗 2 cujo valor é 4 Da mesma forma os segundos menores deveriam ser todos nãonegativos mas isso não acontece para dois deles cujos valores são 9 e 25 Não é difícil verificar que uma matriz 𝑚 𝑛 qualquer possui 𝑚 𝑘 𝑛 𝑘 menores de ordem 𝑘 Como é preciso avaliar os menores de todas as ordens 𝑘 𝑘 1 𝑛 a verificação da convexidade concavidade de uma função em várias 𝑛 variáveis pode ser uma tarefa custosa mesmo usando um computador 17 DEFINIÇÕES E CONCEITOS PRELIMINARES Nos PPLs o que se busca é uma solução cujo valor no caso de minimização seja menor ou igual ao de qualquer outra solução viável Uma tal solução recebe o nome de solução ótima Nos problemas nãolineares estas soluções serão denominadas ótimos globais uma vez que alguns problemas em particular aqueles com funções não convexas também possuem soluções que são ótimos locais isto é são ótimas em uma determinada região do espaço de solução mas têm valor inferior ao de um ótimo global Definição 3 mínimo global Um ponto 𝑥 é um mínimo global de 𝑓𝑥 em 𝑋 ℝ𝑛 se 𝑓𝑥 𝑓𝑥 para todo 𝑥 𝑋 Definição 4 mínimo local Um ponto 𝑥 é um mínimo local de 𝑓𝑥 em 𝑋 ℝ𝑛 se existe uma vizinhança 𝒩𝑥 𝑋 tal que 𝑓𝑥 𝑓𝑥 para todo 𝑥 𝒩𝑥 18 DEFINIÇÕES E CONCEITOS PRELIMINARES A vizinhança 𝒩𝑥 de uma dada solução 𝑥 pode ser definida por exemplo pelos pontos 𝑥 𝑥1 𝑥2 𝑥𝑛𝑇 para os quais 𝑥𝑖 𝑥𝑖 𝜀 𝑖 1 𝑛 A Figura 5a ilustra uma função na qual existe um único mínimo local que portanto é também um mínimo global Isso quer dizer que um método para otimização local de problemas nãolineares encontraria esta solução se iniciado em uma solução apropriada Funções não convexas têm muitos mínimos locais como se vê na ilustração na Figura 5b Um mínimo local será dito estrito se para qualquer 𝜀 𝜀 verificase a desigualdade estrita 𝑓 𝑥 𝑓𝑥 para todo 𝑥 𝒩𝑥 𝒩𝑥 Ou seja podese tomar vizinhanças cada vez menores no entorno de 𝑥 e ainda assim ele será um mínimo local Na Figura 5c ilustrase uma função com múltiplos mínimos sendo três deles estritos e um platô com infinitas soluções igualmente ótimas 19 DEFINIÇÕES E CONCEITOS PRELIMINARES No curso de Cálculo a Uma Variável você aprendeu que a derivada primeira de 𝑓𝑥 deve se anular em um ponto de mínimo máximo isto é 𝑓 𝑥 0 Esta é uma condição necessária porém não suficiente para que um ponto seja mínimo máximo global de 𝑓𝑥 Por exemplo a função mostrada na Figura 3d possui um ponto estacionário 𝑥 que atende a condição 𝑓 𝑥 0 mas que não é mínimo de 𝑓𝑥 O Teorema4 expressa um resultado importante e que será usado repetidas vezes na solução de problemas de PNL funções convexas côncavas têm um único ponto de mínimo máximo local Logo um método que garanta a convergência para um ponto localmente ótimo é capaz de encontrar a solução ótima global Teorema4 Um mínimo máximo local 𝑥 de 𝑓 também será seu mínimo máximo global se 𝑓 for uma função convexa côncava em 𝑋 ℝ𝑛 20 DEFINIÇÕES E CONCEITOS PRELIMINARES Figura 5 Exemplos de funções em ℝ2 que não são côncavas nem convexas 21 OTIMIZAÇÃO LINEAR x NÃO LINEAR DIFERENÇAS Antes de analisar os problemas não lineares vale lembrar que um problema de Programação Linear PPL obedece quatro pressupostos básicos aditividade proporcionalidade fracionamento e certeza O primeiro destes pressupostos diz que a contribuição das variáveis de decisão à FO e às restrições é igual à soma das contribuições individuais O segundo expressa o fato de estas contribuições individuais são diretamente proporcionais ao nível de ativação das respectivas variáveis O terceiro pressuposto versa sobre a possibilidade das variáveis de decisão assumirem qualquer valor dentro de um intervalo ao invés de ficarem restritas a valores inteiros E por fim assumese que todos os dados de entrada são conhecidos com certeza É extremamente importante que o leitor compreenda cada uma destas premissas Se necessário consulte a um livro texto de Programação Linear 22 OTIMIZAÇÃO LINEAR x NÃO LINEAR DIFERENÇAS Dessas quatro hipóteses de modelagem apenas as duas primeiras não são aderentes aos modelos de PNL foco do presente estudo O pressuposto da aditividade por exemplo não se verifica no cálculo de diversas propriedades físico químicas de derivados de petróleo obtidos pela de mistura de correntes de derivados intermediários Na composição de carteiras de investimento é comum o uso de funções não lineares para se obter uma medida de risco associada ao conjunto de ativos selecionados Markowitz 1952 propôs um modelo pioneiro para esta finalidade no qual o risco da carteira é medidos por meio da variância do retorno dos ativos selecionados calculado como a soma das variâncias de cada ativo e das covariâncias entre pares de ativos 23 OTIMIZAÇÃO LINEAR x NÃO LINEAR DIFERENÇAS Por sua vez a hipótese de proporcionalidade não é aderente à modelagem dos custos variáveis de movimentação e manuseio em armazéns e centros de distribuições onde a presença de ganhos de escala fazem com que o custo variável total cresça a taxas decrescentes ao menos para um dado intervalo da quantidade de carga movimentada Economias de escala também estão presentes em sistemas de transporte que usam hubs na consolidação do fluxo cargas passageiros etc permitindo assim a redução dos custos unitários nos arcos entre hubs que via de regra empregam veículos de maior capacidade 24 OTIMIZAÇÃO LINEAR x NÃO LINEAR DIFERENÇAS Enquanto a adoção de premissas de modelagem distintas pode não parecer um grande desafio a solução de programas não lineares é tarefa bem mais árdua Uma das dificuldades se à eventual não convexidade das restrições que definem o conjunto de soluções viáveis ou da função objetivo Em problemas de PNL a interseção das restrições define um conjunto que pode ser não convexo ao contrário do que acontece nos PPLs em que as restrições lineares dão origem a semiespaços cuja interseção define um poliedro em ℝ𝑛 Uma função objetivo não convexa ou um conjunto solução não convexo produzem um problema extremamente difícil para o qual a obtenção de soluções ótimas pode ser computacionalmente muito custosa ou até intratável Mesmo a minimização maximização de uma função convexa côncava em um conjunto de solução convexo resulta em um problema de otimização bem mais difícil que um PPL 25 OTIMIZAÇÃO LINEAR x NÃO LINEAR DIFERENÇAS Outra peculiaridade dos problemas de PNL se refere localização das soluções ótimas dentro do conjunto viável Na presença de uma função objetivo ou de restrições não lineares não se pode garantir que as soluções ótimas ocorram na periferia da região viável como acontece em um PPL E muito menos garantir que sempre haverá ao menos uma solução ótima em um ponto extremo da região isto é em um vértice Os exemplos nas Figuras 6 7 e 8 ilustram as soluções ótimas de três problemas de PNL em duas variáveis Nas Figuras 6 e 7 são mostrados programas cuja solução ótima ocorre na fronteira mas não em um vértice da região viável No primeiro caso a solução ótima ocorre no ponto 𝑥 26𝑇 definido pela interseção da curva de nível 𝑧 6 com a restrição não linear 9𝑥1 2 5𝑥2 2 216 note que o gradiente da FO em 𝑥 26𝑇 é 𝑧 35𝑇 o que indica que os pontos de valor maior estão à direita da curva de nível 26 OTIMIZAÇÃO LINEAR x NÃO LINEAR DIFERENÇAS 𝑧 36 que não pertencem ao poliedro Logo não é possível aumentar o valor da FO caminhandose na direção de 𝑧 35𝑇 Nas Figuras 7 e 8 são ilustrados dois problemas de maximização em que a FO é côncava possuindo portanto um ponto de máximo Na Figura 7 notase que este ponto ocorre fora do conjunto solução e logo o ótimo fica definido pela interseção da curva de nível de maior valor que intercepta a região viável Ou seja da curva 𝑧 857 com a restrição 9𝑥1 2 5𝑥2 2 216 em 𝑥 Τ 8 3 5𝑇 Já o problema não linear mostrado na Figura 8 possui como ótimo o ponto de máximo da função𝑧 54𝑥1 9𝑥1 2 78𝑥2 13𝑥2 2 em ℝ2 isto é 𝑥 33𝑇 que ocorre no interior da região viável A partir destes três exemplos se conclui que qualquer algoritmo para obtenção de soluções ótimas para problemas de PNL deverá considerar todos os pontos da região viável e não apenas os da fronteira 27 OTIMIZAÇÃO LINEAR x NÃO LINEAR DIFERENÇAS Funções não convexas na definição da FO ou das restrições tornam a resolução dos programas ainda mais custosa muitas vezes inviabilizando a obtenção de soluções ótimas A Figura 9 apresenta um programa de PNL obtido pela substituição da segunda restrição do problema ilustrado na Figura 1 definido por uma função convexa pela restrição 𝑔2 𝑥 8𝑥1 𝑥1 2 14𝑥2 𝑥2 2 49 0 tal que 𝑔2𝑥 é uma função côncava A troca de apenas esta restrição faz com que o conjunto de soluções seja não convexo ao contrário dos três exemplos anteriores onde as funções convexas em cada restrição definem conjuntos convexos cuja interseção também é convexa 28 OTIMIZAÇÃO LINEAR E NÃO LINEAR DIFERENÇAS 29 Figura 6 Programa com restrições não lineares FO linear e solução ótima na fronteira viável Fonte Hillier Lieberman 2001 OTIMIZAÇÃO LINEAR E NÃO LINEAR DIFERENÇAS 30 Figura 7 Programa com FO não linear restrições lineares e solução na fronteira viável Fonte Hillier Lieberman 2001 OTIMIZAÇÃO LINEAR E NÃO LINEAR DIFERENÇAS 31 Figura 8 Programa com FO não linear restrições lineares e solução no interior da região viável Fonte Hillier Lieberman 2001 OTIMIZAÇÃO LINEAR E NÃO LINEAR DIFERENÇAS 32 Figura 9 Programa com FO linear restrições não lineares e solução em um vértice da região viável Fonte Hillier Lieberman 2001 CLASSES DE PROBLEMAS NÃOLINEARES Os problemas de PNL são divididos em subclasses de acordo com as não linearidades neles contidas As propriedades dos problemas em cada subclasse muitas vezes permitem que sejam desenvolvidas técnicas de solução específicas Abaixo as principais subclasses estão brevemente descritas Otimização Irrestrita compreende os problemas de PNL sem restrições Além das aplicações relevantes sua importância também se deve ao fato de que a solução de problemas restritos pode envolver a resolução de subproblemas irrestritos PNL com restrições lineares o conjunto de restrições nestes problemas é equivalente ao de um PPL havendo termos não lineares apenas na FO Alguns algoritmos especializados para este problema empregam extensões do método Simplex 33 CLASSES DE PROBLEMAS NÃOLINEARES Programação Quadrática é um caso especial dos problemas de PNL com restrições lineares em que a FO é quadrática ou seja definida por uma soma ou diferença de termos nos quais há o produto de duas variáveis ou o quadrado de uma das variáveis Nos casos em que esta função quadrática é côncava uma extensão direta do método Simplex é capaz de resolver o problema com baixo custo computacional Programação Convexa são problemas que envolvem a maximização minimização de uma a FO é côncava convexa sujeita a restrições convexas o que garante que um ótimo local também será global Compreende uma ampla classe de problemas de otimização inclusive as três citadas anteriormente Como se verá adiante neste caso as condições necessárias e suficientes para otimalidade são uma extensão natural daquelas usadas nos problemas irrestritos 34 CLASSES DE PROBLEMAS NÃOLINEARES Programação Separável tratase de um caso especial de programação convexa onde a FO 𝑓𝑥 pode ser escrita como a soma de funções de uma única variável isto é 𝑓 𝑥 σ𝑖1 𝑛 𝑓𝑖 𝑥𝑖 Algumas técnicas de solução tiram proveito desta estrutura particular para desenhar técnicas de solução eficientes Programação NãoConvexa inclui todos os problemas de PNL nos quais os pressupostos exigidos em problemas convexos não se aplicam Ou seja basta que uma das funções presentes no problema seja nãoconvexa para que ele pertença a esta classe No caso geral os algoritmos existentes são capazes de identificar ótimos locais mas não há condições suficientes para provar sua otimalidade global Alguns casos especiais de PNL não convexa como aqueles das duas classes seguintes podem ser resolvidos sem grande dificuldade por algoritmos especializados 35 CLASSES DE PROBLEMAS NÃOLINEARES Programação Geométrica são problemas nos quais a FO e as restrições são definidos por funções da forma 𝑓 𝑥 σ𝑖1 𝑛 𝑐𝑖𝑃𝑖𝑥 onde 𝑃𝑖 𝑥 𝑥1 𝑎1 𝑥2 𝑎2 𝑥𝑛 𝑎𝑛 sendo 𝑐𝑖 e 𝑎𝑖 constantes reais para 𝑖 1 𝑛 Problemas relevantes de projeto em engenharia são naturalmente modelados com funções deste tipo Nestas aplicações é usual que as variáveis 𝑥𝑖 representem decisões de projeto e os parâmetros 𝑎𝑖 sejam constantes físicas Nos casos em que as constantes 𝑐𝑖 são estritamente positivas é possível realizar uma transformação para obter um PNL convexo equivalente Programação Fracionária se a função objetivo for definida por uma razão isto é 𝑓𝑥 Τ 𝑓1 𝑥 𝑓2𝑥 é possível em alguns casos realizar uma transformação para obter um problema convexo No caso particular em que 𝑓1𝑥 e 𝑓2𝑥 são funções li 36 CLASSES DE PROBLEMAS NÃOLINEARES neares é possível transformar o programa fracionário em um PPL Também é possível obter um PNL convexo sempre que i 𝑓1𝑥 for côncava ii 𝑓2𝑥 for convexa e iii as funções g𝑖𝑥 que definem as restrições forem convexas PNLI e PNLIM são problemas de PNL em que parte as variáveis de decisão são inteiras A rigor qualquer programa com variáveis inteiras não é linear pois viola o pressuposto de fracionamento A denominação Programação Não Linear Inteira PNLI é dada à classe de problemas em que 𝑓 𝑥 e 𝑔𝑖𝑥 são função não lineares De forma análoga PNLIM define a classe de problemas não lineares em que parte apenas das variáveis é inteira A presença de funções não lineares e de variáveis inteiras define um problema de otimização extremamente custoso de ser resolvido especialmente se houver funções não convexas na formulação 37 CLASSES DE PROBLEMAS NÃOLINEARES Problema de Complementaridade consiste na obtenção de uma solução viável 𝑥 𝑦 ℝ2𝑛 que satisfaça 𝑥 𝐹𝑦 𝑥 0 𝑦 0 e 𝑥𝑇𝑦 0 esta última denominada de restrição de complementaridade da qual decorre que 𝑥𝑖 0 ou 𝑦𝑖 0 ou ambos para 𝑖 1 𝑛 𝐹 é uma função vetorial de 𝑦 Como não possui função objetivo o problema consiste em localizar uma solução viável para um sistema que contém ao menos uma equação não linear Esta equação é definida pela soma de termos bilineares isto é soma de termos iguais 𝑥𝑖𝑦𝑖 para 𝑖 1 𝑛 Uma caso especial de grande importância é o Problema Linear de Complementaridade no qual 𝐹𝑦 𝑞 𝑀𝑦 sendo 𝑞 um vetor coluna 𝑛 1 e 𝑀 uma matriz 𝑛 𝑛 Algoritmos eficientes existem para resolver este problema quando 𝑀 possui determinadas propriedades 38 CLASSES DE PROBLEMAS NÃOLINEARES As principais aplicações envolvem teoria dos jogos problemas de equilíbrio econômico e problemas de equilíbrio em engenharia assim como na resolução de problemas de programação quadrática 39 PROBLEMAS EM UMA VARIÁVEL Considere o problema de PNL irrestrita 1 onde 𝑓 𝑎 𝑏 ℝ min 𝑓𝑥 𝑥 𝑎 𝑏 1 Uma forma de encontrar o ótimo global de 𝑓𝑥 no intervalo 𝑎 𝑏 não necessariamente eficiente é identificar todos seus ótimos locais Obviamente se 𝑎 eou 𝑏 o ótimo global pode não existir como sugerem as Figuras 10a e 10b Mas se 𝑎 eou 𝑏 então o ótimo global poderá acontecer em 1 Pontos do intervalo 𝑎 𝑥 𝑏 onde 𝑓 𝑥 0 ditos pontos estacionários 2 Pontos onde 𝑓𝑥 não existe 3 Nos extremos do intervalo isto é em 𝑥 𝑎 ou 𝑥 𝑏 40 PROBLEMAS EM UMA VARIÁVEL Figura 10 Funções que não possuem mínimo ou máximo quando 𝑎 ou 𝑏 41 PROBLEMAS EM UMA VARIÁVEL CASO 1 O mínimo máximo 𝑥 é um ponto estacionário 𝑓 𝑥 0 no intervalo 𝑎 𝑏 Seja um ponto𝑥 𝑎 𝑏 tal que 𝑓 𝑥 existe Se𝑥 for um mínimo local então 𝑓 𝑥 0 Note ainda que 𝑓 muda de sinal em 𝑥 caso este seja um ótimo local Ou seja dada uma vizinhança 𝒩𝑥 tomandose 𝑥 𝒩𝑥 à esquerda de 𝑥 temse 𝑓 0 sendo que 𝑓 vai diminuindo até se anular em 𝑥 A partir daí 𝑓 0 e módulo 𝑓 volta a aumentar Procure verificar estas observações nas Figuras 11 e 12 Note porém que esta última ilustra o máximo local de uma função no entorno do qual o comportamento do sinal de 𝑓 é contrário ao verificado no entorno de um mínimo Antes de discutir o caso 2 é importante apresentar mais dois Teoremas Teorema 3 Se 𝑓𝑥 0 e 𝑓 𝑥 0 então 𝑥 é um mínimo local 42 PROBLEMAS EM UMA VARIÁVEL 43 Figura 11 Mudança no sinal de 𝑓𝑥 no entorno de um mínimo em ℝ PROBLEMAS EM UMA VARIÁVEL 44 Figura 12 Mudança no sinal de 𝑓𝑥 no entorno de um máximo em ℝ PROBLEMAS EM UMA VARIÁVEL Lembrese que se 𝑓 𝑥 0 então a concavidade da função no entorno de ҧ𝑥 é voltada para cima Analogamente se 𝑓 𝑥 0 a concavidade estará voltada para baixo Volte à Figura 3a para verificar esta propriedade E o que acontece se 𝑓 𝑥 0 e 𝑓 𝑥 0 como por exemplo na função 𝑓𝑥 3𝑥2 Neste caso usase o resultado apresentado no Teorema 4 Considere 𝑓𝑛𝑥 a derivada de ordem 𝑛 de 𝑓𝑥 em 𝑥 tal que 𝑓𝑛𝑥 0 e 𝑓𝑚 𝑥 0 para 𝑚 1 𝑛 1 Ou seja 𝑛 é a derivada de menor ordem cujo valor não é nulo em 𝑥 Teorema 4 Se 𝑓𝑥 0 e 𝑛 é ímpar então 𝑥 não é mínimo máximo local 𝑛 é par e 𝑓𝑛 𝑥 0 𝑓𝑛 𝑥 0 então 𝑥 é um mínimo máximo local 45 PROBLEMAS EM UMA VARIÁVEL CASO 2 O ponto de mínimo máximo 𝑥 ocorre em 𝑎 𝑏 mas 𝑓 não existe em 𝑥 Se o mínimo local acontece em um ponto 𝑥 onde 𝑓 não é diferenciável então será necessário avaliar 𝑓 em no entorno de 𝑥 Ou seja𝑥 será um mínimo local se 𝑓 𝑥1 𝑓 𝑥 e 𝑓 𝑥2 𝑓 𝑥 para 𝑥1 𝑥 e 𝑥2 𝑥 Ou seja tomados dois pontos quaisquer à esquerda e à direita de 𝑥 verificase se o valor de 𝑓 nestes pontos é maior que em 𝑥 Por exemplo a função 𝑓 𝑥 𝑥 4 2 para 𝑥 ℝ ilustrada na Figura 13 De forma análoga a caracterização de um ponto de máximo é obtida se invertendo as desigualdades em 𝑓 𝑥1 e 𝑓 𝑥2 Nos casos em que 𝑓 não está definida em todo o domínio a solução exata pode ser inviável sendo mais adequado o uso de procedimentos iterativos para aproximar 𝑥 46 PROBLEMAS EM UMA VARIÁVEL 47 Figura 13 Mínimo em um ponto onde a derivada primeira não existe PROBLEMAS EM UMA VARIÁVEL CASO 3 O ponto de mínimo ҧ𝑥 ocorre nos extremos isto é 𝑥 𝑎 ou 𝑥 𝑏 Os extremos 𝑥 𝑎 e 𝑥 𝑏 serão candidatos a mínimo respectivamente se 𝑓 𝑎 0 e 𝑓 𝑏 0 Analogamente se o problema consistir na identificação do máximo então os extremos serão candidatos se 𝑓 𝑎 0 e 𝑓 𝑏 0 As Figuras 14a e 14b ilustram funções que possuem mínimo ou máximo em um extremo finito do intervalo Este exemplo a seguir ilustra estes três casos na identificação do máximo de uma função Exemplo 1 O lucro de uma operação industrial é calculado em função da quantidade produzida 𝑥 ton tal que 0 𝑥 15 Seu custo de produção é de 10 ton e o preço de venda de cada tonelada cai com a quantidade ofertada no mercado sendo estimado como em 20 𝑥 ton Determine a quantidade que maximiza o lucro da operação 48 PROBLEMAS EM UMA VARIÁVEL 49 Figura 14 Mínimo e máximos nos extremos do intervalo 𝑎 𝑏 a b b PROBLEMAS EM UMA VARIÁVEL Resolução O lucro total desta operação é dado pela função 𝐿𝑥 definida pela diferença entre a receita total e o custo total Ou seja 𝐿 𝑥 20 𝑥 𝑥 10𝑥 𝑥2 10𝑥 Portanto o PNL a ser resolvido é min 𝐿 𝑥 𝑥2 10𝑥 s a 0 𝑥 15 Os pontos candidatos a máximo são CASO1 Note que 𝐿𝑥 é definida em todos os pontos do intervalo 0 𝑥 15 e calculada como 𝐿 𝑥 2𝑥 10 A condição necessária para 𝑥 neste intervalo seja um 50 PROBLEMAS EM UMA VARIÁVEL ponto de máximo é 𝐿 𝑥 0 Logo 2𝑥 10 0 𝑥 5 Como 𝐿 𝑥 2 𝑥 5 é um máximo local no intervalo 0 𝑥 15 e corresponde a um lucro 𝐿 5 25 CASO 2 Como 𝐿𝑥 é diferenciável no intervalo 0 𝑥 15 então este caso não se aplica ao problema em questão CASO 3 Nos extremos do intervalo as derivadas valem 𝐿0 10 e 𝐿15 75 Como 𝐿 0 0 e 𝐿 30 0 os extremos não são candidatos a máximos locais 51 PROBLEMAS EM UMA VARIÁVEL Avaliados os três casos possíveis o único máximo local encontrado foi 𝑥 5 Observe ainda que 𝐿𝑥 2 para todo 𝑥 real o que garante que 𝐿𝑥 é uma função côncava Logo o máximo local identificado é também um ótimo global 𝑥 do problema O gráfico de 𝐿𝑥 é apresentado na Figura 15 Note que para valores superiores a 10 toneladas o lucro se torna negativo Exemplo 2 Resolva o seguinte PNL max 𝑓 𝑥 0 𝑥 6 onde 𝑓 𝑥 ൝ 2 𝑥 1 2 0 𝑥 3 3 𝑥 4 2 3 𝑥 6 A Figura 16 ilustra o gráfico de 𝑓𝑥 52 PROBLEMAS EM UMA VARIÁVEL 53 Figura 15 Função lucro a ser otimizada no exemplo 1 PROBLEMAS EM UMA VARIÁVEL 54 Figura 16 Função lucro a ser otimizada no exemplo 1 PROBLEMAS EM UMA VARIÁVEL Resolução Novamente serão analisados os três casos CASO 1 Pontos estacionários candidatos No intervalo 0 𝑥 3 têmse 𝑓 𝑥 2 𝑥 12 2 𝑥 1 e logo 𝑓𝑥 2 Fazendose 𝑓𝑥 0 obtémse 2 𝑥 1 0 𝑥 1 Portanto 𝑥 1 é um ponto de máximo uma vez que 𝑓 𝑥 0 55 PROBLEMAS EM UMA VARIÁVEL No intervalo 3 𝑥 6 têmse 𝑓 𝑥 3 𝑥 42 2 𝑥 4 e logo 𝑓𝑥 2 Fazendose 𝑓𝑥 0 obtémse 2 𝑥 4 0 𝑥 4 Logo 𝑥 4 é um ponto de mínimo pois 𝑓 𝑥 0 Portanto no intervalo 0 𝑥 6 apenas o ponto estacionário 𝑥 1 é máximo sendo seu valor igual 𝑓1 2 56 PROBLEMAS EM UMA VARIÁVEL CASO 2 Pontos candidatos onde 𝑓 não existe A derivada primeira de 𝑓𝑥 𝑓𝑥 não existe no ponto 𝑥 3 Para comprovar isso calcule as derivadas laterais e verifique que elas são diferentes Para 𝑥 3 𝑥 tendendo a 3 pela esquerda 𝑓 3 4 Para 𝑥 3 tendendo a 3 pela direita 𝑓3 2 Como 𝑓 3 𝑓 3 𝑓𝑥 não existe em 𝑥 3 Neste caso para verificar se este é um máximo local basta avaliar 𝑓𝑥 em no entorno de 𝑥 3 Se dessa avaliação se conclui que 𝑓𝑥 𝑓𝑥1 e 𝑓𝑥 𝑓𝑥2 para todo 𝑥1 e 𝑥2 tal que 𝑥1 𝑥 𝑥2 então 𝑥 3 será um máximo Porém 57 PROBLEMAS EM UMA VARIÁVEL Se 𝑥1 29 e 𝑥2 31 𝑓 3 2 𝑓 29 161 𝑓 3 2 𝑓 31 219 Logo 𝑥 3 não é um máximo nem mínimo local CASO 3 Extremos do intervalo como pontos candidatos Como 𝑓0 2 0 𝑥 0 é um mínimo local E sendo 𝑓6 4 0 concluise que 𝑥 6 é um máximo local cujo valor é 𝑓 6 1 Portanto no intervalo 0 𝑥 6 há dois máximos locais 𝑥 1 e 𝑥 6 cujos valores são 𝑓1 2 e 𝑓6 1 Concluise assim que o ótimo global do problema é 𝑥 1 58 O MÉTODO DA SEÇÃO ÁUREA A estratégia empregada na solução dos programas dos exemplos 1 e 2 tem algumas limitações para aplicação em qualquer PNL da forma 1 A primeira delas se refere à resolução de 𝑓 𝑥 0 que pode resultar em uma equação não linear cuja solução analítica não seja possível ou que seja computacionalmente cara de se obter por métodos numéricos Outra dificuldade se refere à localização de mínimos quando 𝑓𝑥 não existir em 𝑥 Nos casos em que 𝑓𝑥 é uma função unimodal é possível empregar métodos para aproximar a solução ótima de 1 Definição 5 Uma função 𝑓𝑥 é unimodal no intervalo 𝑎 𝑏 se é estritamente crescente no intervalo 𝑎 𝑥 e estritamente decrescente no intervalo 𝑥 𝑏 59 O MÉTODO DA SEÇÃO ÁUREA Em outras palavras uma função 𝑓𝑥 é unimodal em 𝑎 𝑏 se possuir um único máximo mínimo local neste intervalo que portanto também é seu ótimo global As Figuras 3a 4b e 5a ilustram funções unimodais ao contrário das Figuras 4a e 5bc Na Figura 4a a definição 5 é violada porque à direita do mínimo a ela não é estritamente crescente enquanto nas Figuras 5bc há múltiplos pontos de mínimo e máximo O método da seção áurea se baseia na construção de subintervalos do intervalo original 𝑎 𝑏 que contenham a solução ótima sendo que o subintervalo obtido em cada iteração do algoritmo está estritamente contido naquele obtido na iteração anterior Ou seja dado 𝑥 𝑎 𝑏 obtémse 𝑐 𝑑 𝑐 𝑑 𝑎 𝑏 tal que que 𝑥 𝑐 𝑑 Para isso avaliase 𝑓𝑥 em dois pontos 𝑥1 e 𝑥2 do intervalo 𝑎 𝑏 tal que 𝑥1 𝑥2 60 O MÉTODO DA SEÇÃO ÁUREA Da avaliação de 𝑓𝑥 em 𝑥1 e 𝑥2 resultam três casos possíveis CASO 1 𝑓 𝑥1 𝑓 𝑥2 𝑥 𝑥1 𝑏 CASO 2 𝑓 𝑥1 𝑓 𝑥2 𝑥 𝑥1 𝑥2 CASO 3 𝑓 𝑥1 𝑓 𝑥2 𝑥 𝑎 𝑥2 A Figura 16 ilustra para três funções unimodais em ℝ2 as possíveis relações entre os valores de 𝑓 𝑥1 e 𝑓 𝑥2 e os correspondentes intervalos de incerteza que contém a solução ótima Uma vez que o caso 2 raramente ocorre podese incorporálo em um dos outros dois 61 O MÉTODO DA SEÇÃO ÁUREA Uma vez identificado o intervalo de incerteza calculamse os novos valores de 𝑥1 e 𝑥2 com base nos seus limites inferior e superior e o processo é repetido na próxima iteração Podese dizer portanto que o método da seção áurea resolve o problema de PNL 1 através de reduções sucessivas do intervalo de incerteza até que a solução seja aproximada com uma dada precisão 𝜀 0 A redução do intervalo de incerteza em cada iteração do método mantém razão áurea entre as partes deste intervalo Em matemática duas quantidades estão em razão áurea quando a razão de sua soma dividida pela maior delas for igual a razão desta última pela menor das quantidades Para reduzir o intervalo de incerteza com base na proporção áurea considere que ele tenha sido dividido em duas partes com comprimentos 𝑙𝑎 e 𝑙𝑏 tal que 𝑙𝑎 𝑙𝑏 como sugere a Figura 17 62 O MÉTODO DA SEÇÃO ÁUREA Estes segmentos estarão em proporção áurea se 𝑙𝑎𝑙𝑏 𝑙𝑎 𝑙𝑎 𝑙𝑏 φ 2 onde φ é o valor da razão áurea Das igualdades em 2 decorre que 𝑙𝑎𝑙𝑏 𝑙𝑎 𝑙𝑎 𝑙𝑎 𝑙𝑏 𝑙𝑎 1 𝑙𝑏 𝑙𝑎 1 1 φ φ 3 63 𝑙𝑎 𝑙𝑏 Figura 17 Divisão do intervalo de incerteza com a proporção áurea 1 O MÉTODO DA SEÇÃO ÁUREA E da última igualdade em 3 obtémse a seguinte equação do segundo grau em φ φ2 φ 1 0 4 cujas raízes são φ 1 5 2 e φ 1 5 2 Uma vez queφ 0 entãoφ 1 5 2 16180339 A este número irracional dá se o nome de razão áurea Nos desenvolvimentos que seguem esta razão será expressa pelo seu inverso 𝛼 Τ 1 𝜑 51 2 06180339 64 O MÉTODO DA SEÇÃO ÁUREA Para determinar 𝑥1 e 𝑥2 onde 𝑓𝑥 será avaliada fazse 𝑥1 𝑏 𝛼𝑏 𝑎 e 𝑥2 𝑎 𝛼𝑏 𝑎 5 ou seja a partir do limite superior do intervalo 𝑏 definese um novo ponto 𝑥1 subtraindo uma fração 𝛼 do comprimento do intervalo Analogamente somase esta mesma fração do comprimento ao limite inferior 𝑎 para definir 𝑥2 Na sequência verificase qual dos dois casos anteriores se aplica CASO 1 𝑓 𝑥1 𝑓𝑥2 então o novo intervalo de incerteza será 𝑥1 𝑏 cujo comprimento cai para 𝑏 𝑥1 𝛼 𝑏 𝑎 e os novos pontos intermediários serão 𝑥3 𝑏 𝛼 𝑏 𝑥1 𝑏 𝛼2𝑏 𝑎 e 𝑥4 𝑥1 𝛼𝑏 𝑥1 6 65 O MÉTODO DA SEÇÃO ÁUREA É interessante notar que o novo limite inferior esquerdo 𝑥3 é igual ao antigo limite superior direito 𝑥2 Para verificar isso lembre que 𝜑2 1 𝜑 Logo 1 𝛼 2 1 1 𝛼 1 𝛼2 𝛼 𝛼2 1 𝛼 De volta à expressa 6 que define 𝑥3 𝑥3 𝑏 𝛼 𝑏 𝑥1 𝑏 𝛼2 𝑏 𝑎 𝑏 1 𝛼 𝑏 𝑎 𝑎 𝛼 𝑏 𝑎 𝑥2 66 O MÉTODO DA SEÇÃO ÁUREA CASO 2 𝑓 𝑥1 𝑓𝑥2 o intervalo de incerteza será atualizado para 𝑎 𝑥2 e da mesma forma seu comprimento reduzirá para 𝑥2 𝑎 𝛼 𝑏 𝑎 E os novos limites serão 𝑥3 𝑥2 𝛼 𝑥2 𝑎 e 𝑥4 𝑎 𝛼 𝑥2 𝑎 𝑎 𝛼2𝑏 𝑎 7 Substituindo 𝛼2 1 𝛼 em 7 a expressão que define 𝑥4 fica 𝑥4 𝑎 𝛼2 𝑏 𝑎 𝑎 1 𝛼 𝑏 𝑎 𝑏 𝛼 𝑏 𝑎 𝑥1 Ou seja o novo limite superior direito 𝑥4 é igual ao antigo limite inferior esquerdo 𝑥1 67 O MÉTODO DA SEÇÃO ÁUREA Em resumo na iteração 𝑘 verificase qual o aplicável e para então determinar o novo intervalo de incerteza dado pelos novos limites inferior e superior e os novos pontos que serão testados na iteração seguinte 𝑘 1 CASO 1 𝑓 𝑥2𝑘1 𝑓𝑥2𝑘2 𝑎𝑘1 𝑥2𝑘1 𝑏𝑘1 𝑏𝑘 𝑥2𝑘3 𝑥2𝑘2 novo pt esquerdo antigo pt direito 𝑥2𝑘4 𝑎𝑘1 𝛼 𝑏𝑘1 𝑎𝑘1 CASO 2 𝑓 𝑥2𝑘1 𝑓𝑥2𝑘2 𝑎𝑘1 𝑎𝑘 𝑏𝑘1 𝑥2𝑘2 𝑥2𝑘3 𝑏𝑘1 𝛼 𝑏𝑘1 𝑎𝑘1 𝑥2𝑘4 𝑥2𝑘1 novo pt direiro antigo pt esquerdo 68 CONVERGÊNCIA DO MÉTODO O método para quando o comprimento do subintervalo na 𝑘ésima iteração 𝐿𝑘 for menor que uma dada precisão préestabelecida 𝜀 Note que a aplicação da razão áurea em cada iteração produz um subintervalo de comprimento aproximadamente igual a uma fração 𝛼 do comprimento do subintervalo anterior Ou seja na primeira iteração gerase um subintervalo de comprimento 𝐿1 𝛼 𝑏 𝑎 Um subintervalo de comprimento 𝐿2 𝛼𝐿1 𝛼2 𝑏 𝑎 é gerado na segunda iteração E assim na 𝑘ésima iteração será obtido um subintervalo de comprimento 𝐿𝑘 𝛼𝑘 𝑏 𝑎 O critério de parada do método pode então ser definido como 𝐿𝑘 𝛼𝑘 𝑏 𝑎 𝜀 Isso quer dizer que o método converge linearmente a taxa de convergência aproximadamente igual a 𝛼 69 CONVERGÊNCIA DO MÉTODO E quantas iterações seriam necessárias para o método parar dada uma precisão 𝜀 Para responder a esta questão é preciso retornar ao critério de convergência anterior Seja 𝐿0 o comprimento inicial do intervalo Se o método parar na késima iteração então o comprimento do subintervalo será 𝐿0𝛼𝑘 𝜀 𝛼𝑘 𝜀 𝐿0 log 𝛼𝑘 log 𝜀 𝐿0 𝑘 log 𝛼 log 𝜀 𝐿0 𝑘 log 𝛼1 log 𝐿0 𝜀 70 CONVERGÊNCIA DO MÉTODO Por simplicidade de notação seja 𝐶 log 1 𝛼 1 Logo como 𝑘 é um inteiro 𝑘 𝐶 log 𝐿 𝜀 8 Fazendo uso da notação assintótica podese escrever 𝑘 é da ordem de log 1 𝜀 ou simplesmente 𝛰 log Τ 1 𝜀 Portanto devese avaliar qual a precisão realmente requerida para se evitar um número proibitivo de iterações Ainda em tempo é preciso discutir a precisão do método Em primeiro lugar note que 𝑓𝑥 é achatada no entorno do ótimo o que pode comprometer a precisão com a qual se pode detectar 𝑓 𝑥 Por isso a precisão é analisada em termos do erro relativo 71 CONVERGÊNCIA DO MÉTODO Erros relativos menores que a precisão da máquina 𝛿 não são detectados Ou seja 𝑓 𝑥 𝑓𝑥 𝑓𝑥 𝛿 9 Antes de prosseguir considere a aproximação de 𝑓𝑥 por Séries de Taylor no entorno de 𝑥 até o termo de segunda ordem1 𝑓𝑥 𝑓 𝑥 1 2 𝑓 𝑥 𝑥 𝑥2 10 De volta a expressão 9 temse 1 2 𝑓 𝑥 𝑥 𝑥2 𝛿 𝑓𝑥 11 72 1 Assumese aqui que 𝑓𝑥 seja diferenciável em 𝑥 CONVERGÊNCIA DO MÉTODO Ou equivalentemente 𝑥 𝑥 𝛿 2 𝑓𝑥 𝑓𝑥 12 E logo o desvio relativo em relação a 𝑥 será 𝑥 𝑥 𝑥 𝛿 2 𝑓𝑥 𝑥2𝑓𝑥 13 Para muitas funções a constante na segunda raiz é da ordem da unidade E mesmo que esta hipótese não seja válida podese transformar 𝑓𝑥 sem alterar seu mínimo 73 CONVERGÊNCIA DO MÉTODO Com isso é possível escrever 𝑥 𝑥 𝛿 𝑥 14 Ou seja a menor precisão com qual se consegue localizar 𝑥 é aproximadamente a raiz quadrada da precisão da máquina 𝛿 vezes o valor de 𝑥 Portanto é inútil tentar reduzir o intervalo de confiança a um tamanho menor que 𝛿 𝑥 74 O MÉTODO DA SEÇÃO ÁUREA Exemplo 1 Encontre aproxime um ótimo local de 𝑓 𝑥 𝑥4 14𝑥3 60𝑥2 70𝑥 no intervalo 02 dada uma precisão de 𝜀 01 Assuma 𝛼 0618 Resolução A Figura 18 apresenta a ilustração de 𝑓𝑥 a Tabela 1 traz a memória de cálculo 75 O MÉTODO DA SEÇÃO ÁUREA Tabela 1 Iterações do método da seção áurea no exemplo 1 para 𝜀 01 76 k ak bk Lk xk1 xk2 fx2k1 fx2k2 CASO 0 0 2 2 0764 1236 24361 18960 2 1 0 1236 1236 0472 0764 21095 24361 1 2 0472 1236 0764 0764 0944 24361 23595 2 3 0472 0944 0472 0652 0764 23833 24361 1 4 0652 0944 0292 0764 0832 24361 24290 2 5 0652 0832 0180 0721 0764 24247 24361 1 6 0721 0832 0111 0764 0790 24361 24367 1 7 0764 0832 0068 O MÉTODO DA SEÇÃO ÁUREA É usual que solução seja aproximada pelo ponto médio do subintervalo obtido na última iteração 𝑘 quando a condição de parada for verificada Mas também é possível usar como estimativa um dos pontos testados na iteração anterior 𝑥2𝑘1 e 𝑥2𝑘 Neste exemplo para uma precisão de 𝜀 001 o método para na sétima iteração Tomandose o ponto médio do subintervalo como estimativa obtémse ҧ𝑥 07640832 2 0798 cujo valor é 24361 Note porém que esta aproximação tem valor pior ou seja maior que o ponto direito testado na iteração anterior 𝑥12 0790 que vale 24367 Este ponto pode então ser usado como aproximação de 𝑥 Se a precisão for reduzida para 𝜀 0005 serão necessárias mais 5 iterações para obter uma aproximação pelo ponto médio igual ҧ𝑥 0781 de valor 24370 A Tabela 2 apresenta a memória de cálculo destas 5 iterações adicionais 77 O MÉTODO DA SEÇÃO ÁUREA 78 k ak bk Lk xk1 xk2 fx2k1 fx2k2 CASO 7 0764 0832 0068 0790 0806 24367 24350 2 8 0764 0806 0042 0780 0790 24370 24367 2 9 0764 0790 0026 0774 0780 24368 24370 1 10 0774 0790 0016 0780 0784 24370 24369 2 11 0774 0784 0010 0778 0780 24369 24370 1 12 0778 0784 0006 Tabela 2 Iterações adicionais do método da seção áurea no exemplo 1 para 𝜀 0005 CONSIDERAÇÕES FINAIS Existem outros algoritmos para aproximar o mínimo de um problema de otimização em uma dimensão como por exemplo o método da bissecção Assim como este último o método da seção áurea é lento porém robusto Por esta razão ele é muitas vezes usado como uma subrotina associada à execução de outros algoritmos mais eficientes quando estes falham Outro fato que reforça a importância dos métodos para busca unidimensional é seu uso como subrotina de alguns algoritmos para otimização em várias variáveis Nestes algoritmos uma direção de pesquisa é determinada para então se realizar uma busca unidimensional cujo objetivo é calcular o passo a ser ao longo da direção obtida 79 BIBLIOGRAFIA Bazaraa M H Sherali and C Shetty Nonlinear Programming Theory and Algorithms New York John Wiley 1993 Hillier FS Lieberman GJ Introduction to Operations Research MacGrawHill 2001 Press WH Teukolsky SA Vetterling WT Flannery BP Numerical recipes in C the art of scientific computing Cambridge University Press 1997 Taha HA Pesquisa Operacional 8 ed Pearson Prentice Hall 2008 Winston W Operations Reseach Applications and Algorithms Duxbury Press 2003 80