direita|thumb|Gráfico de uma superfície dada por . O máximo global em é indicado pelo ponto azul.
thumb|Busca de mínimo por Nelder-Mead na função de Simionescu. Os vértices do simplex são ordenados por seus valores, com 1 tendo o menor valor (melhor ).|alt=
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."The Nature of Mathematical Programming ," Mathematical Programming Glossary, INFORMS Computing Society. É 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 de algum conjunto para os números reais Procura-se: um elemento tal que para todo ("minimização") ou tal que para todo ("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:
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 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, é algum subconjunto do espaço euclidiano , frequentemente especificado por um conjunto de restrições, igualdades ou desigualdades que os membros de devem satisfazer. O domínio de é chamado de espaço de busca ou conjunto de escolha, enquanto os elementos de são denominados soluções candidatas ou soluções viáveis.
A função é 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 é definido como um elemento para o qual existe algum tal que:
a expressão é válida;
isto é, em alguma região ao redor de , 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:
Isso denota o valor mínimo da função objetivo , ao escolher a partir do conjunto dos números reais . O valor mínimo nesse caso é 1, ocorrendo em .
De forma similar, a notação:
solicita o valor máximo da função objetivo , onde 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:
ou equivalentemente:
Isso representa o valor (ou valores) do argumento no intervalo que minimiza (ou minimizam) a função objetivo (o valor mínimo real da função não é o que o problema requer). Nesse caso, a resposta é , já que é inviável, isto é, não pertence ao conjunto viável.
Analogamente:
ou equivalentemente:
representa o par (ou pares) que maximiza (ou maximizam) o valor da função objetivo , com a restrição adicional de que pertença ao intervalo (novamente, o valor máximo atingido pela expressão não é o foco). Nesse caso, as soluções são os pares da forma e , onde varia sobre todos os inteiros.
Os operadores e às vezes são grafados como e , 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 é 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 é 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).