análise quantitativa para encontrar soluções ideais

Otimização

22 min de leitura
Em 56 idiomas
2 imagens

A otimização matemática (também referida como programação matemática) é a seleção do melhor elemento, com relação a determinados critérios, a partir de um conjunto de alternativas disponíveis. É geralmente dividida em dois subcampos: otimização discreta e otimização contínua. Problemas de otimização surgem em todas as disciplinas quantitativas, desde a ciência da computação e a engenharia até a pesquisa operacional e a economia, e o desenvolvimento de métodos de resolução tem sido de interesse para a matemática há séculos.

Na abordagem mais geral, um problema de otimização consiste em maximizar ou minimizar uma função real escolhendo sistematicamente valores de entrada a partir de um conjunto permitido e computando o valor da função. A generalização da teoria e das técnicas de otimização para outras formulações constitui uma ampla área da matemática aplicada.

Problemas de otimização

Os problemas de otimização podem ser divididos em duas categorias, dependendo de as variáveis serem contínuas ou discretas:

Um problema de otimização com variáveis discretas é conhecido como uma otimização discreta, na qual um objeto matemático como um número inteiro, uma permutação ou um grafo deve ser encontrado a partir de um conjunto contável.
Um problema com variáveis contínuas é conhecido como uma otimização contínua, no qual argumentos ótimos pertencentes a um conjunto contínuo devem ser encontrados. Eles podem incluir problemas restritos e problemas multimodais.

Um problema de otimização pode ser representado da seguinte maneira:

Dado: uma função

f\colon A\to \mathbb {R}

de algum conjunto

A

para os números reais

Procura-se: um elemento

\mathbf {x} _{0}\in A

tal que

f(\mathbf {x} _{0})\leq f(\mathbf {x})

para todo

\mathbf {x} \in A

("minimização") ou tal que

f(\mathbf {x} _{0})\geq f(\mathbf {x})

para todo

\mathbf {x} \in A

("maximização").

Tal formulação é chamada de problema de otimização ou problema de programação matemática (um termo que não tem relação direta com a programação de computadores, mas ainda em uso, por exemplo, na programação linear — ver História abaixo). Muitos problemas reais e teóricos podem ser modelados sob esse arcabouço geral.

Visto que a seguinte equivalência é válida:

f(\mathbf {x} _{0})\geq f(\mathbf {x})\iff -f(\mathbf {x} _{0})\leq -f(\mathbf {x}),

basta resolver apenas problemas de minimização. No entanto, a perspectiva oposta de considerar apenas problemas de maximização também é válida.

Problemas formulados por meio dessa técnica nas áreas da física podem se referir à metodologia como minimização de energia, abordando o valor da função $f$ como representativo da energia do sistema que está sendo modelado. No aprendizado de máquina, é sempre necessário avaliar continuamente a qualidade de um modelo de dados usando uma função de perda (ou função de custo), na qual um mínimo implica um conjunto de parâmetros potencialmente ótimos com um erro ótimo (o menor possível).

Tipicamente, $A$ é algum subconjunto do espaço euclidiano $\mathbb {R} ^{n}$ , frequentemente especificado por um conjunto de restrições, igualdades ou desigualdades que os membros de $A$ devem satisfazer. O domínio $A$ de $f$ é chamado de espaço de busca ou conjunto de escolha, enquanto os elementos de $A$ são denominados soluções candidatas ou soluções viáveis.

A função $f$ é variadamente chamada de função objetivo, função critério, função de perda, função de custo (minimização), função utilidade ou função de aptidão (maximização) ou, em determinados campos, função de energia ou funcional de energia. Uma solução viável que minimiza (ou maximiza) a função objetivo é chamada de solução ótima.

Na matemática, os problemas convencionais de otimização são geralmente enunciados em termos de minimização.

Um mínimo local $\mathbf {x} ^{*}$ é definido como um elemento para o qual existe algum $\delta >0$ tal que:

\forall \mathbf {x} \in A\quad {\text{onde}}\quad \|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta,

a expressão $f(\mathbf {x} ^{*})\leq f(\mathbf {x})$ é válida;

isto é, em alguma região ao redor de $\mathbf {x} ^{*}$ , todos os valores da função são maiores ou iguais ao valor nesse elemento. Máximos locais são definidos de forma semelhante.

Enquanto um mínimo local é pelo menos tão bom quanto quaisquer elementos vizinhos, um mínimo global é pelo menos tão bom quanto todo elemento viável. Geralmente, a menos que a função objetivo seja convexa em um problema de minimização, pode haver vários mínimos locais. Em um problema convexo, se houver um mínimo local que seja interior (não na fronteira do conjunto de elementos viáveis), ele também será o mínimo global; entretanto, um problema não convexo pode possuir mais de um mínimo local, nem todos os quais precisam ser mínimos globais.

Um grande número de algoritmos propostos para resolver problemas não convexos — incluindo a maioria dos solucionadores comercialmente disponíveis — não é capaz de fazer distinção entre soluções localmente ótimas e soluções globalmente ótimas, tratando as primeiras como soluções reais para o problema original. A otimização global é o ramo da matemática aplicada e da análise numérica que se dedica ao desenvolvimento de algoritmos determinísticos capazes de garantir convergência em tempo finito para a verdadeira solução ótima de um problema não convexo.

Notação

Problemas de otimização são frequentemente expressos com notação específica. Aqui estão alguns exemplos:

Valor mínimo e máximo de uma função

Considere a seguinte notação:

\min _{x\in \mathbb {R} }\left(x^{2}+1\right)

Isso denota o valor mínimo da função objetivo $x^{2}+1$ , ao escolher $x$ a partir do conjunto dos números reais $\mathbb {R}$ . O valor mínimo nesse caso é 1, ocorrendo em $x=0$ .

De forma similar, a notação:

\max _{x\in \mathbb {R} }2x

solicita o valor máximo da função objetivo $2x$ , onde $x$ pode ser qualquer número real. Nesse caso, não existe tal máximo, visto que a função objetivo é ilimitada, sendo a resposta "infinito" ou "indefinido".

Argumentos de entrada ótimos

Considere a seguinte notação:

{\underset {x\in (-\infty,-1]}{\operatorname {arg\,min} }}x^{2}+1,

ou equivalentemente:

{\underset {x}{\operatorname {arg\,min} }}x^{2}+1,\quad {\text{sujeito a:}}\quad x\in (-\infty,-1].

Isso representa o valor (ou valores) do argumento $x$ no intervalo $(-\infty,-1]$ que minimiza (ou minimizam) a função objetivo $x^{2}+1$ (o valor mínimo real da função não é o que o problema requer). Nesse caso, a resposta é $x=-1$ , já que $x=0$ é inviável, isto é, não pertence ao conjunto viável.

Analogamente:

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

ou equivalentemente:

{\underset {x,\;y}{\operatorname {arg\,max} }}x\cos y,\quad {\text{sujeito a:}}\quad x\in [-5,5],\;y\in \mathbb {R},

representa o par (ou pares) $\{x,y\}$ que maximiza (ou maximizam) o valor da função objetivo $x\cos y$ , com a restrição adicional de que $x$ pertença ao intervalo $[-5,5]$ (novamente, o valor máximo atingido pela expressão não é o foco). Nesse caso, as soluções são os pares da forma $\{5,2k\pi \}$ e $\{-5,(2k+1)\pi \}$ , onde $k$ varia sobre todos os inteiros.

Os operadores $\operatorname {arg\,min}$ e $\operatorname {arg\,max}$ às vezes são grafados como $\operatorname {argmin}$ e $\operatorname {argmax}$ , e significam argumento do mínimo e argumento do máximo.

História

Fermat e Lagrange descobriram fórmulas baseadas em cálculo diferencial para identificar ótimos, enquanto Newton e Gauss propuseram métodos iterativos para convergir em direção a um ótimo.

O termo "programação linear" para determinados casos de otimização deve-se a George Dantzig, embora grande parte da teoria tivesse sido introduzida por Leonid Kantorovich em 1939. ("Programação", nesse contexto, não se refere à programação de computadores, mas provém do uso de "programa" pelas Forças Armadas dos Estados Unidos para designar propostas de cronogramas de treinamento e logística, que eram os problemas estudados por Dantzig na época). Dantzig publicou o algoritmo simplex em 1947, e também John von Neumann e outros pesquisadores trabalharam nos aspectos teóricos da programação linear (como a teoria da dualidade) por volta do mesmo período.

Outros pesquisadores notáveis na otimização matemática incluem:

Richard Bellman
Dimitri Bertsekas
Michel Bierlaire
Stephen P. Boyd
Roger Fletcher
Martin Grötschel
Ronald A. Howard
Fritz John
Narendra Karmarkar
William Karush
Leonid Khachiyan
Bernard Koopman
Harold Kuhn
László Lovász
David Luenberger
Arkadi Nemirovski
Yurii Nesterov
Lev Pontryagin
R. Tyrrell Rockafellar
Naum Z. Shor
Albert Tucker

Principais subcampos

A 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. Isso pode ser visto como um caso particular da programação não linear ou como generalização da programação linear ou quadrática convexa.
- A programação linear (PL), um tipo de programação convexa, estuda o caso no qual a função objetivo $f$ é linear e as restrições são especificadas utilizando apenas igualdades e desigualdades lineares. Tal conjunto viável de restrições é chamado de poliedro ou de politopo se for limitado.
- A programação cônica de segunda ordem (SOCP) é uma classe de programas convexos que inclui determinados tipos de programas quadráticos.
- A programação semidefinida (SDP) é um subcampo da otimização convexa em que as variáveis fundamentais são matrizes semidefinidas. Trata-se de uma generalização da programação linear e quadrática convexa.
- A programação cônica é uma forma geral de programação convexa. PL, SOCP e SDP podem ser vistas como programas cônicos com tipos apropriados de cones.
- A programação geométrica é uma técnica mediante a qual restrições de desigualdade e funções objetivo expressas como posinômios e restrições de igualdade expressas como monômios podem ser transformadas em um programa convexo.
A programação inteira estuda programas lineares nos quais algumas ou todas as variáveis são restritas a assumir valores inteiros. Essa formulação não é convexa e, em geral, é consideravelmente mais difícil do que a programação linear ordinária.
A programação quadrática permite que a função objetivo contenha termos quadráticos, enquanto o conjunto viável deve ser especificado por igualdades e desigualdades lineares. Para formas específicas do termo quadrático, constitui uma forma de programação convexa.
A programação fracionária estuda a otimização de razões entre duas funções não lineares. A classe especial de programas fracionários côncavos pode ser transformada em um problema de otimização convexa.
A programação não linear estuda o caso geral em que a função objetivo, as restrições ou ambas contêm partes não lineares. Pode ou não constituir um programa convexo. De forma geral, o fato de o programa ser ou não convexo afeta diretamente a complexidade de sua resolução.
A programação estocástica estuda o caso no qual algumas das restrições ou parâmetros dependem de variáveis aleatórias.
A otimização robusta é, assim como a programação estocástica, uma tentativa de modelar a incerteza nos dados subjacentes ao problema de otimização. A otimização robusta visa encontrar soluções que sejam válidas sob todas as realizações possíveis das incertezas definidas por um conjunto de incerteza.
A otimização combinatória preocupa-se com problemas nos quais o conjunto de soluções viáveis é discreto ou pode ser reduzido a um conjunto discreto.
A otimização estocástica é empregada com medições de funções sujeitas a ruído estocástico ou entradas aleatórias no processo de busca.
A otimização em dimensão infinita estuda o caso em que o conjunto de soluções viáveis é um subconjunto de um espaço de dimensão infinita, tal como um espaço de funções.
Heurísticas e meta-heurísticas fazem poucas ou nenhumas suposições estruturais sobre o problema em otimização. Habitualmente, heurísticas não garantem que uma solução ótima seja necessariamente encontrada. Por outro lado, heurísticas são utilizadas para encontrar soluções aproximadas para muitos problemas complexos de otimização.
A satisfação de restrições estuda o caso em que a função objetivo $f$ é constante (muito utilizada na inteligência artificial, particularmente no raciocínio automatizado).
- A programação com restrições é um paradigma de programação no qual as relações entre variáveis são expressas na forma de restrições.
A programação disjuntiva é utilizada onde pelo menos uma restrição deve ser satisfeita, mas não necessariamente todas. Apresenta utilidade particular no sequenciamento e escalonamento de tarefas (scheduling).
O mapeamento de espaço (space mapping) é um conceito para modelagem e otimização de sistemas de engenharia com precisão de modelo de alta fidelidade (fino), explorando um modelo grosseiro ou modelo substituto fisicamente significativo e computacionalmente mais leve.

Em uma série de subcampos, as técnicas são projetadas prioritariamente para otimização em contextos dinâmicos (isto é, tomada de decisão ao longo do tempo):

O cálculo das variações preocupa-se em encontrar a melhor maneira de atingir determinado objetivo, tal como encontrar uma superfície cujo contorno seja uma curva específica, mas com a menor área possível.
A teoria do controle ótimo é uma generalização do cálculo das variações que introduz políticas de controle.
A programação dinâmica é a abordagem para resolver o problema de otimização estocástica com parâmetros estocásticos, aleatórios e desconhecidos no modelo. Ela estuda o caso no qual a estratégia de otimização baseia-se na divisão do problema em subproblemas menores. A equação que descreve a relação entre esses subproblemas é denominada equação de Bellman.
A programação matemática com restrições de equilíbrio (MPEC) ocorre quando as restrições incluem desigualdades variacionais ou relações de complementaridade.

Otimização multiobjetivo

A adição de mais de um objetivo a um problema de otimização introduz complexidade adicional. Por exemplo, para otimizar um projeto estrutural, deseja-se uma estrutura que seja simultaneamente leve e rígida. Quando dois objetivos entram em conflito, um compromisso (trade-off) deve ser estabelecido. Pode haver um projeto mais leve, um projeto mais rígido e um número infinito de projetos intermediários que equilibram peso e rigidez. O conjunto de projetos de compromisso que melhoram um critério às custas de pelo menos um outro critério é conhecido como o conjunto de Pareto. A curva traçada relacionando peso contra rigidez dos melhores projetos é conhecida como a fronteira de Pareto.

Um projeto é classificado como "Pareto-ótimo" (equivalentemente, "Pareto-eficiente" ou pertencente ao conjunto de Pareto) se não for dominado por nenhum outro projeto: se ele for pior do que outro projeto sob determinados aspectos e não for superior sob nenhum aspecto, então ele é dominado e não é Pareto-ótimo.

A escolha entre as soluções "Pareto-ótimas" para determinar a "solução preferida" cabe ao tomador de decisão. Em outras palavras, formular o problema como uma otimização multiobjetivo sinaliza que certas informações estão ausentes: os objetivos desejáveis são dados, mas as combinações relativas entre eles não estão previamente hierarquizadas. Em alguns casos, as informações faltantes podem ser obtidas por meio de sessões interativas com o tomador de decisão.

Problemas de otimização multiobjetivo foram posteriormente generalizados em problemas de otimização vetorial, nos quais a ordem (parcial) não é mais regida unicamente pela ordenação de Pareto.

Otimização multimodal ou global

Problemas de otimização são frequentemente multimodais; isto é, possuem múltiplas boas soluções. Elas podem ser todas globalmente boas (com o mesmo valor de função de custo) ou pode haver uma mistura de soluções globalmente boas e soluções localmente boas. Obter todas (ou pelo menos algumas das) múltiplas soluções é o objetivo de um otimizador multimodal.

Técnicas clássicas de otimização, devido à sua abordagem iterativa local, não apresentam desempenho satisfatório quando empregadas para obter soluções múltiplas, uma vez que não há garantia de que soluções diferentes serão alcançadas mesmo utilizando pontos de partida distintos em múltiplas execuções do algoritmo.

Abordagens usuais para problemas de otimização global, nos quais múltiplos extremos locais podem estar presentes, incluem algoritmos evolutivos, otimização bayesiana e recozimento simulado (simulated annealing).

Classificação de pontos críticos e extremos

Problema de viabilidade

O problema de satisfatibilidade, também denominado problema de viabilidade, consiste simplesmente em encontrar qualquer solução viável, independentemente do valor da função objetivo. Isso pode ser interpretado como um caso especial da otimização matemática no qual o valor objetivo é constante para todas as soluções e, portanto, qualquer solução encontrada é ótima.

Muitos algoritmos de otimização necessitam partir de um ponto viável. Uma forma de obter esse ponto é relaxar as condições de viabilidade por meio de uma variável de folga; com folga suficiente, qualquer ponto inicial torna-se viável. Em seguida, minimiza-se essa variável de folga até que ela seja nula ou negativa.

Existência

O teorema de Weierstrass estabelece que uma função real contínua definida em um conjunto compacto atinge seus valores máximo e mínimo. De forma mais ampla, uma função semicontínua inferiormente em um conjunto compacto atinge seu mínimo; uma função semicontínua superiormente em um conjunto compacto atinge seu valor máximo.

Condições necessárias para otimalidade

Um dos teoremas de Fermat afirma que os ótimos de problemas irrestritos são encontrados em pontos estacionários, onde a primeira derivada ou o gradiente da função objetivo se anula (ver teste da primeira derivada). Mais geralmente, podem ser encontrados em pontos críticos, onde a primeira derivada ou o gradiente da função objetivo é nulo ou indefinido, ou na fronteira do conjunto de escolha. Uma equação (ou sistema de equações) que estabelece que a(s) primeira(s) derivada(s) é(são) igual(is) a zero em um ótimo interior é chamada de 'condição de primeira ordem' ou conjunto de condições de primeira ordem.

Ótimos de problemas com restrições de igualdade podem ser determinados pelo método dos multiplicadores de Lagrange. Os ótimos de problemas com restrições de igualdade e/ou desigualdade podem ser encontrados utilizando-se as condições de Karush–Kuhn–Tucker.

Condições suficientes para otimalidade

Embora o teste da primeira derivada identifique pontos que podem ser extremos, esse teste não distingue se um ponto é um mínimo, um máximo ou nenhum dos dois. Quando a função objetivo é duas vezes diferenciável, esses casos podem ser distinguidos avaliando-se a segunda derivada ou a matriz de segundas derivadas (denominada matriz hessiana) em problemas irrestritos, ou a matriz de segundas derivadas da função objetivo e das restrições (chamada de hessiana orlada) em problemas com restrições. As condições que distinguem máximos ou mínimos de outros pontos estacionários são denominadas 'condições de segunda ordem' (ver teste da segunda derivada). Se uma solução candidata satisfaz as condições de primeira ordem, o atendimento simultâneo das condições de segunda ordem é suficiente para estabelecer, ao menos, a otimalidade local.

Sensibilidade e continuidade dos ótimos

O teorema do envelope descreve como o valor de uma solução ótima varia quando um parâmetro subjacente é modificado. O processo de calcular essa variação é denominado estática comparativa.

O teorema do máximo de Claude Berge (1963) descreve a continuidade de uma solução ótima em função de parâmetros subjacentes.

Cálculo de otimização

Para problemas irrestritos com funções duas vezes diferenciáveis, certos pontos críticos podem ser obtidos encontrando-se os pontos nos quais o gradiente da função objetivo se anula (isto é, os pontos estacionários). Mais genericamente, um subgradiente nulo atesta que um mínimo local foi alcançado para problemas de minimização com funções convexas e outras funções localmente lipschitzianas, encontradas frequentemente na minimização de funções de perda em redes neurais. A estimativa de momento positivo-negativo permite contornar mínimos locais e convergir para o mínimo global da função objetivo.

Ademais, pontos críticos podem ser classificados por meio da positividade ou negatividade da matriz hessiana: se a hessiana for positiva definida em um ponto crítico, o ponto será um mínimo local; se for negativa definida, o ponto será um máximo local; por fim, se for indefinida, o ponto corresponderá a algum tipo de ponto de sela.

Problemas com restrições podem ser frequentemente convertidos em problemas irrestritos com o auxílio dos multiplicadores de Lagrange. A relaxação lagrangiana também pode fornecer soluções aproximadas para problemas restritos de alta complexidade.

Quando a função objetivo é uma função convexa, qualquer mínimo local será simultaneamente um mínimo global. Existem técnicas numéricas eficientes para minimizar funções convexas, tais como os métodos de pontos interiores.

Convergência global

Mais genericamente, se a função objetivo não for uma função quadrática, muitos métodos de otimização empregam estratégias auxiliares para assegurar que alguma subsequência de iterações convirja para uma solução ótima. O primeiro método clássico (e ainda popular) para assegurar a convergência baseia-se na busca linear (line search), que otimiza a função unidimensionalmente ao longo de uma direção de descida. Um segundo método, amplamente utilizado, emprega regiões de confiança (trust regions). Tanto a busca linear quanto as regiões de confiança são empregadas em métodos modernos de otimização não diferenciável. Habitualmente, um otimizador global opera com velocidade substancialmente inferior à de otimizadores locais avançados (como o BFGS); por esse motivo, muitas vezes constrói-se um otimizador global eficiente executando o otimizador local a partir de múltiplos pontos de partida distintos.

Técnicas computacionais de otimização

Para solucionar problemas, pesquisadores utilizam algoritmos que terminam em um número finito de passos, métodos iterativos que convergem para uma solução (em classes específicas de problemas) ou heurísticas que fornecem soluções aproximadas para determinados problemas (embora suas iterações não necessariamente convirjam formalmente).

Algoritmos de otimização

Algoritmo simplex de George Dantzig, projetado para programação linear
Extensões do algoritmo simplex, projetadas para programação quadrática e programação linear-fracionária
Variantes do algoritmo simplex especialmente adaptadas para otimização de redes
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 diferenciam-se conforme avaliam hessianas, gradientes ou apenas valores da própria função. Embora a avaliação de hessianas (H) e gradientes (G) aumente a taxa de convergência para funções nas quais essas grandezas existem e variam com suficiente suavidade, tais avaliações aumentam a complexidade computacional (ou custo computacional) de cada iteração. Em certos casos, o custo computacional por iteração pode tornar-se excessivamente proibitivo.

Um critério fundamental na escolha de otimizadores é a quantidade de avaliações de função requeridas, visto que isso frequentemente representa a maior parcela do esforço computacional total, superando o custo das operações internas do algoritmo sobre as $N$ variáveis. As derivadas fornecem informações direcionais detalhadas, mas demandam esforço computacional considerável: por exemplo, aproximar numericamente o gradiente consome pelo menos $N+1$ avaliações da função. Para aproximações de derivadas de segunda ordem (reunidas na matriz hessiana), o número de avaliações escala na ordem de $N^{2}$ . O método de Newton requer derivadas de segunda ordem, exigindo na ordem de $N^{2}$ chamadas de função por iteração, enquanto um otimizador puramente baseado em gradiente requer apenas $N$ . Todavia, otimizadores baseados em gradiente habitualmente exigem muito mais iterações do que o algoritmo de Newton. A escolha do método mais vantajoso quanto ao total de avaliações depende estritamente da estrutura do problema considerado.

Métodos que avaliam hessianas (ou aproximam hessianas usando diferenças finitas):
- Método de Newton
- Programação quadrática sequencial (SQP): método baseado em Newton para problemas restritos de pequena e média escala. Algumas versões admitem problemas de alta dimensionalidade.
- Métodos de pontos interiores: ampla classe de métodos para otimização restrita, alguns dos quais utilizam apenas informações de (sub)gradientes, enquanto outros exigem o cálculo explícito de hessianas.
Métodos que avaliam gradientes ou aproximam gradientes (ou até subgradientes):
- Métodos de descida por coordenadas: algoritmos que atualizam uma única coordenada a cada iteração.
- Métodos de gradiente conjugado: métodos iterativos voltados a problemas de grande porte. (Teoricamente, terminam em um número finito de passos com funções quadráticas, mas essa terminação finita não é observada estritamente na prática em computadores de precisão finita).
- Gradiente descendente (ou "descida mais íngreme" / "subida mais íngreme"): método de interesse histórico e teórico, que experimentou renovado interesse no aprendizado de máquina para encontrar soluções aproximadas em problemas massivos.
- Métodos de subgradiente: método iterativo para problemas de grande porte com funções localmente lipschitzianas usando gradientes generalizados. Segundo Boris T. Polyak, métodos de projeção de subgradiente assemelham-se aos métodos de gradiente conjugado.
- Método de feixes de descida (bundle method): método iterativo para problemas de pequeno e médio porte com funções localmente lipschitzianas, especialmente na minimização convexa (assemelha-se a métodos de gradiente conjugado).
- Método do elipsoide: método iterativo para problemas de pequena escala com funções objetivo quase-convexas e de grande relevância teórica, particularmente ao estabelecer a complexidade de tempo polinomial de certos problemas de otimização combinatória. Guarda similaridades com métodos quase-Newton.
- Método do gradiente condicional (Frank–Wolfe): para minimização aproximada de problemas estruturados com restrições lineares, especialmente em redes de tráfego. Para problemas gerais irrestritos, reduz-se ao método do gradiente ordinário.
- Métodos quase-Newton: métodos iterativos para problemas de médio e grande porte (por exemplo, $N<1000$ ).
- Método de aproximação estocástica por perturbação simultânea (SPSA): voltado para otimização estocástica, empregando aproximações aleatórias eficientes do gradiente.
Métodos que avaliam apenas valores da função: caso o problema seja continuamente diferenciável, gradientes podem ser aproximados por diferenças finitas, permitindo o emprego de métodos baseados em gradientes.
- Métodos de interpolação
- Métodos de busca por padrão (pattern search), que exibem melhores propriedades de convergência do que a heurística de Nelder–Mead.
- Descida em espelho (mirror descent)

Heurísticas

Além de algoritmos exatos (com terminação finita) e métodos iterativos (convergentes), existem abordagens heurísticas. Uma heurística é qualquer algoritmo que não oferece garantia matemática formal de encontrar a solução ótima, mas que se mostra útil e eficaz em problemas práticos complexos. Algumas heurísticas conhecidas:

Evolução diferencial
Relaxamento dinâmico
Algoritmos evolutivos
Algoritmos genéticos
Subida de encosta (hill climbing) com reinício aleatório
Algoritmo memético
Heurística simplicial de Nelder–Mead: heurística popular para minimização aproximada (livre de gradientes)
Otimização por enxame de partículas (PSO)
Recozimento simulado (simulated annealing)
Tunelamento estocástico
Busca tabu

Aplicações

Mecânica

Problemas em dinâmica de corpos rígidos (em particular dinâmica de corpos rígidos articulados) frequentemente requerem técnicas de programação matemática, uma vez que a dinâmica de corpos rígidos pode ser tratada como a resolução de uma equação diferencial ordinária sobre uma variedade de restrições; as restrições são geométricas e não lineares, tais como "estes dois pontos devem coincidir permanentemente", "esta superfície não deve penetrar esta outra" ou "este ponto deve permanecer sobre esta curva". Além disso, o problema de computar forças de contato pode ser formulado resolvendo-se um problema de complementaridade linear (LCP), que também pode ser visto como um problema de programação quadrática (QP).

Muitos problemas de projeto estrutural podem ser formulados como programas de otimização, disciplina conhecida como otimização de projeto (design optimization). Um subconjunto dessa área é a otimização em engenharia, e um desdobramento moderno relevante é a otimização de projeto multidisciplinar (MDO), largamente aplicada em problemas da engenharia aeroespacial.

Essa abordagem também possui aplicações consolidadas em cosmologia e astrofísica.

Economia e finanças

A economia é tão estritamente ligada à otimização de agentes que uma definição influente descreve a ciência econômica como o "estudo do comportamento humano como uma relação entre fins e meios escassos" com usos alternativos. A teoria da otimização moderna integra a teoria tradicional de otimização, mas sobrepõe-se também à teoria dos jogos e ao estudo do equilíbrio econômico. Os códigos do Journal of Economic Literature (classificação JEL) categorizam a programação matemática, técnicas de otimização e tópicos afins sob as seções JEL:C61-C63.

Na microeconomia, o problema de maximização da utilidade e o seu problema dual, o problema de minimização do dispêndio, constituem problemas formais de otimização econômica. Desde que atuem de forma consistente, assume-se que os consumidores maximizam sua utilidade, enquanto as empresas habitualmente maximizam seu lucro. Além disso, os agentes econômicos são frequentemente modelados como avessos ao risco, preferindo mitigar exposições estocásticas. Modelos de precificação de ativos também recorrem à teoria da otimização, embora a formulação subjacente baseie-se na otimização de processos estocásticos em vez de otimização estática. A teoria do comércio internacional utiliza a otimização para justificar padrões de trocas comerciais entre nações. A otimização de carteiras de investimento (portfólios) é um exemplo canônico de otimização multiobjetivo aplicada às finanças.

Desde a década de 1970, economistas modelam decisões dinâmicas intertemporais recorrendo à teoria do controle. Por exemplo, modelos de busca dinâmicos são utilizados no estudo do mercado de trabalho. Uma distinção essencial é feita entre modelos determinísticos e estocásticos. Macroeconomistas constroem modelos de equilíbrio geral dinâmico estocástico (DSGE) que caracterizam a dinâmica macroeconômica global como resultado das decisões ótimas e interdependentes de trabalhadores, consumidores, investidores e governos.

Engenharia elétrica

Aplicações comuns de técnicas de otimização na engenharia elétrica incluem o projeto de filtros ativos, a redução de campos magnéticos dispersos em sistemas supercondutores de armazenamento de energia magnética (SMES), o projeto de componentes de micro-ondas por mapeamento de espaço, antenas de telefonia celular e o projeto eletromagnético em geral. A otimização com validação eletromagnética de circuitos e antenas tem feito uso extensivo de modelos substitutos (baseados em física ou empíricos) associados a metodologias de mapeamento de espaço desde a formulação inicial desse método em 1993. Métodos de otimização também são fundamentais na análise de fluxo de potência em sistemas elétricos de potência (fluxo de potência ótimo).

Engenharia civil

A otimização é extensamente utilizada na engenharia civil. A gestão da construção e a engenharia de transportes estão entre os ramos que mais dependem de algoritmos de otimização. Problemas comuns envolvem terraplenagem (corte e aterro de rodovias), análise de ciclo de vida de estruturas e infraestruturas, nivelamento de recursos, alocação de recursos hídricos, gestão de tráfego e otimização de cronogramas.

Pesquisa operacional

Outra área que faz uso extensivo de técnicas de otimização é a pesquisa operacional. A pesquisa operacional emprega modelagem estocástica e simulação para subsidiar tomadas de decisão estratégicas. De forma crescente, utiliza a programação estocástica para modelar decisões dinâmicas adaptativas a eventos externos; problemas dessa ordem são resolvidos por meio de algoritmos de otimização em larga escala e métodos de otimização estocástica.

Engenharia de controle

A otimização matemática é utilizada amplamente no projeto de controladores modernos. Controladores avançados como o controle preditivo baseado em modelo (MPC) e a otimização em tempo real (RTO) fundamentam-se em otimização matemática. Esses algoritmos operam em linha e determinam repetidamente valores para as variáveis de decisão (como a abertura de válvulas de estrangulamento em uma planta industrial), resolvendo iterativamente problemas de otimização matemática com restrições e modelos dinâmicos do sistema físico controlado.

Geofísica

Métodos de otimização são empregados com regularidade em problemas de estimativa de parâmetros geofísicos. A partir de dados geofísicos medidos (por exemplo, registros sísmicos), busca-se determinar as propriedades físicas e a geometria tridimensional das camadas rochosas e fluidos subsuperficiais. A maioria dos problemas geofísicos é não linear, empregando-se tanto formulações determinísticas quanto métodos estocásticos.

Modelagem molecular

Métodos de otimização não linear são amplamente aplicados na análise conformacional de moléculas.

Biologia computacional de sistemas

Técnicas de otimização são aplicadas em várias vertentes da biologia computacional de sistemas, como na construção de modelos, planejamento ótimo de experimentos, engenharia metabólica e biologia sintética. A programação linear tem sido aplicada para estimar os rendimentos máximos teóricos de produtos em fermentações industriais, bem como para inferir redes de regulação gênica a partir de conjuntos de dados de microarranjos e redes de regulação transcricional a partir de dados de alto rendimento. A programação não linear tem sido utilizada para analisar o metabolismo energético celular e para apoiar o projeto metabólico e a estimação paramétrica em vias bioquímicas.

Aprendizado de máquina

Leitura adicional

Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (em inglês). Cambridge: Cambridge University Press. ISBN 0-521-83378-7
Gill, P. E.; Murray, W.; Wright, M. H. (1982). Practical Optimization (em inglês). Londres: Academic Press. ISBN 0-12-283952-8
Lee, Jon (2004). A First Course in Combinatorial Optimization (em inglês). [S.l.]: Cambridge University Press. ISBN 0-521-01012-8
Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (em inglês) 2.ª ed. Berlim: Springer. ISBN 0-387-30303-0
G. L. Nemhauser, A. H. G. Rinnooy Kan e M. J. Todd (eds.): Optimization, Elsevier, (1989).
Stanislav Walukiewicz: Integer Programming, Springer, ISBN 978-90-481-4068-8, (1990).
R. Fletcher: Practical Methods of Optimization, 2.ª ed., Wiley, (2000).
Panos M. Pardalos: Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Springer, ISBN 978-1-4419-4829-8, (2000).
Xiaoqi Yang, K. L. Teo, Lou Caccetta (eds.): Optimization Methods and Applications, Springer, ISBN 978-0-7923-6866-3, (2001).
Panos M. Pardalos e Mauricio G. C. Resende (eds.): Handbook of Applied Optimization, Oxford University Press, ISBN 978-0-19-512594-8, (2002).
Wil Michiels, Emile Aarts e Jan Korst: Theoretical Aspects of Local Search, Springer, ISBN 978-3-642-07148-5, (2006).
Der-San Chen, Robert G. Batson e Yu Dang: Applied Integer Programming: Modeling and Solution, Wiley, ISBN 978-0-470-37306-4, (2010).
Mykel J. Kochenderfer e Tim A. Wheeler (2019). Algorithms for Optimization. The MIT Press. ISBN 978-0-262-03942-0.
Vladislav Bukshtynov: Optimization: Success in Practice, CRC Press (Taylor & Francis), ISBN 978-1-032-22947-8, (2023).
Rosario Toscano: Solving Optimization Problems with the Heuristic Kalman Algorithm: New Stochastic Methods, Springer, ISBN 978-3-031-52458-5, (2024).
Immanuel M. Bomze, Tibor Csendes, Reiner Horst e Panos M. Pardalos: Developments in Global Optimization, Kluwer Academic, ISBN 978-1-4419-4768-0, (2010).

Ler a seguir

Programação não linear Condições de Karush-Kuhn-Tucker Otimização global Otimização combinatória Dualidade (otimização)

Aprendizagem de máquina onlinemétodo de aprendizagem de máquina

Texto da Wikipédia, CC BY-SA 4.0 · Artigo de origem