Otimização matemática (Mathematical optimization)

Otimização matemática (alternativamente escrita como otimização) ou programação matemática é o processo de seleção de um elemento ideal, com base em critérios específicos, a partir de um conjunto definido de alternativas disponíveis. Normalmente é categorizado em dois subcampos principais: otimização discreta e otimização contínua. Problemas de otimização surgem em várias disciplinas quantitativas, desde ciência da computação e engenharia até pesquisa operacional e economia, e a busca por metodologias de solução eficazes tem sido um foco central na matemática há séculos.

De uma perspectiva mais ampla, um problema de otimização envolve maximizar ou minimizar uma função com valor real por meio da seleção sistemática de valores de entrada de um domínio permitido e subsequente avaliação da saída da função. Estender a teoria da otimização e suas técnicas associadas a diversas formulações de problemas representa um domínio significativo dentro da matemática aplicada.

Problemas de otimização

Os problemas de otimização são normalmente classificados em duas categorias principais, com base na natureza de suas variáveis, especificamente se são contínuas ou discretas:

• Um problema de otimização com variáveis discretas é denominado otimização discreta, onde o objetivo é identificar um elemento ideal, como um número inteiro, permutação ou gráfico, de um conjunto contável.
• Um problema envolvendo variáveis contínuas é chamado de otimização contínua, exigindo a identificação de argumentos ótimos dentro de um domínio contínuo. Esta categoria abrange problemas restritos e multimodais.

Um problema de otimização pode ser formalmente expresso da seguinte forma:

Dado: Uma função ${\displaystyle f:A\rightarrow \mathbb {R} }$ mapeamento de um conjunto A para os números reais.

Procurado: Um elemento x§56§ ∈ A tal que f(x§1516§) ≤ f(x) para todos x ∈ A (representando minimização) ou tal que f(x§3334§) ≥ f(x) para todos x ∈ A (representando maximização).

Este tipo de formulação é designado como um problema de otimização ou um problema de programação matemática. Este termo, embora não esteja diretamente associado à programação de computadores, continua predominante, por exemplo, na programação linear. Numerosos desafios teóricos e do mundo real podem ser modelados de forma eficaz dentro desta estrutura abrangente.

Dada a validade da seguinte equivalência:

f ( x §1617§ ) ≥ f ( x ) ⇔ − f ( x §5152§ ) ≤ − f ( x ) , {\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} )\Leftrightarrow -f(\mathbf {x} _{0})\leq -f(\mathbf {x} ),}

é suficiente resolver apenas problemas de minimização. Por outro lado, uma abordagem igualmente válida envolveria focar exclusivamente em problemas de maximização.

Em física, os problemas formulados com esta técnica são frequentemente denominados minimização de energia, onde o valor da função f significa a energia do sistema em consideração. No aprendizado de máquina, a avaliação contínua da qualidade de um modelo de dados é fundamental, normalmente alcançada por meio de uma função de custo em que um valor mínimo indica um conjunto de parâmetros potencialmente ideais associados ao menor erro possível.

O conjunto A normalmente constitui um subconjunto do espaço euclidiano ${\displaystyle \mathbb {R} ^{n}}$. Este subconjunto é frequentemente definido por uma série de restrições, que podem ser igualdades ou desigualdades que todos os elementos de A devem satisfazer. O domínio A para a função f é referido como o espaço de pesquisa ou o conjunto de escolhas, e seus elementos individuais são designados como soluções candidatas ou soluções viáveis.

A função f é conhecida por vários nomes, incluindo função objetivo, critério função, função de perda ou função de custo quando a minimização é o objetivo. Para problemas de maximização, pode ser denominada função de utilidade ou função de aptidão. Em disciplinas específicas, também é chamada de função energética ou funcional energético. Uma solução ótima é definida como uma solução viável que minimiza ou maximiza a função objetivo.

No campo da matemática, problemas de otimização padrão são normalmente formulados como tarefas de minimização.

Um mínimo local, denotado como x*, é caracterizado como um elemento para o qual um valor positivo δ > 0 existe, satisfazendo a condição de que:

${\displaystyle \forall \mathbf {x} \in A\;{\text{where}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,}$

a desigualdade f(x*) ≤ f(x) é satisfeita;

Isso implica que dentro de uma vizinhança específica de x*, todos os valores da função são maiores ou iguais ao valor em x*. Os máximos locais são caracterizados por uma definição análoga.

Embora um mínimo local represente um valor superior ou igual ao de seus elementos vizinhos imediatos, um mínimo global supera ou iguala o valor de cada elemento viável. Normalmente, em problemas de minimização, podem existir múltiplos mínimos locais, a menos que a função objetivo seja convexa. Para um problema convexo, um mínimo local interior (aquele não localizado na fronteira do conjunto viável) também constitui o mínimo global. No entanto, um problema não convexo pode possuir vários mínimos locais, nem todos necessariamente qualificados como mínimos globais. Numerosos algoritmos projetados para resolver problemas não convexos, incluindo a maioria dos solucionadores comerciais, frequentemente não conseguem diferenciar entre soluções localmente ótimas e globalmente ótimas, muitas vezes tratando os ótimos locais como as verdadeiras soluções para o problema. A otimização global é um campo especializado em matemática aplicada e análise numérica dedicada à criação de algoritmos determinísticos que podem garantir a convergência para a solução ideal real de um problema não convexo dentro de um período de tempo finito.

Convenções Notacionais

Problemas de otimização são frequentemente representados usando sistemas notacionais específicos. Os exemplos a seguir ilustram isso:

Determinando os valores mínimo e máximo de uma função

Examine a notação subsequente:

min x ∈<!-- ∈ --> R ( x §3132§ + §3738§ ) {\displaystyle \min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)}

Esta notação significa o valor mais baixo possível da função objetivo x§34§ + 1, onde x é selecionado do conjunto de números reais ${\displaystyle \mathbb {R} }$. Neste caso específico, o valor mínimo é 1, alcançado quando x é igual a 0.

De maneira semelhante, a notação

${\displaystyle \max _{x\in \mathbb {R} }\;2x}$

busca identificar o maior valor possível da função objetivo 2x, com x representando qualquer número real. No entanto, neste cenário, não existe nenhum máximo finito porque a função objetivo é ilimitada, levando a um resultado de "infinito" ou "indefinido".

Argumentos de entrada ideais

A notação subsequente ilustra:

a r g m i n x ∈<!-- ∈ --> ( −<!-- − --> ∞<!-- ∞ --> , −<!-- − --> §4344§ ] x §5657§ + §6263§ , {\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}

Como alternativa, isso pode ser expresso como:

a r g m i n x x §3435§ + §4041§ , sujeito a: x ∈ ( − ∞ , − §7071§ ] . {\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in (-\infty ,-1].}

Esta expressão identifica o(s) valor(es) do argumento x dentro do intervalo (−∞,−1] que produz o mínimo para a função objetivo x§78§ + 1. É importante observar que esta consulta não busca o valor mínimo da função em si, mas sim o(s) argumento(s) que o produz(em). Consequentemente, a solução é x = −1, dado que x = 0 é inviável, o que significa que está fora do conjunto viável definido.

De maneira análoga,

${\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,}$

Em alternativa,

${\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,}$

Isso denota o(s) par(es) {x, y} que maximizam o valor da função objetivo x cos y, sujeito à restrição de que x está dentro do intervalo [−5,5]. O valor máximo específico da expressão não é relevante neste contexto. Consequentemente, as soluções são pares estruturados como {5, 2kπ} e {−5, (2k + 1)π}, onde k representa qualquer número inteiro.

Os operadores arg min e arg max são denotados alternativamente como argmin e argmax, significando respectivamente o argumento do mínimo e o argumento do máximo.

Histórico

Fermat e Lagrange desenvolveram fórmulas baseadas em cálculo para identificar pontos ótimos. Por outro lado, Newton e Gauss introduziram metodologias iterativas para aproximar-se de um ótimo.

George B. Dantzig cunhou o termo "programação linear" para descrever cenários de otimização específicos; no entanto, uma parte substancial da teoria subjacente foi previamente estabelecida por Leonid Kantorovich em 1939. É importante notar que Programação, neste contexto, não se refere à programação de computadores; em vez disso, origina-se do uso do termo programa pelos militares dos Estados Unidos para denotar cronogramas de treinamento e logística propostos, que constituíram os problemas que Dantzig investigou durante aquele período. Posteriormente, Dantzig publicou o algoritmo Simplex em 1947. Ao mesmo tempo, John von Neumann e outros pesquisadores contribuíram para os fundamentos teóricos da programação linear, incluindo a teoria da dualidade.

Pesquisadores adicionais proeminentes no campo da otimização matemática incluem:

Subcampos principais

• A programação convexa investiga cenários onde a função objetivo é convexa para problemas de minimização ou côncava para problemas de maximização, e o próprio conjunto de restrições é convexo. Esta abordagem pode ser considerada um exemplo específico de programação não linear ou uma generalização mais ampla de programação quadrática linear ou convexa.
  • A programação linear (PL), um subconjunto da programação convexa, concentra-se em situações onde a função objetivo f é linear e as restrições são definidas exclusivamente por igualdades e desigualdades lineares. Quando limitado, esse conjunto de restrições é denominado poliedro ou politopo.
  • A programação cônica de segunda ordem (SOCP) constitui uma forma de programação convexa que abrange categorias específicas de programas quadráticos.
  • A programação semidefinida (SDP) representa um subcampo de otimização convexa caracterizado por variáveis ​​subjacentes que são matrizes semidefinidas. Este método serve como uma generalização da programação quadrática linear e convexa.
  • A programação cônica constitui uma estrutura generalizada para programação convexa. A programação linear (LP), a programação cônica de segunda ordem (SOCP) e a programação semidefinida (SDP) podem ser conceituadas como programas cônicos ao empregar o tipo de cone adequado.
  • A programação geométrica é uma metodologia que permite a transformação de restrições objetivas e de desigualdade, quando expressas como posinômios, e restrições de igualdade, quando expressas como monômios, em um programa convexo.
• A programação inteira investiga programas lineares onde um subconjunto ou todas as variáveis são restritos a valores inteiros. Esta abordagem é inerentemente não convexa e normalmente apresenta desafios computacionais significativamente maiores em comparação com a programação linear padrão.
• A programação quadrática permite que a função objetivo incorpore termos quadráticos, desde que o conjunto viável seja definido por igualdades e desigualdades lineares. Sob certas configurações do termo quadrático, este método cai dentro do domínio da programação convexa.
• A programação fracionária investiga a otimização de relações entre duas funções não lineares. Uma categoria específica, programas fracionários côncavos, pode ser transformada em problemas de otimização convexos.
• A programação não linear aborda cenários onde a função objetivo, as restrições ou ambas incorporam componentes não lineares. Tais programas podem ou não ser convexos, característica que geralmente influencia a complexidade de sua solução.
• A programação estocástica examina situações em que certas restrições ou parâmetros dependem de variáveis aleatórias.
• Semelhante à programação estocástica, a otimização robusta se esforça para levar em conta a incerteza dos dados em um problema de otimização. O seu objetivo é identificar soluções que permaneçam válidas em todas as manifestações potenciais de incertezas, conforme delineado por um conjunto de incertezas.
• A otimização combinatória aborda problemas caracterizados por um conjunto discreto de soluções viáveis, ou problemas que podem ser transformados nessa forma discreta.
• A otimização estocástica é aplicada quando o processo de pesquisa envolve medições de funções aleatórias ou ruidosas, ou entradas aleatórias.
• A otimização de dimensão infinita investiga cenários onde o conjunto de soluções viáveis constitui um subconjunto de um espaço de dimensão infinita, por exemplo, um espaço de funções.
• Heurísticas e metaheurísticas operam com suposições mínimas ou nenhumas em relação ao problema de otimização. Embora as heurísticas normalmente não garantam a descoberta de uma solução ideal, elas são frequentemente empregadas para identificar soluções aproximadas para vários desafios complexos de otimização.
• A satisfação de restrições examina situações em que a função objetivo f permanece constante, um princípio aplicado em inteligência artificial, particularmente em raciocínio automatizado.
  • A programação com restrições representa um paradigma onde os relacionamentos entre variáveis são articulados como restrições.
• A programação disjuntiva é empregada em contextos onde pelo menos uma, mas não todas, as restrições especificadas devem ser satisfeitas, encontrando utilidade particular em aplicações de escalonamento.
• O mapeamento espacial é uma metodologia para modelar e otimizar sistemas de engenharia para obter precisão de modelo de alta fidelidade, aproveitando um modelo aproximado ou substituto apropriado e fisicamente significativo.

Vários subcampos desenvolvem principalmente técnicas de otimização em contextos dinâmicos, envolvendo especificamente a tomada de decisões ao longo do tempo:

• O cálculo de variações concentra-se na identificação de caminhos ótimos para atingir um objetivo específico, por exemplo, determinar uma superfície com um limite definido que possua a área mínima possível.
• A teoria do controle ótimo amplia o cálculo de variações ao incorporar políticas de controle.
• A programação dinâmica oferece um método para resolver problemas de otimização estocástica caracterizados por parâmetros de modelo aleatórios ou desconhecidos. Esta abordagem envolve uma estratégia de otimização que decompõe um problema em subproblemas menores, com suas inter-relações descritas pela equação de Bellman.
• A programação matemática com restrições de equilíbrio envolve cenários onde as restrições abrangem desigualdades variacionais ou complementaridades.

Otimização multiobjetivo

A incorporação de múltiplos objetivos em um problema de otimização aumenta inerentemente sua complexidade. Por exemplo, a otimização de um projeto estrutural normalmente busca leveza e rigidez. Quando os objectivos entram em conflito, torna-se necessário um compromisso, resultando potencialmente num único design mais leve, num único design mais rígido e numa gama infinita de designs que representam compromissos entre peso e rigidez. O conjunto de designs de trade-off que melhoram um critério enquanto potencialmente diminuem outro é denominado conjunto de Pareto. A representação gráfica de peso versus rigidez para esses projetos ideais forma a fronteira de Pareto.

Um projeto é considerado "ótimo de Pareto" (também conhecido como "eficiente de Pareto" ou pertencente ao conjunto de Pareto) se nenhum outro projeto o dominar. A dominação ocorre quando um design é inferior em alguns aspectos e superior em nenhum em comparação com outro design, tornando-o não-óptimo de Pareto.

A seleção de uma "solução favorita" de um conjunto de soluções "ótimas de Pareto" normalmente é atribuída ao tomador de decisão. Isto implica que formular um problema como otimização multiobjetivo indica falta de informação, especificamente no que diz respeito à priorização relativa dos objetivos desejáveis. Em certos cenários, essas informações ausentes podem ser obtidas por meio de sessões interativas com o tomador de decisão.

Os problemas de otimização multiobjetivo foram generalizados em problemas de otimização vetorial, nos quais a ordenação parcial não é necessariamente definida pelo critério de Pareto.

Otimização multimodal e global

Os problemas de otimização frequentemente apresentam multimodalidade, o que significa que abrangem diversas soluções eficazes. Essas soluções podem ser uniformemente ótimas globalmente (possuindo valores idênticos de função de custo) ou compreender uma combinação de resultados ótimos global e localmente. O objetivo principal de um otimizador multimodal é identificar todas, ou pelo menos um subconjunto significativo, dessas múltiplas soluções.

As técnicas tradicionais de otimização, devido à sua natureza iterativa, muitas vezes se mostram inadequadas para identificar múltiplas soluções. Essa limitação surge porque mesmo com pontos de partida variados em múltiplas execuções de algoritmos, não há garantia de descoberta de soluções distintas.

Metodologias proeminentes para resolver problemas de otimização global, particularmente aqueles caracterizados pela presença de múltiplos extremos locais, incluem algoritmos evolutivos, otimização bayesiana e recozimento simulado.

Classificação de Pontos Críticos e Extremos

O problema de viabilidade

O problema de satisfatibilidade, também conhecido como problema de viabilidade, envolve a identificação de qualquer solução viável sem considerar seu valor objetivo. Este cenário pode ser conceituado como um exemplo específico de otimização matemática onde todas as soluções viáveis ​​compartilham um valor objetivo idêntico, tornando cada uma dessas soluções ótimas.

Numerosos algoritmos de otimização necessitam de um ponto viável inicial. Uma estratégia comum para conseguir isto envolve relaxar as condições de viabilidade através da introdução de uma variável de folga; folga suficiente garante que qualquer ponto de partida se torne viável. Posteriormente, esta variável de folga é minimizada até atingir um valor nulo ou negativo.

Existência de Optima

O teorema do valor extremo de Karl Weierstrass postula que uma função contínua de valor real definida em um conjunto compacto atingirá seus valores máximo e mínimo. De forma mais ampla, uma função semicontínua inferior em um conjunto compacto atingirá seu mínimo, enquanto uma função semicontínua superior em um conjunto compacto atingirá seu máximo.

Condições necessárias para otimização

Um teorema de Fermat afirma que os ótimos para problemas irrestritos ocorrem em pontos estacionários, caracterizados por uma primeira derivada zero ou gradiente da função objetivo. De forma mais abrangente, os ótimos podem estar localizados em pontos críticos onde a primeira derivada ou gradiente é zero ou indefinida, ou ao longo do limite da região viável. Uma equação, ou sistema de equações, especificando que a(s) primeira(s) derivada(s) é(ão) igual(is) a zero em um ótimo interior é chamada de 'condição de primeira ordem' ou um conjunto de condições de primeira ordem.

O método do multiplicador de Lagrange pode ser empregado para identificar ótimos em problemas sujeitos a restrições de igualdade. Para problemas que incorporam restrições de igualdade e/ou desigualdade, as 'condições de Karush-Kuhn-Tucker' fornecem uma estrutura para localizar ótimos.

Condições suficientes para otimização

Embora o teste da primeira derivada possa identificar extremos potenciais, ele não diferencia entre um mínimo, um máximo ou um ponto de sela. Para funções objetivo que são duas vezes diferenciáveis, essas distinções podem ser feitas examinando a segunda derivada ou a matriz Hessiana (a matriz das segundas derivadas) em problemas irrestritos. Em problemas restritos, é utilizado o Hessiano limitado, que inclui as segundas derivadas da função objetivo e das restrições. Os critérios que distinguem máximos ou mínimos de outros pontos estacionários são referidos como “condições de segunda ordem”. Se uma solução prospectiva satisfaz as condições de primeira ordem, então a sua adesão às condições de segunda ordem é suficiente para confirmar pelo menos a otimalidade local.

Sensibilidade e continuidade do Optima

O teorema do envelope elucida a alteração no valor de uma solução ótima em resposta a uma mudança em um parâmetro subjacente. O procedimento analítico para quantificar essa mudança é denominado estática comparativa.

O teorema do máximo de Claude Berge, introduzido em 1963, elucida a continuidade de uma solução ótima em relação aos seus parâmetros subjacentes.

Cálculo de Otimização

Em problemas de otimização irrestrita envolvendo funções duas vezes diferenciáveis, os pontos críticos são identificáveis como pontos estacionários onde o gradiente da função objetivo é zero. Mais amplamente, para problemas de minimização com funções Lipschitz convexas ou locais (como aquelas encontradas na minimização de funções de perda de redes neurais), um subgradiente zero confirma a identificação de um mínimo local. Além disso, a estimativa do momento positivo-negativo pode facilitar a fuga dos mínimos locais e alcançar a convergência para o mínimo global da função objetivo.

Os pontos críticos podem ser categorizados com base na definição da matriz Hessiana: um Hessiano definido positivo em um ponto crítico indica um mínimo local; um Hessiano definido negativo significa um máximo local; e um Hessiano indefinido sugere um ponto de sela.

Problemas de otimização restritos são frequentemente convertidos em formas irrestritas através da aplicação de multiplicadores de Lagrange. Além disso, a relaxação Lagrangeana oferece um método para derivar soluções aproximadas para problemas complexos e restritos.

Se a função objetivo for convexa, qualquer mínimo local representa inerentemente um mínimo global. Métodos numéricos eficientes, como técnicas de pontos interiores, estão disponíveis para minimizar funções convexas.

Convergência Global

Quando a função objetivo é não quadrática, vários algoritmos de otimização empregam estratégias para garantir que uma subsequência de iterações converge para uma solução ótima. Um método de garantia de convergência fundamental e amplamente utilizado envolve pesquisas lineares, que otimizam uma função ao longo de uma única dimensão. Uma abordagem alternativa e cada vez mais prevalecente para garantir a convergência utiliza regiões de confiança. Tanto as pesquisas de linha quanto as regiões de confiança são essenciais para as técnicas contemporâneas de otimização não diferenciáveis. Normalmente, os otimizadores globais apresentam desempenho mais lento em comparação com otimizadores locais sofisticados (por exemplo, BFGS); conseqüentemente, um otimizador global eficaz pode muitas vezes ser sintetizado iniciando um otimizador local a partir de vários pontos de partida distintos.

Técnicas de otimização computacional

Para resolver problemas de otimização, os pesquisadores podem empregar algoritmos que concluem dentro de um número finito de etapas, métodos iterativos projetados para convergir para uma solução para classes de problemas específicas ou heurísticas que oferecem soluções aproximadas, mesmo que suas iterações não convirjam necessariamente.

Algoritmos de otimização

• O algoritmo Simplex, desenvolvido por George Dantzig, foi projetado especificamente para programação linear.
• Extensões do algoritmo Simplex foram desenvolvidas para programação quadrática e programação linear-fracionária.
• Variantes do algoritmo Simplex são particularmente adequadas para problemas de otimização de rede.
• Algoritmos Combinatórios
• Algoritmos de otimização quântica

Métodos iterativos

Os métodos iterativos empregados para resolver problemas de programação não linear são diferenciados por sua dependência da avaliação de Hessianos, gradientes ou apenas valores de funções. Embora a avaliação de Hessianos (H) e gradientes (G) possa aumentar a taxa de convergência para funções suficientemente suaves onde essas quantidades existem, tais avaliações elevam simultaneamente a complexidade computacional (ou custo) por iteração. Em certos cenários, essa carga computacional pode se tornar proibitivamente alta.

Um critério primário para avaliar otimizadores é o número de avaliações de funções necessárias, pois isso muitas vezes constitui um esforço computacional significativo, frequentemente ultrapassando as operações internas do próprio otimizador, que processa principalmente N variáveis. Embora os derivados ofereçam informações detalhadas para otimizadores, seu cálculo é mais desafiador; por exemplo, aproximar o gradiente requer pelo menos avaliações de função N+1. Para aproximações de derivadas de segunda ordem, compiladas dentro da matriz Hessiana, o número de avaliações de funções aumenta com N². O método de Newton, que requer derivadas de segunda ordem, incorre em um custo computacional por iteração proporcional a N² chamadas de função, enquanto um otimizador de gradiente puro mais simples requer apenas N chamadas. No entanto, os otimizadores de gradiente normalmente exigem mais iterações do que o algoritmo de Newton. A escolha ideal em relação ao número de chamadas de função depende do problema específico.

• • Método de Newton
  • A programação quadrática sequencial representa uma metodologia baseada em Newton adequada para problemas restritos de pequena e média escala, com certas variantes capazes de lidar com desafios de grandes dimensões.
  • Os métodos de pontos interiores constituem uma ampla categoria de técnicas para otimização restrita, com alguns dependendo apenas de informações de (sub)gradiente e outros necessitando da avaliação de Hessianos.
• • Métodos de descida por coordenadas: algoritmos que ajustam iterativamente uma única coordenada em cada etapa.
  • Os métodos de gradiente conjugado são abordagens iterativas projetadas para problemas de grande escala. Teoricamente, esses métodos alcançam terminação finita quando aplicados a funções objetivo quadráticas; no entanto, esta terminação finita não é realizada na prática em sistemas de computação de precisão finita.
  • A descida gradiente, também conhecida como "descida mais íngreme" ou "subida mais íngreme", é um método de significado histórico e teórico. Embora inerentemente lento, experimentou um interesse renovado em identificar soluções aproximadas para problemas de escala excepcionalmente grande.
  • Os métodos de subgradiente representam uma abordagem iterativa para grandes funções de Lipschitz localmente, empregando gradientes generalizados. Conforme observado por Boris T. Polyak, os métodos de projeção de subgradiente têm semelhanças com os métodos de gradiente conjugado.
  • O método de descida de pacote é uma técnica iterativa para problemas de pequeno a médio porte envolvendo funções Lipschitz localmente, especialmente pertinente para problemas de minimização convexa e exibindo semelhanças com métodos de gradiente conjugado.
  • O método elipsóide é uma técnica iterativa para problemas de pequena escala com funções objetivo quaseconvexas. Possui significativo interesse teórico, notadamente para estabelecer a complexidade de tempo polinomial de certos problemas de otimização combinatória, e compartilha características com métodos Quasi-Newton.
  • O método do gradiente condicional (Frank-Wolfe) é projetado para a minimização aproximada de problemas especialmente estruturados com restrições lineares, particularmente no contexto de redes de tráfego. Para problemas gerais sem restrições, este método simplifica o método do gradiente, que é amplamente considerado obsoleto para a maioria das aplicações.
  • Os métodos quase-Newton são técnicas iterativas adequadas para problemas de média a grande escala (por exemplo, normalmente onde N < 1000).
  • O método de Aproximação Estocástica de Perturbação Simultânea (SPSA) é aplicado na otimização estocástica, que emprega uma aproximação de gradiente aleatória, mas eficiente.
• • Métodos de interpolação
  • Métodos de busca de padrões, possuindo propriedades de convergência superiores em comparação com a heurística Nelder-Mead (que utiliza simplices).
  • Descida do espelho

Heurísticas

Além de algoritmos de terminação finita e métodos iterativos convergentes, também existem heurísticas. Uma heurística é definida como um algoritmo que, embora não seja matematicamente garantido para localizar a solução ideal, mostra-se valioso em contextos práticos específicos.

Aplicativos

Mecânica

Problemas dentro da dinâmica de corpos rígidos, particularmente dinâmicas de corpos rígidos articulados, frequentemente necessitam de técnicas de programação matemática. Isso ocorre porque a dinâmica de corpos rígidos pode ser conceituada como a resolução de uma equação diferencial ordinária em uma variedade de restrições, onde essas restrições incluem diversas condições geométricas não lineares, por exemplo, "estes dois pontos devem sempre coincidir", "esta superfície não deve penetrar em nenhuma outra" ou "este ponto deve sempre estar em algum lugar desta curva". Além disso, o cálculo das forças de contato pode ser abordado através da solução de um problema de complementaridade linear, que também pode ser interpretado como um problema de programação quadrática (QP).

Numerosos problemas de projeto são frequentemente formulados como programas de otimização; este domínio é denominado otimização de design. A otimização de engenharia constitui um subconjunto, enquanto um subcampo distinto e em expansão é a otimização de projetos multidisciplinares, que, embora amplamente aplicável, encontrou utilidade particular em problemas de engenharia aeroespacial.

Esta abordagem é aplicável em cosmologia e astrofísica.

Economia e finanças

A ligação intrínseca entre economia e otimização de agentes é sublinhada por uma definição influente que caracteriza a economia como ciência como o "estudo do comportamento humano como uma relação entre fins e meios escassos" possuindo aplicações alternativas. A teoria contemporânea da otimização abrange abordagens tradicionais, ao mesmo tempo que se cruza com a teoria dos jogos e a análise do equilíbrio económico. Dentro do sistema de classificação do Journal of Economic Literature, programação matemática, metodologias de otimização e assuntos associados são categorizados em JEL:C61-C63.

A microeconomia frequentemente aborda problemas de otimização econômica, notadamente o problema de maximização da utilidade e seu duplo correspondente, o problema de minimização de despesas. Assumindo um comportamento consistente, presume-se que os consumidores maximizem a sua utilidade, enquanto que normalmente se presume que as empresas maximizam os seus lucros. Além disso, os agentes económicos são frequentemente modelados como avessos ao risco, indicando uma preferência por evitar riscos. A teoria da otimização também é aplicada para modelar preços de ativos, embora a estrutura matemática fundamental envolva a otimização de processos estocásticos em vez da otimização estática. Além disso, a teoria do comércio internacional emprega princípios de otimização para elucidar a dinâmica comercial entre os países. A otimização de portfólio serve como uma ilustração proeminente da otimização multiobjetivo no domínio econômico.

Os economistas têm utilizado a teoria do controle para modelar processos dinâmicos de tomada de decisão ao longo do tempo desde a década de 1970. Por exemplo, modelos de pesquisa dinâmica são utilizados para analisar a conduta no mercado de trabalho. Existe uma diferenciação fundamental entre abordagens de modelagem determinística e estocástica. Os macroeconomistas constroem modelos de equilíbrio geral estocástico dinâmico (DSGE), que caracterizam a dinâmica económica global como resultado das escolhas de otimização interdependentes feitas por trabalhadores, consumidores, investidores e entidades governamentais.

Engenharia Elétrica

As técnicas de otimização encontram inúmeras aplicações na engenharia elétrica, abrangendo áreas como projeto de filtros ativos, mitigação de campos dispersos em sistemas supercondutores de armazenamento de energia magnética, projeto de mapeamento espacial para estruturas de micro-ondas, antenas de aparelhos telefônicos e projeto baseado em eletromagnetismo. Desde a sua criação em 1993, metodologias de mapeamento espacial, muitas vezes combinadas com modelos substitutos empíricos ou baseados em física adequados, têm sido amplamente empregadas na otimização de projetos validados eletromagneticamente de componentes e antenas de micro-ondas. Além disso, as técnicas de otimização são essenciais para a análise do fluxo de potência.

Engenharia Civil

Os princípios de otimização são amplamente aplicados em vários domínios da engenharia civil. Notavelmente, a gestão da construção e a engenharia de transportes representam subdisciplinas-chave da engenharia civil que apresentam uma dependência substancial da otimização. Os desafios comuns da engenharia civil abordados através da otimização incluem operações de corte e aterro de estradas, avaliações do ciclo de vida de estruturas e infraestrutura, nivelamento de recursos, distribuição de recursos hídricos, gestão de tráfego e otimização de cronograma.

Pesquisa Operacional

A pesquisa operacional constitui outra disciplina que emprega extensivamente técnicas de otimização. Este campo também aproveita modelagem e simulação estocásticas para facilitar processos aprimorados de tomada de decisão. Há uma tendência crescente na pesquisa operacional de utilizar programação estocástica para modelar decisões dinâmicas que se ajustam em resposta a eventos em evolução; esses problemas são passíveis de soluções derivadas de otimização em larga escala e metodologias de otimização estocástica.

Engenharia de Controle

A otimização matemática desempenha um papel significativo no projeto de controladores contemporâneos. Sistemas de controle avançados, incluindo controle preditivo de modelo (MPC) e otimização em tempo real (RTO), integram a otimização matemática. Operando on-line, esses algoritmos determinam iterativamente valores para variáveis de decisão – por exemplo, aberturas de estrangulamento em uma planta de processo – resolvendo repetidamente um problema de otimização matemática que incorpora restrições do sistema e um modelo do sistema controlado.

Geofísica

Técnicas de otimização são aplicadas rotineiramente em desafios de estimativa de parâmetros geofísicos. A partir de um determinado conjunto de medições geofísicas, como registros sísmicos, é prática padrão deduzir as propriedades físicas e configurações geométricas de rochas e fluidos subterrâneos. A maioria dos problemas geofísicos são inerentemente não lineares, necessitando da aplicação generalizada de metodologias determinísticas e estocásticas.

Modelagem Molecular

Metodologias de otimização não linear são amplamente empregadas no campo da análise conformacional.

Biologia de Sistemas Computacionais

Metodologias de otimização são amplamente empregadas em vários domínios da biologia de sistemas computacionais, abrangendo construção de modelos, projeto de experimentos ideais, engenharia metabólica e biologia sintética. Especificamente, a programação linear tem sido utilizada para determinar os rendimentos máximos alcançáveis ​​de produtos de fermentação e para deduzir redes reguladoras genéticas a partir de diversos conjuntos de dados de microarranjos, juntamente com redes reguladoras transcricionais derivadas de dados de alto rendimento. Além disso, a programação não linear tem sido fundamental na análise do metabolismo energético e na sua aplicação à engenharia metabólica e na estimativa de parâmetros dentro das vias bioquímicas.

Aprendizado de máquina

Solucionadores

Notas

Notas

Boyd, Stephen P.; Vandenberghe, Lieven (2004). Otimização Convexa. Cambridge: Cambridge University Press. ISBN 0-521-83378-7.

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Otimização convexa. Cambridge: Cambridge University Press. ISBN 0-521-83378-7.Gill, P. E.; Murray, W.; Wright, M. H. (1982). Practical Optimization. Londres: Academic Press. ISBN 0-12-283952-8.Lee, Jon (2004). Um primeiro curso em otimização combinatória. Imprensa da Universidade de Cambridge. ISBN 0-521-01012-8.Nocedal, Jorge; Wright, Stephen J. (2006). Otimização Numérica (2ª ed.). Berlim: Springer. ISBN 0-387-30303-0.
  • "Árvore de decisão para software de otimização"."EE364a: Otimização Convexa I". Curso da Universidade de Stanford.Varoquaux, Gaël. "Otimização Matemática: Encontrando Mínimos de Funções".Fonte: Arquivo da TORIma Academia