Otimização
A otimizaçã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.
Imagem: f_mafra · BY-SA · Openverse
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 pode ser representado da seguinte maneira: 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: 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 {\displaystyle 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).
Imagem: Assembleia Legislativa do Paraná (ALEP) · PDM · Openverse
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
Isso denota o valor mínimo da função objetivo x 2 + 1 {\displaystyle x^{2}+1} , ao escolher x {\displaystyle x} a partir do conjunto dos números reais R {\displaystyle \mathbb {R} } . O valor mínimo nesse caso é 1, ocorrendo em x = 0 {\displaystyle x=0} . solicita o valor máximo da função objetivo 2 x {\displaystyle 2x} , onde x {\displaystyle 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
Isso representa o valor (ou valores) do argumento x {\displaystyle x} no intervalo ( − ∞ , − 1 ] {\displaystyle (-\infty ,-1]} que minimiza (ou minimizam) a função objetivo x 2 + 1 {\displaystyle x^{2}+1} (o valor mínimo real da função não é o que o problema requer). Nesse caso, a resposta é x = − 1 {\displaystyle x=-1} , já que x = 0 {\displaystyle x=0} é inviável, isto é, não pertence ao conjunto viável. representa o par (ou pares) { x , y } {\displaystyle \{x,y\}} que maximiza (ou maximizam) o valor da função objetivo x cos y {\displaystyle x\cos y} , com a restrição adicional de que x {\displaystyle x} pertença ao intervalo [ − 5 , 5 ] {\displaystyle [-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 , 2 k π } {\displaystyle \{5,2k\pi \}} e { − 5 , ( 2 k + 1 ) π } {\displaystyle \{-5,(2k+1)\pi \}} , onde k {\displaystyle k} varia sobre todos os inteiros.
Imagem: Assembleia Legislativa do Paraná (ALEP) · PDM · Openverse
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:
Imagem: Assembleia Legislativa do Paraná (ALEP) · PDM · Openverse
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):
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.
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.
Imagem: clcontato · BY · Openverse
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.
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.
Imagem: Problemas_SBSE.png: Fabriciogf derivative work: Fabriciogf (talk) · BY · Openverse
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).
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 {\displaystyle 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 {\displaystyle 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 {\displaystyle N^{2}} . O método de Newton requer derivadas de segunda ordem, exigindo na ordem de N 2 {\displaystyle N^{2}} chamadas de função por iteração, enquanto um otimizador puramente baseado em gradiente requer apenas N {\displaystyle 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.
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:
Imagem: Assembleia Legislativa do Paraná (ALEP) · PDM · Openverse
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. Métodos de otimização não linear são amplamente aplicados na análise conformacional de moléculas. 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.
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).
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.
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.
