Otimização restrita

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

Na otimização matemática , a otimização restrita (em alguns contextos chamada de otimização de restrições ) é o processo de otimizar uma função objetivo em relação a algumas variáveis ​​na presença de restrições nessas 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 as condições para as variáveis ​​que devem ser satisfeitas, ourestrições flexíveis , que têm alguns valores de variáveis ​​que são penalizados na função objetivo se, e com base na medida em que, as condições das variáveis ​​não forem satisfeitas.

Relação com problemas de satisfação de restrições

O problema de otimização de restrições (COP) é ​​uma generalização significativa do modelo clássico de problema de satisfação de restrições (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.

Formulário geral

Um problema geral de minimização restrita pode ser escrito da seguinte forma: [2]

Ondeesão restrições que devem ser satisfeitas (elas são chamadas de restrições rígidas ) eé a função objetivo que precisa ser otimizada sujeita às restrições.

Em alguns problemas, freqüentemente chamados de problemas de otimização de restrições , a função objetivo é, na verdade, a soma das funções de custo, cada uma das quais penaliza a extensão (se houver) em que uma restrição flexível (uma restrição que é preferida, mas não exigida para ser satisfeita) é violado.

Métodos de solução

Muitos algoritmos de otimização restritos podem ser adaptados ao caso irrestrito, muitas vezes através 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. Isto é referido como o 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 maximizarsujeito 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 parae consequentemente,.

Multiplicador de Lagrange

Se o problema restrito possui 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 ​​menos o número original de restrições de igualdade. Alternativamente, se as restrições são todas restrições de igualdade e são 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 solucionados.

Programação linear

Se a função objetivo e todas as restrições rígidas são lineares e algumas restrições rígidas são 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, ou por métodos de pontos interiores que funcionam em tempo polinomial.

Programação não linear

Se a função objetivo ou algumas das restrições são não lineares e algumas restrições são desigualdades, então o problema é um problema de programação não linear .

Programação quadrática

Se todas as restrições rígidas são lineares e algumas são desigualdades, mas a função objetivo é quadrática, o problema é um problema de programação quadrática . É um tipo de programação não linear. Ainda pode ser resolvido em tempo polinomial pelo método elipsóide se a função objetivo for convexa ; caso contrário, o problema pode ser NP hard .

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 ligar

A otimização de restrições pode ser resolvida por algoritmos branch-and-bound . São algoritmos de backtracking que armazenam o custo da melhor solução encontrada durante a execução e a utilizam 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.

Assumindo que o custo deve ser minimizado, a eficiência desses algoritmos depende de como é avaliado o custo que pode ser obtido ao estender uma solução parcial. De fato, se o algoritmo pode retroceder a partir de uma solução parcial, parte da busca é ignorada. Quanto menor o custo estimado, melhor o algoritmo, pois um custo estimado menor é mais provável de ser menor do que o melhor custo de solução encontrado até o momento.

Por outro lado, esse custo estimado não pode ser inferior ao custo efetivo que pode ser obtido estendendo a solução, caso contrário o algoritmo pode retroceder enquanto existir uma solução melhor que a melhor encontrada até o momento. Como resultado, o algoritmo requer um limite superior no custo que pode ser obtido ao estender 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 intervalares . [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 flexível separadamente. Para cada restrição flexível, é assumido o valor máximo possível para qualquer atribuição às variáveis ​​não atribuídas. A soma desses valores é um limite superior porque as restrições flexíveis não podem assumir um valor mais alto. É exato porque os valores máximos de restrições flexíveis podem derivar de diferentes avaliações: uma restrição flexível pode ser máxima paraenquanto outra restrição é máxima para.

Pesquisa de boneca russa

Este método [6] executa um algoritmo branch-and-bound emproblemas, ondeé o número de variáveis. Cada um desses problemas é o subproblema obtido pela eliminação de uma sequência de variáveisdo problema original, juntamente com as restrições que os contêm. Depois do problema das variáveisé resolvido, seu custo ótimo pode ser usado como um limite superior enquanto resolve os outros problemas,

Em particular, a estimativa de custo de uma solução comà medida que as variáveis ​​não atribuídas são adicionadas 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 este último problema já foi resolvido. Mais precisamente, o custo de restrições flexíveis 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 flexíveis contendo apenas variáveis ​​não atribuídas é estimado usando a solução ótima do problema correspondente, que já é conhecida neste ponto.

Há semelhança entre o método Russian Doll Search e a programação dinâmica . Assim como a programação dinâmica, o Russian Doll Search resolve subproblemas para resolver todo o problema. Mas, enquanto a Programação Dinâmica combina diretamente os resultados obtidos em subproblemas para obter o resultado de todo o problema, o Russian Doll Search apenas os utiliza como limites durante sua busca.

Eliminação do bucket

O algoritmo de eliminação de bucket pode ser adaptado para otimização de restrições. Uma determinada variável pode realmente ser removida do problema substituindo todas as restrições flexíveis que a contêm por uma nova restrição flexível. O custo dessa nova restrição é calculado 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 flexíveis que o contêm, esão suas variáveis, exceto, a nova restrição flexível é definida por:

A eliminação de bucket funciona com uma ordenação (arbitrária) das variáveis. Cada variável está associada a um bucket de restrições; o bucket de uma variável contém todas as restrições que têm a variável mais alta na ordem. A eliminação do bucket procede da última variável para a primeira. Para cada variável, todas as restrições do bucket são substituídas conforme acima para remover a variável. A restrição resultante é então colocada no bucket apropriado.

Veja também

Referências

  1. ^ 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 , Manual de Programação de Restrições, Elsevier, vol. 2, pp. 3–12, doi : 10.1016/s1574-6526(06)80005-2 , recuperado em 2019-10-04
  2. ^ Martins, JRRA; Ning, A. (2021). Otimização de Projetos de Engenharia . Cambridge University Press. ISBN 978-1108833417.
  3. ^ 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 
  4. ^ Prosser, Mike (1993). "Otimização restrita por substituição". Matemática Básica para Economistas . Nova York: Routledge. págs. 338–346. ISBN 0-415-08424-5.
  5. ^ Líder, Jeffery J. (2004). Análise Numérica e Computação Científica . Addison Wesley. ISBN 0-201-73499-0.
  6. Verfaillie, Gérard, Michel Lemaître e Thomas Schiex. " Pesquisa de boneca russa para resolver problemas de otimização de restrições ." AAAI/IAAI, Vol. 1. 1996.

Leitura adicional