Muitos algoritmos de optimização sem restrições podem ser adaptados ao caso restrito, muitas vezes através do uso de um método de penalização. No entanto, os passos de pesquisa tomados pelo método sem constrangimentos podem ser inaceitáveis para o problema constrangido, levando a uma falta de convergência. Isto é referido como o efeito Maratos.
Restrições de igualdadeEditar
Método de substituiçãoEditar
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. A idéia é substituir a restrição na função objetiva para criar uma função composta que incorpora o efeito da restrição. Por exemplo, suponha que o objetivo é maximizar f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}
subordinado a x + y = 10 {\i1}displaystyle x+y=10
. A restrição implica y = 10 – x {\\displaystyle y=10-x}
, que pode ser substituído na função objetiva para criar p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}}
. A condição necessária de primeira ordem dá ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\frac {\parcial p}{\parcial x}}=10-2x=0}
, que pode ser resolvido para x = 5 {\i1}displaystyle x=5}
e, consequentemente, y = 10 – 5 = 5 {\\i1}displaystyle y=10-5=5}
.
Multiplicador de LagrangeEdit
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 sem restrições, 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 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 objetiva, deixando um problema sem restrições em um número menor de variáveis.
Restrições de desigualdadeEditar
Com restrições de desigualdade, o problema pode ser caracterizado em termos das condições de otimização geométrica, condições de Fritz John e condições de Karush-Kuhn-Tucker, sob as quais problemas simples podem ser resolvidos.
Programação linearEditar
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. Isto pode ser resolvido pelo método simplex, que normalmente funciona em tempo polinomial no tamanho do problema mas não é garantido, ou por métodos de pontos interiores que são garantidos de funcionar em tempo polinomial.
Programação não linearEditar
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áticaEditar
Se todas as restrições rígidas são lineares e algumas são desigualdades, mas a função objetivo é quadrática, o 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 elipsóide se a função objetivo for convexa; caso contrário, o problema pode ser NP hard.
KKT conditionsEdit
Allowing inequality constraints, a abordagem KKT para programação não linear generaliza o método dos multiplicadores de Lagrange. Ele pode ser aplicado sob diferenciais e convexidade.
Branch and boundEdit
A optimização de restrições pode ser resolvida por algoritmos de branch-and-bound. Estes são algoritmos de backtracking que armazenam o custo da melhor solução encontrada durante a execução e que a utilizam para evitar parte da pesquisa. 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 faz backtracks, ao invés de tentar estender esta solução.
Assumindo que o custo deve ser minimizado, a eficiência destes algoritmos depende de como o custo que pode ser obtido com a extensão de uma solução parcial é avaliado. Na verdade, se o algoritmo pode voltar atrás a partir de uma solução parcial, parte da pesquisa é ignorada. Quanto menor o custo estimado, melhor o algoritmo, pois um custo estimado mais baixo é mais provável que seja inferior ao melhor custo da solução encontrada até agora.
Por outro lado, este custo estimado não pode ser inferior ao custo efetivo que pode ser obtido com a extensão da solução, pois de outra forma o algoritmo poderia retroceder enquanto uma solução melhor do que a melhor encontrada até agora existe. Como resultado, o algoritmo requer um limite superior no custo que pode ser obtido ao estender uma solução parcial, e este limite superior deve ser o menor possível.
Uma variação desta abordagem chamada método de Hansen usa métodos de intervalo. Ele implementa inerentemente restrições retangulares.
Funções de limite de primeira escolhaEditar
Uma forma de avaliar este 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 de função não podem assumir um valor superior. Ela é exata porque os valores máximos das restrições soft podem derivar de avaliações diferentes: uma restrição soft pode ser máxima para x = um {\i1}estilo de exibição x=a}.
enquanto outra restrição é máxima para x = b {\displaystyle x=b}
.
Pesquisa de bonecos russosEditar
Este método executa um algoritmo de ramificação e encadernação em n {\i1}displaystyle n
problemas, onde n {\i1}displaystyle n
é o número de variáveis. Cada um desses problemas é o sub-problema obtido por uma sequência de variáveis x 1 , … , x i {\i1}, {\i}ldots ,x_{\i}}
do problema original, juntamente com as restrições que os contêm. Após o problema nas variáveis x i + 1 , … , x n {\i+1},{\i+1},{\i}ldots ,x_{n}}
está resolvido, o seu custo óptimo pode ser usado como limite superior enquanto se resolve os outros problemas,
Em particular, a estimativa de custo de uma solução com x i + 1 , … , x n {\i+1},\i}ldots ,x_{n}}
uma vez que as variáveis não atribuídas são adicionadas ao custo que deriva das variáveis avaliadas. Virtualmente, isto corresponde em 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 das restrições brandas contendo tanto variáveis atribuídas como não atribuídas é estimado como acima (ou usando um outro método arbitrário); o custo das restrições brandas contendo apenas variáveis não atribuídas é, em vez disso, estimado usando a solução ótima do problema correspondente, que já é conhecida neste ponto.
Existe similaridade entre o método Russian Doll Search e a Programação Dinâmica. Assim como a Programação Dinâmica, a Doll Search Russa resolve os sub-problemas para resolver todo o problema. Mas, enquanto a Programação Dinâmica combina diretamente os resultados obtidos nos sub-problemas para obter o resultado de todo o problema, a Russian Doll Search só os usa como limites durante sua busca.
Eliminação de baldesEditar
O algoritmo de eliminação de baldes pode ser adaptado para otimização de restrições. Uma determinada variável pode de fato ser removida do problema substituindo todas as restrições suaves que a contenham por uma nova restrição suave. O custo dessa nova restrição é calculado assumindo um valor máximo para cada valor da variável removida. Formalmente, se x {\displaystyle x}
é a variável a ser removida, C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}}
são as restrições suaves que o contêm, e y 1 , … , y m {\i1}displaystyle y_{1},{\i}ldots ,y_{m}}
são as suas variáveis excepto x {\displaystyle x}
, a nova restrição suave é definida por: C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . C(y_{1}=a_{1},{1},ldots ,y_{n}=a_{n}=a_{n})==max _{a}sum _{i}C_{i}(x=a,y_{1}=a_{1},{1}ldots ,y_{n}=a_{n}).}
A eliminação de baldes funciona com uma ordenação (arbitrária) das variáveis. Cada variável está associada a um balde de restrições; o balde de uma variável contém todas as restrições tendo a variável com o maior número de restrições na ordem. A eliminação de balde procede da última variável para a primeira. Para cada variável, todas as restrições do balde são substituídas como acima para remover a variável. A restrição resultante é então colocada na caçamba apropriada.