Compare as técnicas primal-dual e primal com restrições objetivas, destacando as vantagens e desvantagens desta última.
Passo 1
O enunciado pede para comparar dois esquemas de solução de problemas de otimização – o primal-dual e o primal com restrições objetivas – e destacar vantagens e desvantagens do segundo. Vamos precisar entender o que cada método faz em termos de formulação de Lagrangianos, atualização de variáveis primais e (quando houver) variáveis duais.
Passo 2
No método primal-dual, introduzimos multiplicadores de Lagrange
para cada restrição e trabalhamos simultaneamente nas variáveis primais
e duais
. O esquema geral envolve:
. Construir o Lagrangeano
onde
são as restrições.
. Atualizar
buscando minimizar
(passo primal).
. Atualizar
buscando maximizar
por algum passo de gradiente ou projeção (passo dual).
. Repetir até convergência ao ponto que satisfaz condições de Karush–Kuhn–Tucker (KKT).
Passo 3
No método primal com restrições objetivas, em vez de usar variáveis duais explíticas, incorporamos penalidades ou barreiras diretamente na função objetivo. Por exemplo, se temos
, resolvemos
onde
é uma penalidade (por ex.
) ou barreira (por ex.
) e
é um parâmetro que regula a força da penalização. Assim, trabalhamos apenas com
, ajustando
para forçar o cumprimento das restrições.
Passo 4
Vantagens do primal com restrições objetivas
Implementação mais simples, pois só há atualização de
.
Dispensa tratamento explícito de projeção ou manutenção de
.
Bom em problemas onde projetar sobre a região viável é custoso, mas avaliar penalidades é barato.
Desvantagens do primal com restrições objetivas
A escolha de
(e do tipo de penalidade) é crítica: muito grande pode deixar o problema mal condicionado; muito pequeno pode violar restrições.
Convergência lenta se o termo de penalidade não cresce adequadamente conforme nos aproximamos da fronteira viável.
Não garante, em geral, satisfação exata das restrições em iterações intermediárias (apenas no limite quando
ou
, conforme a formulação).
Resposta
O esquema primal com restrições objetivas simplifica a implementação ao lidar só com variáveis primais, mas depende fortemente da escolha de parâmetros de penalização/barreira e normalmente exige estratégias adicionais para garantir que as restrições sejam satisfeitas com precisão e obter boa taxa de convergência.