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.

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:

• - Programação convexa estuda o caso em que a função objetivo é convexa (minimização) ou côncava (maximização) e o conjunto de restrições é convexo. Isto pode ser visto como um caso particular de programação não linear ou como a generalização da programação quadrática linear ou convexa.

• Programação linear (LP): é um tipo de programação convexa, em que a função objetivo f é linear e o conjunto de restrições é especificado usando apenas equações e desigualdades lineares. Este conjunto é chamado de poliedro ou politopo se for limitado.

• Programação cônica: é uma forma geral de programação convexa. PL, PCSO e PSD podem ser vistos como programas cônicos com o tipo de cone apropriado.

• Programação cônica de segunda ordem (PCSO): É um tipo de programação convexa e inclui certos tipos de problemas de programação quadrática.

• Programação semidefinida (PSD): é um subcampo da otimização convexa onde as variáveis ​​fundamentais são matrizes "Matriz (matemática)" semidefinidas. É uma generalização da programação linear e da programação quadrática convexa.

• Programação geométrica: é uma técnica pela qual as restrições de objetivo e de desigualdade expressas como polinômios e as restrições de igualdade como monômios podem ser transformadas em um programa convexo.

• Programação com números inteiros ou Programação inteira: estuda programas lineares nos quais algumas ou todas as variáveis ​​são forçadas a assumir valores inteiros. Isso não é convexo e geralmente é muito mais complexo do que a programação linear normal.

• - Programação quadrática: permite que a função objetivo tenha termos quadráticos, enquanto o conjunto viável pode ser especificado com equações lineares e desigualdades. Para formas específicas do termo quadrático, este é um tipo de programação convexa.

• - Programação fracionária: estuda a otimização de razões de duas funções não lineares. A classe especial de programas fracionários côncavos pode ser transformada em um problema de otimização convexo.

• - Programação não linear: estuda o caso geral em que a função objetivo, ou as restrições, ou ambas, contêm partes não lineares. Este pode ou não ser um programa convexo. Em geral, o fato de o programa ser convexo afeta a dificuldade de resolução.

• - Programação estocástica ou Otimização estocástica: estuda o caso em que algumas das restrições ou parâmetros dependem de variáveis ​​aleatórias.

• - Programação robusta: assim como a programação estocástica, é uma tentativa de capturar a incerteza nos dados fundamentais do problema de otimização. Isso é feito usando variáveis ​​aleatórias, mas em vez disso, o problema é resolvido levando-se em consideração imprecisões nos dados de entrada.

• - Otimização combinatória: preocupa-se com problemas onde o conjunto de soluções viáveis ​​é discreto ou pode ser reduzido a um.

• - Otimização de dimensão infinita: estuda o caso onde o conjunto de soluções viáveis ​​é um subconjunto de um espaço de dimensão infinita, por exemplo um espaço de funções.

• - Heurísticas&action=edit&redlink=1 "Heurísticas (ciência da computação) (ainda não escrita)") e Metaheurísticas: fazem suposições sobre o problema que está sendo otimizado. Normalmente, as heurísticas não garantem que qualquer solução ótima será encontrada. As heurísticas são então usadas para encontrar soluções aproximadas para muitos problemas complicados de otimização.

• - Satisfação de restrições: estuda o caso em que a função objetivo f é constante (isto é usado em inteligência artificial, particularmente em raciocínio automatizado).

• - Programação disjuntiva: usada quando pelo menos uma restrição pode ser satisfeita, mas não todas. Isto é particularmente útil na programação em vários subcampos. As técnicas são projetadas principalmente para otimização em contextos dinâmicos (ou seja, tomada de decisão ao longo do tempo).

• - Cálculo de variações: busca otimizar um objetivo definido ao longo de muitos pontos ao longo do tempo, considerando como a função objetivo muda se a mudança for pequena no caminho de escolha. A técnica de controle ideal é uma generalização disso.

• - Programação dinâmica estuda o caso em que a estratégia de otimização se baseia na divisão do problema em subproblemas menores. A equação que descreve a relação entre esses subproblemas é chamada de equação de Bellman.

• - Programação matemática com restrições de equilíbrio é onde as restrições incluem desigualdades variáveis ​​ou complementares.

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, 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.

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).

Algoritmos de otimização

• - Algoritmo Simplex de George Dantzig, projetado para programação linear.

• - Extensões ao algoritmo Simplex, projetado para programação quadrática e programação linear-fracionária.

• - Variantes do algoritmo Simplex especialmente apropriadas para otimização de redes.

• - Algoritmos combinatórios.

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.

• - Métodos que avaliam Hessianos (ou Hessianos aproximados, usando diferenças finitas):

• Método de Newton.

• Programação sequencial quadrática: um método de Newton baseado em problemas restritos de pequena e média escala. Algumas versões podem lidar com problemas de grandes dimensões.

• - Métodos que avaliam gradientes ou aproximam gradientes usando diferenças finitas (ou mesmo subgradientes):

• Métodos quase-Newton: métodos iterativos para problemas de médio-grande porte (exemplo N<1000).

• Métodos de gradiente conjugado: métodos iterativos para grandes problemas. (Em teoria, estes métodos terminam num número finito de passos com funções objectivo quadráticas, mas esta terminação finita não é observada na prática em computadores de precisão finita.)

• Métodos de Pontos Interiores: Esta é uma ótima classe de métodos para otimização restrita. Alguns métodos de pontos interiores usam apenas informações de subgradiente e outros requerem avaliação de Hessianos.

• Descida gradiente (alternativamente, descida íngreme ou subida íngreme): método lento de interesse teórico e histórico, que se renovou para encontrar soluções aproximadas para enormes problemas.

• Método de subgradiente: um método iterativo para funções Lipschitz localmente grandes usando gradientes generalizados.

• - Métodos que avaliam apenas valores de funções: se um problema for continuamente diferenciável, então os gradientes podem ser aproximados usando diferenças finitas, caso em que um método baseado em gradiente pode ser usado.

• Métodos de interpolação.

• Métodos de busca de padrões, que possuem melhores propriedades de convergência que a heurística de Nelder-Mead.

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 do 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:

• - Evolução diferencial.

• - Algoritmo de busca diferencial.

• - Relaxamento Dinâmico.

• - Algoritmos genéticos.

• - Escalar montanhas.

• - Nelder-Mead: uma heurística popular para aproximação de minimização (sem chamadas a gradientes).

• - Otimização de enxame de partículas.

• - Otimização artificial da colônia de abelhas.

• - Otimização multiobjetivo.

• - Eficiência de Pareto.

• - Multiplicadores de Lagrange.

• - Otimização bayesiana.

• - COIN-OR – Infraestrutura Computacional para Pesquisa Operacional.

• - Árvore de decisão para software de otimização Links para códigos fonte de otimização.

• - Otimização global Arquivado em 28 de dezembro de 2008 na Wayback Machine.

• - Glossário de Programação Matemática.

• - Sociedade de Programação Matemática.

• - NEOS Wiki atualmente sendo substituído pelo Arquivado em 22 de agosto de 2002 na Wayback Machine.

• - Optimization Online Um repositório para otimização de e-prints.

• - Links relacionados à otimização.

• - Otimização Convexa I EE364a: Curso da Universidade de Stanford.

• - Otimização Convexa – Livro de Boyd e Vandenberghe sobre Otimização Convexa.

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.

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:

• - Programação convexa estuda o caso em que a função objetivo é convexa (minimização) ou côncava (maximização) e o conjunto de restrições é convexo. Isto pode ser visto como um caso particular de programação não linear ou como a generalização da programação quadrática linear ou convexa.

• Programação linear (LP): é um tipo de programação convexa, em que a função objetivo f é linear e o conjunto de restrições é especificado usando apenas equações e desigualdades lineares. Este conjunto é chamado de poliedro ou politopo se for limitado.

• Programação cônica: é uma forma geral de programação convexa. PL, PCSO e PSD podem ser vistos como programas cônicos com o tipo de cone apropriado.

• Programação cônica de segunda ordem (PCSO): É um tipo de programação convexa e inclui certos tipos de problemas de programação quadrática.

• Programação semidefinida (PSD): é um subcampo da otimização convexa onde as variáveis ​​fundamentais são matrizes "Matriz (matemática)" semidefinidas. É uma generalização da programação linear e da programação quadrática convexa.

• Programação geométrica: é uma técnica pela qual as restrições de objetivo e de desigualdade expressas como polinômios e as restrições de igualdade como monômios podem ser transformadas em um programa convexo.

• Programação com números inteiros ou Programação inteira: estuda programas lineares nos quais algumas ou todas as variáveis ​​são forçadas a assumir valores inteiros. Isso não é convexo e geralmente é muito mais complexo do que a programação linear normal.

• - Programação quadrática: permite que a função objetivo tenha termos quadráticos, enquanto o conjunto viável pode ser especificado com equações lineares e desigualdades. Para formas específicas do termo quadrático, este é um tipo de programação convexa.

• - Programação fracionária: estuda a otimização de razões de duas funções não lineares. A classe especial de programas fracionários côncavos pode ser transformada em um problema de otimização convexo.

• - Programação não linear: estuda o caso geral em que a função objetivo, ou as restrições, ou ambas, contêm partes não lineares. Este pode ou não ser um programa convexo. Em geral, o fato de o programa ser convexo afeta a dificuldade de resolução.

• - Programação estocástica ou Otimização estocástica: estuda o caso em que algumas das restrições ou parâmetros dependem de variáveis ​​aleatórias.

• - Programação robusta: assim como a programação estocástica, é uma tentativa de capturar a incerteza nos dados fundamentais do problema de otimização. Isso é feito usando variáveis ​​aleatórias, mas em vez disso, o problema é resolvido levando-se em consideração imprecisões nos dados de entrada.

• - Otimização combinatória: preocupa-se com problemas onde o conjunto de soluções viáveis ​​é discreto ou pode ser reduzido a um.

• - Otimização de dimensão infinita: estuda o caso onde o conjunto de soluções viáveis ​​é um subconjunto de um espaço de dimensão infinita, por exemplo um espaço de funções.

• - Heurísticas&action=edit&redlink=1 "Heurísticas (ciência da computação) (ainda não escrita)") e Metaheurísticas: fazem suposições sobre o problema que está sendo otimizado. Normalmente, as heurísticas não garantem que qualquer solução ótima será encontrada. As heurísticas são então usadas para encontrar soluções aproximadas para muitos problemas complicados de otimização.

• - Satisfação de restrições: estuda o caso em que a função objetivo f é constante (isto é usado em inteligência artificial, particularmente em raciocínio automatizado).

• - Programação disjuntiva: usada quando pelo menos uma restrição pode ser satisfeita, mas não todas. Isto é particularmente útil na programação em vários subcampos. As técnicas são projetadas principalmente para otimização em contextos dinâmicos (ou seja, tomada de decisão ao longo do tempo).

• - Cálculo de variações: busca otimizar um objetivo definido ao longo de muitos pontos ao longo do tempo, considerando como a função objetivo muda se a mudança for pequena no caminho de escolha. A técnica de controle ideal é uma generalização disso.

• - Programação dinâmica estuda o caso em que a estratégia de otimização se baseia na divisão do problema em subproblemas menores. A equação que descreve a relação entre esses subproblemas é chamada de equação de Bellman.

• - Programação matemática com restrições de equilíbrio é onde as restrições incluem desigualdades variáveis ​​ou complementares.

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, 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.

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).

Algoritmos de otimização

• - Algoritmo Simplex de George Dantzig, projetado para programação linear.

• - Extensões ao algoritmo Simplex, projetado para programação quadrática e programação linear-fracionária.

• - Variantes do algoritmo Simplex especialmente apropriadas para otimização de redes.

• - Algoritmos combinatórios.

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.

• - Métodos que avaliam Hessianos (ou Hessianos aproximados, usando diferenças finitas):

• Método de Newton.

• Programação sequencial quadrática: um método de Newton baseado em problemas restritos de pequena e média escala. Algumas versões podem lidar com problemas de grandes dimensões.

• - Métodos que avaliam gradientes ou aproximam gradientes usando diferenças finitas (ou mesmo subgradientes):

• Métodos quase-Newton: métodos iterativos para problemas de médio-grande porte (exemplo N<1000).

• Métodos de gradiente conjugado: métodos iterativos para grandes problemas. (Em teoria, estes métodos terminam num número finito de passos com funções objectivo quadráticas, mas esta terminação finita não é observada na prática em computadores de precisão finita.)

• Métodos de Pontos Interiores: Esta é uma ótima classe de métodos para otimização restrita. Alguns métodos de pontos interiores usam apenas informações de subgradiente e outros requerem avaliação de Hessianos.

• Descida gradiente (alternativamente, descida íngreme ou subida íngreme): método lento de interesse teórico e histórico, que se renovou para encontrar soluções aproximadas para enormes problemas.

• Método de subgradiente: um método iterativo para funções Lipschitz localmente grandes usando gradientes generalizados.

• - Métodos que avaliam apenas valores de funções: se um problema for continuamente diferenciável, então os gradientes podem ser aproximados usando diferenças finitas, caso em que um método baseado em gradiente pode ser usado.

• Métodos de interpolação.

• Métodos de busca de padrões, que possuem melhores propriedades de convergência que a heurística de Nelder-Mead.

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 do 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:

• - Evolução diferencial.

• - Algoritmo de busca diferencial.

• - Relaxamento Dinâmico.

• - Algoritmos genéticos.

• - Escalar montanhas.

• - Nelder-Mead: uma heurística popular para aproximação de minimização (sem chamadas a gradientes).

• - Otimização de enxame de partículas.

• - Otimização artificial da colônia de abelhas.

• - Otimização multiobjetivo.

• - Eficiência de Pareto.

• - Multiplicadores de Lagrange.

• - Otimização bayesiana.

• - COIN-OR – Infraestrutura Computacional para Pesquisa Operacional.

• - Árvore de decisão para software de otimização Links para códigos fonte de otimização.

• - Otimização global Arquivado em 28 de dezembro de 2008 na Wayback Machine.

• - Glossário de Programação Matemática.

• - Sociedade de Programação Matemática.

• - NEOS Wiki atualmente sendo substituído pelo Arquivado em 22 de agosto de 2002 na Wayback Machine.

• - Optimization Online Um repositório para otimização de e-prints.

• - Links relacionados à otimização.

• - Otimização Convexa I EE364a: Curso da Universidade de Stanford.

• - Otimização Convexa – Livro de Boyd e Vandenberghe sobre Otimização Convexa.