Algoritmos de otimização de recursos | Construpedia
Navegación
Algoritmos de otimização de recursos
Introdução
Em geral
Em matemática, estatística, economia, ciências empíricas e ciência da computação, otimização (também, otimização matemática ou programação matemática) é a seleção do melhor elemento (com relação a algum critério) de um conjunto de elementos disponíveis. A pesquisa operacional é um dos campos da matemática com base no qual a otimização funciona.[1].
No caso mais simples, um problema de otimização consiste em maximizar ou minimizar uma função real escolhendo sistematicamente valores de entrada (retirados de um conjunto permitido) e calculando o valor de “Magnitude (matemática)” da função. A generalização da teoria e técnicas de otimização para outras formulações compreende uma grande área da matemática aplicada. Em termos gerais, a otimização inclui a descoberta dos "melhores valores" de alguma função objetivo dado um domínio definido, incluindo uma variedade de diferentes tipos de funções objetivo e diferentes tipos de domínios.
Otimização refere-se à ação e efeito da otimização. Em termos gerais, refere-se à capacidade de fazer ou resolver algo da forma mais eficiente possível e, na melhor das hipóteses, utilizando o mínimo de recursos.
Nas últimas décadas, o termo otimização tem sido associado ao mundo da computação. No entanto, é um conceito que também é utilizado em matemática, gestão de processos e economia.
Problemas de otimização
Um problema de otimização pode ser representado da seguinte forma:
Tal formulação é chamada de problema de otimização ou problema de programação matemática (um termo não diretamente relacionado à programação de computadores, mas ainda em uso, por exemplo, na programação linear - consulte a seção História). Muitos problemas teóricos e do mundo real podem ser modelados usando este esquema geral. Problemas formulados com esta técnica nas áreas de física e visão computacional referem-se à técnica como minimização de energia, falando do valor da função f que representa a energia do sistema que está sendo modelado.
Normalmente, A é algum subconjunto do espaço euclidiano R, muitas vezes limitado por um conjunto de restrições, igualdades ou desigualdades "Restrição (matemática)" que os elementos de devem satisfazer. O domínio de é chamado de ou , enquanto os elementos de são chamados de soluções candidatas ou .
Algoritmos de otimização de recursos
Introdução
Em geral
Em matemática, estatística, economia, ciências empíricas e ciência da computação, otimização (também, otimização matemática ou programação matemática) é a seleção do melhor elemento (com relação a algum critério) de um conjunto de elementos disponíveis. A pesquisa operacional é um dos campos da matemática com base no qual a otimização funciona.[1].
No caso mais simples, um problema de otimização consiste em maximizar ou minimizar uma função real escolhendo sistematicamente valores de entrada (retirados de um conjunto permitido) e calculando o valor de “Magnitude (matemática)” da função. A generalização da teoria e técnicas de otimização para outras formulações compreende uma grande área da matemática aplicada. Em termos gerais, a otimização inclui a descoberta dos "melhores valores" de alguma função objetivo dado um domínio definido, incluindo uma variedade de diferentes tipos de funções objetivo e diferentes tipos de domínios.
Otimização refere-se à ação e efeito da otimização. Em termos gerais, refere-se à capacidade de fazer ou resolver algo da forma mais eficiente possível e, na melhor das hipóteses, utilizando o mínimo de recursos.
Nas últimas décadas, o termo otimização tem sido associado ao mundo da computação. No entanto, é um conceito que também é utilizado em matemática, gestão de processos e economia.
Problemas de otimização
Um problema de otimização pode ser representado da seguinte forma:
Tal formulação é chamada de problema de otimização ou problema de programação matemática (um termo não diretamente relacionado à programação de computadores, mas ainda em uso, por exemplo, na programação linear - consulte a seção História). Muitos problemas teóricos e do mundo real podem ser modelados usando este esquema geral. Problemas formulados com esta técnica nas áreas de física e visão computacional referem-se à técnica como minimização de energia, falando do valor da função que representa a energia do sistema que está sendo modelado.
A
A
f
espaço de busca
conjunto de escolhas
A
soluções viáveis
A função f é chamada, de várias maneiras, de função objetivo, função de custo (minimização),[2] função de utilidade (maximização), função de utilidade indireta (minimização),[3] ou, em certos campos, função de energia, ou funcional de energia "Funcional (matemática)"). Uma solução viável que minimiza (ou maximiza, se este for o propósito) a função objetivo é chamada de solução ótima.
Por convenção, o formato padrão de um problema de otimização é expresso em termos de minimização. Geralmente, a menos que tanto a função objetivo quanto a região viável sejam convexas em um problema de minimização, pode haver vários mínimos locais, onde um mínimo local x é definido como um ponto para o qual existe algum δ > 0, onde para todo x tal que.
a expressão.
é verdade; Ou seja, em alguma região em torno de x, todos os valores da função são maiores ou iguais ao valor naquele ponto. O máximo local é definido de forma semelhante.
Um grande número de algoritmos propostos para resolver problemas não-convexos – incluindo a maioria dos solucionadores disponíveis comercialmente – não são capazes de fazer uma distinção entre soluções ótimas locais e soluções ótimas rigorosas, e tratar as primeiras como soluções atuais do problema original. O ramo da matemática aplicada e da análise numérica responsável pelo desenvolvimento de algoritmos determinísticos capazes de garantir a convergência em tempo finito para a solução ótima real de um problema não convexo é denominado otimização global.
Notação
Contenido
Los problemas de optimización se expresan a menudo con una notación especial. A continuación se muestran algunos ejemplos.
Valor mínimo e máximo de uma função
Considere a seguinte notação:
Isso denota o valor mínimo de "Magnitude (matemática)") da função objetivo, quando x é selecionado do conjunto de números reais. O valor mínimo neste caso é e ocorre para .
Da mesma forma, a notação.
expressa o valor máximo da função objetivo 2x, onde x é qualquer número real. Neste caso, não existe tal máximo, portanto não existe um valor ótimo limitado.
Argumentos para entrada ideal
Considere a seguinte expressão:
ou equivalente.
Isto representa o valor (ou valores) do argumento "Argumento (análise complexa)") de x no intervalo "Intervalo (matemática)") que minimiza (ou maximiza) a função objetivo x + 1 (e não o valor mínimo que a função objetivo atinge para esses valores). Neste caso, a resposta é x = -1, pois x = 0 não é viável, ou seja, não pertence ao domínio do problema.
De forma similar,
que equivale a.
representa o par (ou pares) (x,y) que minimiza (ou maximiza) o valor da função objetivo xcos(y), com a restrição adicional de que x está no intervalo [-5,5] (novamente, o valor mínimo da função não importa). Neste caso, as soluções são os pares da forma (5, 2kπ) e (−5,(2k+1)π), onde k percorre todos os inteiros.
Arg min e arg max às vezes são escritos como argmin e argmax, significando argumento mínimo e argumento máximo.
História
Pierre de Fermat e Joseph Louis Lagrange encontraram fórmulas baseadas em cálculo para identificar valores ótimos, enquanto Isaac Newton e Carl Friedrich Gauss propuseram métodos iterativos para aproximar o ótimo. Historicamente, o termo programação linear para se referir a certos problemas de otimização é devido a George B. Dantzig, embora grande parte da teoria tenha sido introduzida por Leonid Kantorovich em 1939. Dantzig publicou o Algoritmo Simplex em 1947 e John von Neumann desenvolveu a teoria da dualidade "Dualidade (matemática)") no mesmo ano.
O termo programação neste contexto não se refere à programação de computadores. Em vez disso, o termo vem do uso de programa pelos militares dos Estados Unidos quando se referem à proposta de treinamento e planejamento logístico, que era o problema estudado por Dantzig na época.
Outros pesquisadores importantes na área de otimização matemática foram os seguintes:
Classificação de pontos críticos e extremos
Viabilidade do problema
A solubilidade do problema, também chamada de viabilidade do problema, é a questão de saber se existe alguma solução viável, independentemente do seu valor objetivo. Este pode ser considerado o caso especial de otimização matemática onde o valor objetivo é o mesmo para todas as soluções e, portanto, qualquer solução é ótima.
Muitos algoritmos de otimização precisam começar de um ponto viável. Uma forma de obter tal ponto é relaxar as condições de viabilidade utilizando uma variável de folga; Com folga suficiente, qualquer ponto de partida é viável. Então, essa variável de folga é minimizada até que a folga seja zero ou negativa.
Existência
O teorema de Weierstrass afirma que uma função real e contínua em um conjunto compacto atinge seu valor máximo e mínimo. De forma mais geral, uma função semicontínua inferior em um conjunto compacto atinge seu mínimo; uma função semicontínua superior em um conjunto compacto atinge seu máximo.
Condições necessárias de otimalidade
Um dos teoremas de Fermat garante que os ótimos de problemas irrestritos são encontrados em pontos estacionários, onde a primeira derivada da função objetivo é zero (ou seu gradiente nulo). Mais geralmente, eles também podem ser encontrados em pontos críticos onde a primeira derivada ou gradiente da função objetivo não está definida, ou no limite da "Fronteira (topologia)" do conjunto de escolha. Uma equação (ou conjunto de equações) indicando que a(s) primeira(s) derivada(s) é(são) igual(es) a zero em um ótimo interior é chamada de condição de primeira ordem ou um conjunto de condições de primeira ordem.
Os ótimos de problemas com restrições de desigualdade são encontrados pelo método dos multiplicadores de Lagrange. Este método calcula um sistema de desigualdades chamado condições de Karush – Kuhn – Tucker ou condições de folga complementar, que são então usadas para calcular o ótimo.
Condições de otimalidade suficientes
Embora o teste da primeira derivada identifique pontos que podem ser extremos, este teste não distingue se um ponto é mínimo, máximo ou nenhum dos dois. Quando a função objetivo é duas vezes diferenciável, esses casos podem ser distinguidos estudando a segunda derivada ou a matriz das segundas derivadas (chamada de matriz Hessiana), em problemas irrestritos, ou a matriz das segundas derivadas da função objetivo e as restrições chamada de matriz Hessiana com borda, em problemas restritos.
As condições que distinguem máximos ou mínimos de outros pontos estacionários são chamadas de condições de segunda ordem. Se uma solução candidata satisfizer as condições de primeira ordem e também as condições de segunda ordem, é suficiente estabelecer, pelo menos, a otimalidade local.
Sensibilidade e continuidade ideais
O teorema do envelope descreve como o valor de uma solução ótima muda quando um parâmetro subjacente muda. O processo que calcula essa mudança é chamado de estática comparativa.
O teorema do máximo de Claude Berge (1963) descreve a continuidade de uma solução ótima em função dos parâmetros subjacentes.
Cálculos de otimização
Para problemas irrestritos com funções duas vezes diferenciáveis, alguns pontos críticos "Ponto crítico (matemática)") podem ser encontrados detectando os pontos onde o gradiente da função objetivo é zero (ou seja, os pontos estacionários). Mais geralmente, um subgradiente zero certifica que um mínimo local foi encontrado para problemas de minimização com funções convexas ou outras funções de Lipschitz.
Além disso, os pontos críticos podem ser classificados usando a definição da matriz Hessiana: se for definido positivo em um ponto crítico, então o ponto é um mínimo local; se for definido negativo, então o ponto é um máximo local; finalmente, se for indefinido, então o ponto é algum tipo de ponto de sela.
Problemas restritos muitas vezes podem ser transformados em problemas irrestritos com a ajuda dos multiplicadores de Lagrange. A relaxação Lagrangiana também pode fornecer soluções aproximadas para problemas difíceis e restritos.
Quando a função objetivo é convexa, então qualquer mínimo local também será um mínimo global. Existem técnicas numéricas eficientes para minimizar funções convexas, por exemplo métodos de pontos interiores.
Técnicas de otimização computacional
Para resolver problemas, los investigadores pueden usar algoritmos que terminen en un número finito de pasos, o métodos iterativos que convergen a una solución (en alguna clase específica de problemas), o heurísticas que pueden proveer soluciones aproximadas a algunos problemas (aunque sus iteraciones no convergen necesariamente).
Métodos iterativos
Os métodos iterativos usados para resolver problemas de programação não linear diferem dependendo do que avaliam: Hessianos, gradientes ou apenas valores de função. Embora a avaliação de Hessianos (H) e gradientes (G) melhore a velocidade de convergência, tais avaliações aumentam a complexidade computacional (ou custo computacional) de cada iteração. Em alguns casos, a complexidade computacional pode ser excessivamente alta.
Um critério importante para otimizadores é apenas o número de avaliações de funções necessárias, já que isso geralmente representa um grande esforço computacional, geralmente muito mais esforço do que o do próprio otimizador, uma vez que ele tem que operar principalmente em N variáveis. Os derivados fornecem informações detalhadas para otimizadores, mas são ainda mais caros para calcular, por exemplo, a aproximação do gradiente requer pelo menos N+1 avaliações de função. Para a aproximação das segundas derivadas (agrupadas na matriz Hessiana) o número de avaliações de funções é da ordem N². O método de Newton requer derivadas de segunda ordem, portanto, para cada iteração o número de chamadas de função é da ordem N², mas para o otimizador de gradiente puro mais simples é da ordem N. No entanto, os otimizadores de gradiente geralmente precisam de mais iterações do que o algoritmo de Newton. Ser melhor quanto ao número de chamadas de função depende do problema em si.
Geralmente, se a função objetivo não for uma função quadrática, então muitos métodos de otimização usam outros métodos para garantir que alguma subsequência de iterações convirja para uma solução ótima. O primeiro método popular que garante convergência é baseado em buscas lineares, que otimizam uma função em uma dimensão. Um segundo método popularizado para garantir a convergência utiliza regiões de confiança. Tanto as pesquisas lineares quanto as regiões de confiança são usadas em métodos modernos de otimização não diferenciáveis. Normalmente, um otimizador global é muito mais lento que otimizadores locais avançados (por exemplo, BFGS), portanto, muitas vezes, um otimizador global eficiente pode ser construído iniciando o otimizador local a partir de diferentes pontos de partida.
Heurística
Além de algoritmos (conclusão finita) e métodos iterativos (convergentes), existem heurísticas que podem fornecer soluções aproximadas para alguns problemas de otimização:
Normalmente, A é algum subconjunto do espaço euclidiano R, muitas vezes limitado por um conjunto de restrições, igualdades ou desigualdades "Restrição (matemática)" que os elementos de A devem satisfazer. O domínio A de f é chamado de espaço de busca ou conjunto de escolhas, enquanto os elementos de A são chamados de soluções candidatas ou soluções viáveis.
A função f é chamada, de várias maneiras, de função objetivo, função de custo (minimização),[2] função de utilidade (maximização), função de utilidade indireta (minimização),[3] ou, em certos campos, função de energia, ou funcional de energia "Funcional (matemática)"). Uma solução viável que minimiza (ou maximiza, se este for o propósito) a função objetivo é chamada de solução ótima.
Por convenção, o formato padrão de um problema de otimização é expresso em termos de minimização. Geralmente, a menos que tanto a função objetivo quanto a região viável sejam convexas em um problema de minimização, pode haver vários mínimos locais, onde um mínimo local x é definido como um ponto para o qual existe algum δ > 0, onde para todo x tal que.
a expressão.
é verdade; Ou seja, em alguma região em torno de x, todos os valores da função são maiores ou iguais ao valor naquele ponto. O máximo local é definido de forma semelhante.
Um grande número de algoritmos propostos para resolver problemas não-convexos – incluindo a maioria dos solucionadores disponíveis comercialmente – não são capazes de fazer uma distinção entre soluções ótimas locais e soluções ótimas rigorosas, e tratar as primeiras como soluções atuais do problema original. O ramo da matemática aplicada e da análise numérica responsável pelo desenvolvimento de algoritmos determinísticos capazes de garantir a convergência em tempo finito para a solução ótima real de um problema não convexo é denominado otimização global.
Notação
Contenido
Los problemas de optimización se expresan a menudo con una notación especial. A continuación se muestran algunos ejemplos.
Valor mínimo e máximo de uma função
Considere a seguinte notação:
Isso denota o valor mínimo de "Magnitude (matemática)") da função objetivo, quando x é selecionado do conjunto de números reais. O valor mínimo neste caso é e ocorre para .
Da mesma forma, a notação.
expressa o valor máximo da função objetivo 2x, onde x é qualquer número real. Neste caso, não existe tal máximo, portanto não existe um valor ótimo limitado.
Argumentos para entrada ideal
Considere a seguinte expressão:
ou equivalente.
Isto representa o valor (ou valores) do argumento "Argumento (análise complexa)") de x no intervalo "Intervalo (matemática)") que minimiza (ou maximiza) a função objetivo x + 1 (e não o valor mínimo que a função objetivo atinge para esses valores). Neste caso, a resposta é x = -1, pois x = 0 não é viável, ou seja, não pertence ao domínio do problema.
De forma similar,
que equivale a.
representa o par (ou pares) (x,y) que minimiza (ou maximiza) o valor da função objetivo xcos(y), com a restrição adicional de que x está no intervalo [-5,5] (novamente, o valor mínimo da função não importa). Neste caso, as soluções são os pares da forma (5, 2kπ) e (−5,(2k+1)π), onde k percorre todos os inteiros.
Arg min e arg max às vezes são escritos como argmin e argmax, significando argumento mínimo e argumento máximo.
História
Pierre de Fermat e Joseph Louis Lagrange encontraram fórmulas baseadas em cálculo para identificar valores ótimos, enquanto Isaac Newton e Carl Friedrich Gauss propuseram métodos iterativos para aproximar o ótimo. Historicamente, o termo programação linear para se referir a certos problemas de otimização é devido a George B. Dantzig, embora grande parte da teoria tenha sido introduzida por Leonid Kantorovich em 1939. Dantzig publicou o Algoritmo Simplex em 1947 e John von Neumann desenvolveu a teoria da dualidade "Dualidade (matemática)") no mesmo ano.
O termo programação neste contexto não se refere à programação de computadores. Em vez disso, o termo vem do uso de programa pelos militares dos Estados Unidos quando se referem à proposta de treinamento e planejamento logístico, que era o problema estudado por Dantzig na época.
Outros pesquisadores importantes na área de otimização matemática foram os seguintes:
Classificação de pontos críticos e extremos
Viabilidade do problema
A solubilidade do problema, também chamada de viabilidade do problema, é a questão de saber se existe alguma solução viável, independentemente do seu valor objetivo. Este pode ser considerado o caso especial de otimização matemática onde o valor objetivo é o mesmo para todas as soluções e, portanto, qualquer solução é ótima.
Muitos algoritmos de otimização precisam começar de um ponto viável. Uma forma de obter tal ponto é relaxar as condições de viabilidade utilizando uma variável de folga; Com folga suficiente, qualquer ponto de partida é viável. Então, essa variável de folga é minimizada até que a folga seja zero ou negativa.
Existência
O teorema de Weierstrass afirma que uma função real e contínua em um conjunto compacto atinge seu valor máximo e mínimo. De forma mais geral, uma função semicontínua inferior em um conjunto compacto atinge seu mínimo; uma função semicontínua superior em um conjunto compacto atinge seu máximo.
Condições necessárias de otimalidade
Um dos teoremas de Fermat garante que os ótimos de problemas irrestritos são encontrados em pontos estacionários, onde a primeira derivada da função objetivo é zero (ou seu gradiente nulo). Mais geralmente, eles também podem ser encontrados em pontos críticos onde a primeira derivada ou gradiente da função objetivo não está definida, ou no limite da "Fronteira (topologia)" do conjunto de escolha. Uma equação (ou conjunto de equações) indicando que a(s) primeira(s) derivada(s) é(são) igual(es) a zero em um ótimo interior é chamada de condição de primeira ordem ou um conjunto de condições de primeira ordem.
Os ótimos de problemas com restrições de desigualdade são encontrados pelo método dos multiplicadores de Lagrange. Este método calcula um sistema de desigualdades chamado condições de Karush – Kuhn – Tucker ou condições de folga complementar, que são então usadas para calcular o ótimo.
Condições de otimalidade suficientes
Embora o teste da primeira derivada identifique pontos que podem ser extremos, este teste não distingue se um ponto é mínimo, máximo ou nenhum dos dois. Quando a função objetivo é duas vezes diferenciável, esses casos podem ser distinguidos estudando a segunda derivada ou a matriz das segundas derivadas (chamada de matriz Hessiana), em problemas irrestritos, ou a matriz das segundas derivadas da função objetivo e as restrições chamada de matriz Hessiana com borda, em problemas restritos.
As condições que distinguem máximos ou mínimos de outros pontos estacionários são chamadas de condições de segunda ordem. Se uma solução candidata satisfizer as condições de primeira ordem e também as condições de segunda ordem, é suficiente estabelecer, pelo menos, a otimalidade local.
Sensibilidade e continuidade ideais
O teorema do envelope descreve como o valor de uma solução ótima muda quando um parâmetro subjacente muda. O processo que calcula essa mudança é chamado de estática comparativa.
O teorema do máximo de Claude Berge (1963) descreve a continuidade de uma solução ótima em função dos parâmetros subjacentes.
Cálculos de otimização
Para problemas irrestritos com funções duas vezes diferenciáveis, alguns pontos críticos "Ponto crítico (matemática)") podem ser encontrados detectando os pontos onde o gradiente da função objetivo é zero (ou seja, os pontos estacionários). Mais geralmente, um subgradiente zero certifica que um mínimo local foi encontrado para problemas de minimização com funções convexas ou outras funções de Lipschitz.
Além disso, os pontos críticos podem ser classificados usando a definição da matriz Hessiana: se for definido positivo em um ponto crítico, então o ponto é um mínimo local; se for definido negativo, então o ponto é um máximo local; finalmente, se for indefinido, então o ponto é algum tipo de ponto de sela.
Problemas restritos muitas vezes podem ser transformados em problemas irrestritos com a ajuda dos multiplicadores de Lagrange. A relaxação Lagrangiana também pode fornecer soluções aproximadas para problemas difíceis e restritos.
Quando a função objetivo é convexa, então qualquer mínimo local também será um mínimo global. Existem técnicas numéricas eficientes para minimizar funções convexas, por exemplo métodos de pontos interiores.
Técnicas de otimização computacional
Para resolver problemas, los investigadores pueden usar algoritmos que terminen en un número finito de pasos, o métodos iterativos que convergen a una solución (en alguna clase específica de problemas), o heurísticas que pueden proveer soluciones aproximadas a algunos problemas (aunque sus iteraciones no convergen necesariamente).
Métodos iterativos
Os métodos iterativos usados para resolver problemas de programação não linear diferem dependendo do que avaliam: Hessianos, gradientes ou apenas valores de função. Embora a avaliação de Hessianos (H) e gradientes (G) melhore a velocidade de convergência, tais avaliações aumentam a complexidade computacional (ou custo computacional) de cada iteração. Em alguns casos, a complexidade computacional pode ser excessivamente alta.
Um critério importante para otimizadores é apenas o número de avaliações de funções necessárias, já que isso geralmente representa um grande esforço computacional, geralmente muito mais esforço do que o do próprio otimizador, uma vez que ele tem que operar principalmente em N variáveis. Os derivados fornecem informações detalhadas para otimizadores, mas são ainda mais caros para calcular, por exemplo, a aproximação do gradiente requer pelo menos N+1 avaliações de função. Para a aproximação das segundas derivadas (agrupadas na matriz Hessiana) o número de avaliações de funções é da ordem N². O método de Newton requer derivadas de segunda ordem, portanto, para cada iteração o número de chamadas de função é da ordem N², mas para o otimizador de gradiente puro mais simples é da ordem N. No entanto, os otimizadores de gradiente geralmente precisam de mais iterações do que o algoritmo de Newton. Ser melhor quanto ao número de chamadas de função depende do problema em si.
Geralmente, se a função objetivo não for uma função quadrática, então muitos métodos de otimização usam outros métodos para garantir que alguma subsequência de iterações convirja para uma solução ótima. O primeiro método popular que garante convergência é baseado em buscas lineares, que otimizam uma função em uma dimensão. Um segundo método popularizado para garantir a convergência utiliza regiões de confiança. Tanto as pesquisas lineares quanto as regiões de confiança são usadas em métodos modernos de otimização não diferenciáveis. Normalmente, um otimizador global é muito mais lento que otimizadores locais avançados (por exemplo, BFGS), portanto, muitas vezes, um otimizador global eficiente pode ser construído iniciando o otimizador local a partir de diferentes pontos de partida.
Heurística
Além de algoritmos (conclusão finita) e métodos iterativos (convergentes), existem heurísticas que podem fornecer soluções aproximadas para alguns problemas de otimização: