Otimização restrita
Em otimização matemática , otimização restrita (em alguns contextos chamada otimização de restrição ) é o processo de otimizar uma função objetivo com relação a algumas variáveis na presença de restrições sobre essas variáveis. A função objetivo é uma função de custo ou função de energia , que deve ser minimizada , ou uma função de recompensa ou função de utilidade , que deve ser maximizada . As restrições podem ser restrições rígidas , que definem condições para as variáveis que devem ser satisfeitas, ou restrições flexíveis , que têm alguns valores de variáveis que são penalizados na função objetivo se, e com base na extensão em que, as condições sobre as variáveis não forem satisfeitas.
Relação com problemas de satisfação de restrições
O problema de otimização restrita (COP) é uma generalização significativa do modelo clássico de problema de satisfação de restrição (CSP). [1] COP é um CSP que inclui uma função objetivo a ser otimizada. Muitos algoritmos são usados para lidar com a parte de otimização.
Forma geral
Um problema geral de minimização restrita pode ser escrito da seguinte forma: [2]
onde e são restrições que devem ser satisfeitas (chamadas de restrições rígidas ), e é a função objetivo que precisa ser otimizada sujeita às restrições.
Em alguns problemas, frequentemente chamados de problemas de otimização de restrições , a função objetivo é, na verdade, a soma de funções de custo, cada uma das quais penaliza a extensão (se houver) em que uma restrição suave (uma restrição que é preferida, mas não necessariamente satisfeita) é violada.
Métodos de solução
Muitos algoritmos de otimização restritos podem ser adaptados ao caso irrestrito, frequentemente por meio do uso de um método de penalidade . No entanto, as etapas de busca realizadas pelo método irrestrito podem ser inaceitáveis para o problema restrito, levando a uma falta de convergência. Isso é conhecido como efeito Maratos. [3]
Restrições de igualdade
Método de substituição
Para problemas muito simples, digamos uma função de duas variáveis sujeitas a uma única restrição de igualdade, é mais prático aplicar o método de substituição. [4] A ideia é substituir a restrição na função objetivo para criar uma função composta que incorpore o efeito da restrição. Por exemplo, suponha que o objetivo seja maximizar sujeito a . A restrição implica , que pode ser substituído na função objetivo para criar . A condição necessária de primeira ordem fornece , que pode ser resolvido para e, consequentemente, .
Multiplicador de Lagrange
Se o problema restrito tiver apenas restrições de igualdade, o método dos multiplicadores de Lagrange pode ser usado para convertê-lo em um problema irrestrito cujo número de variáveis é o número original de variáveis mais o número original de restrições de igualdade. Alternativamente, se as restrições forem todas restrições de igualdade e forem todas lineares, elas podem ser resolvidas para algumas das variáveis em termos das outras, e as primeiras podem ser substituídas fora da função objetivo, deixando um problema irrestrito em um número menor de variáveis.
Restrições de desigualdade
Com restrições de desigualdade, o problema pode ser caracterizado em termos das condições de otimalidade geométrica, condições de Fritz John e condições de Karush–Kuhn–Tucker , sob as quais problemas simples podem ser resolvidos.
Programação linear
Se a função objetivo e todas as restrições rígidas forem lineares e algumas restrições rígidas forem desigualdades, então o problema é um problema de programação linear . Isso pode ser resolvido pelo método simplex , que geralmente funciona em tempo polinomial no tamanho do problema, mas não é garantido que funcione, ou por métodos de ponto interior que são garantidos que funcionam em tempo polinomial.
Programação não linear
Se a função objetivo ou algumas das restrições forem não lineares, e algumas restrições forem desigualdades, então o problema é um problema de programação não linear .
Programação quadrática
Se todas as restrições rígidas forem lineares e algumas forem desigualdades, mas a função objetivo for quadrática, o problema é um problema de programação quadrática . É um tipo de programação não linear. Ele ainda pode ser resolvido em tempo polinomial pelo método elipsoide se a função objetivo for convexa ; caso contrário, o problema pode ser NP difícil .
Condições KKT
Permitindo restrições de desigualdade, a abordagem KKT para programação não linear generaliza o método dos multiplicadores de Lagrange. Pode ser aplicado sob diferenciabilidade e convexidade.
Ramificar e limitar
A otimização de restrição pode ser resolvida por algoritmos branch-and-bound . Esses são algoritmos de backtracking que armazenam o custo da melhor solução encontrada durante a execução e o usam para evitar parte da busca. Mais precisamente, sempre que o algoritmo encontra uma solução parcial que não pode ser estendida para formar uma solução de melhor custo do que o melhor custo armazenado, o algoritmo retrocede, em vez de tentar estender essa solução.
Supondo que o custo seja minimizado, a eficiência desses algoritmos depende de como o custo que pode ser obtido da extensão de uma solução parcial é avaliado. De fato, se o algoritmo puder retroceder de uma solução parcial, parte da busca é ignorada. Quanto menor o custo estimado, melhor o algoritmo, pois um custo estimado menor tem mais probabilidade de ser menor do que o melhor custo de solução encontrado até agora.
Por outro lado, esse custo estimado não pode ser menor do que o custo efetivo que pode ser obtido estendendo a solução, pois, caso contrário, o algoritmo pode voltar atrás enquanto uma solução melhor do que a melhor encontrada até agora existir. Como resultado, o algoritmo requer um limite superior no custo que pode ser obtido estendendo uma solução parcial, e esse limite superior deve ser o menor possível.
Uma variação dessa abordagem, chamada método de Hansen, usa métodos de intervalo . [5] Ele implementa inerentemente restrições retangulares.
Funções delimitadoras de primeira escolha
Uma maneira de avaliar esse limite superior para uma solução parcial é considerar cada restrição suave separadamente. Para cada restrição suave, o valor máximo possível para qualquer atribuição às variáveis não atribuídas é assumido. A soma desses valores é um limite superior porque as restrições suaves não podem assumir um valor mais alto. É exato porque os valores máximos das restrições suaves podem derivar de diferentes avaliações: uma restrição suave pode ser máxima para enquanto outra restrição é máxima para .
Busca por bonecas russas
Este método [6] executa um algoritmo branch-and-bound em problemas, onde é o número de variáveis. Cada um desses problemas é o subproblema obtido pela remoção de uma sequência de variáveis do problema original, juntamente com as restrições que as contêm. Após o problema sobre variáveis ser resolvido, seu custo ótimo pode ser usado como um limite superior ao resolver os outros problemas,
Em particular, a estimativa de custo de uma solução tendo como variáveis não atribuídas é adicionada ao custo que deriva das variáveis avaliadas. Virtualmente, isso corresponde a ignorar as variáveis avaliadas e resolver o problema nas não atribuídas, exceto que o último problema já foi resolvido. Mais precisamente, o custo de restrições suaves contendo variáveis atribuídas e não atribuídas é estimado como acima (ou usando um outro método arbitrário); o custo de restrições suaves contendo apenas variáveis não atribuídas é estimado usando a solução ótima do problema correspondente, que já é conhecida neste ponto.
Há similaridade entre o método Russian Doll Search e a programação dinâmica . Assim como a programação dinâmica, a Russian Doll Search resolve subproblemas para resolver o problema todo. Mas, enquanto a Dynamic Programming combina diretamente os resultados obtidos em subproblemas para obter o resultado do problema todo, a Russian Doll Search os usa apenas como limites durante sua busca.
Eliminação de balde
O algoritmo de eliminação de bucket pode ser adaptado para otimização de restrições. Uma dada variável pode ser de fato removida do problema substituindo todas as restrições suaves que a contêm por uma nova restrição suave. O custo desta nova restrição é computado assumindo um valor máximo para cada valor da variável removida. Formalmente, se é a variável a ser removida, são as restrições suaves que a contêm, e são suas variáveis exceto , a nova restrição suave é definida por:
A eliminação de bucket funciona com uma ordenação (arbitrária) das variáveis. Cada variável é associada a um bucket de restrições; o bucket de uma variável contém todas as restrições tendo a variável como a mais alta na ordem. A eliminação de bucket procede da última variável para a primeira. Para cada variável, todas as restrições do bucket são substituídas como acima para remover a variável. A restrição resultante é então colocada no bucket apropriado.
Veja também
- Mínimos quadrados restritos
- Otimização de restrição distribuída
- Problema de satisfação de restrições (CSP)
- Programação de restrições
- Programação inteira
- Projeção métrica
- Método de penalidade
- Superiorização
Referências
- ^ Rossi, Francesca; van Beek, Peter; Walsh, Toby (2006-01-01), Rossi, Francesca; van Beek, Peter; Walsh, Toby (eds.), "Capítulo 1 – Introdução", Fundamentos da Inteligência Artificial , Handbook of Constraint Programming, vol. 2, Elsevier, pp. 3–12, doi :10.1016/s1574-6526(06)80005-2 , recuperado em 2019-10-04
- ^ Martins, JRRA; Ning, A. (2021). Otimização de Projeto de Engenharia. Cambridge University Press. ISBN 978-1108833417.
- ^ Wenyu Sun; Ya-Xiang Yuan (2010). Teoria e métodos de otimização: programação não linear , Springer, ISBN 978-1441937650 . pág. 541
- ^ Prosser, Mike (1993). "Otimização Restrita por Substituição". Matemática Básica para Economistas . Nova York: Routledge. pp. 338–346. ISBN 0-415-08424-5.
- ^ Líder, Jeffery J. (2004). Análise Numérica e Computação Científica . Addison Wesley. ISBN 0-201-73499-0.
- ^ Verfaillie, Gérard, Michel Lemaître e Thomas Schiex. "Busca de boneca russa para resolver problemas de otimização de restrições." AAAI/IAAI, Vol. 1. 1996.
Leitura adicional
- Bertsekas, Dimitri P. (1982). Otimização Restrita e Métodos de Multiplicadores de Lagrange . Nova York: Academic Press. ISBN 0-12-093480-9.
- Dechter, Rina (2003). Processamento de Restrições . Morgan Kaufmann. ISBN 1-55860-890-7.