Questão 2: Produzindo expressões para atualização das variáveis duais Lagrangeanas e para o subgradiente de
(a) Para cada problema trabalhado na questão 1, indique a expressão de atualização das Variáveis Duais Lagrageanas.
(b) Para ambos os problemas abordados na questão 1, mostre a expressão que permite determinar o subgradiente de
.
(a) Para cada problema trabalhado na questão 1, indique a expressão de atualização das Variáveis Duais Lagrageanas.
(b) Para ambos os problemas abordados na questão 1, mostre a expressão que permite determinar o subgradiente de
Passo 1
O enunciado pede duas coisas:
- (a) indicar a expressão de atualização das variáveis duais Lagrangeanas para cada um dos dois problemas tratados na questão 1;
- (b) mostrar a expressão que permite determinar o subgradiente de
(interpreto aqui como as relações úteis para subgradiente do Lagrangiano e, principalmente, do dual).
Não foi enviado o texto da questão 1. Como não posso acessar esses problemas específicos, vou considerar os dois casos canônicos que costumam aparecer em exercícios de Lagrange/Dual:
- Problema I (desigualdades): minimização de
sujeita a , onde tem componentes . - Problema II (igualdades): minimização de
sujeita a , onde tem componentes .
Vou derivar passo a passo as fórmulas de atualização das variáveis duais e as expressões do subgradiente que valem para esses dois casos canônicos. Essas fórmulas são as que normalmente o professor espera ver na prova.
Passo 2
Definição do Lagrangiano e do dual — explicação simples e o que cada símbolo significa.
- Para o Problema I (desigualdades) define-se o Lagrangiano
onde:
-
é a variável primal; -
é o vetor de multiplicadores (variáveis duais), com a restrição (componentewise); -
tem as funções de desigualdade . -
Para o Problema II (igualdades) define-se o Lagrangiano
onde agora
é livre (sem restrição de sinal) e
são as funções de igualdade
.
O dual (função dual) é definido, em ambos os casos, por
O problema dual é
, com
no caso de desigualdades e
no caso de igualdades.
Passo 3
Subgradiente do Lagrangiano e do dual — conceito e derivação didática passo a passo.
Primeiro: subgradiente de
visto como função de
com
fixo.
- Observação:
é linear em . Portanto, quando está fixo,
no caso de desigualdades, e
no caso de igualdades. Em termos de subgradiente (caso de não diferenciabilidade), a coleção de subgradientes de
em
contém exatamente esses vetores.
Agora: subgradiente da função dual
.
- Seja
(ou um minimizador aproximado). Então, para qualquer ,
Também
. Subtraindo,
Isto mostra que
é um subgradiente de
em
; em notação,
- Analogamente, no caso de igualdade, se
então
Resumo didático: o subgradiente do dual
no ponto
é dado avaliando as restrições no minimizador primal correspondente
. Em fórmulas:
(no caso de desigualdades) e
(no caso de igualdades).
Passo 4
Regra de atualização das variáveis duais — ideia da subida por subgradiente (dual ascent).
Queremos resolver
. Como
é concava (em problemas convexos de primal), podemos aplicar um método de subida por subgradiente: a iteração básica é
onde:
-
é um subgradiente do dual em ; -
é o passo (step-size); -
é a projeção ortogonal no conjunto factível de (por exemplo, projeção na ortant não-negativo quando necessário).
Substituindo a expressão do subgradiente obtida no passo anterior, tomando
(ou um minimizador aproximado
), obtemos as fórmulas concretas:
-
Para o Problema I (desigualdades
): - subgradiente do dual:
; - projeção em
é a projeção componente a componente, isto é aplicado componente a componente; - atualização prática:
onde a projeçãoé aplicada componente a componente. - subgradiente do dual:
-
Para o Problema II (igualdades
): - subgradiente do dual:
; - não há restrição de não-negatividade, logo
e a projeção é identidade; - atualização prática:
- subgradiente do dual:
Explicação das notações importantes:
-
é tipicamente o minimizador exato de . Na prática de prova pode-se também usar um aproximado (por exemplo obtido por uma etapa de otimização primal) — então substitui-se por . - A escolha do passo
pode ser: pequena fixa, ou sequência que satisfaça e (condição clássica para convergência por subgradiente), ou regras como passo de Polyak se o ótimo dual conhecido for usado.
Passo 5
Derivação curta que mostra por que a atualização acima faz sentido (intuição).
- Queremos aumentar
. Pela desigualdade de subgradiente, para qualquer ,
(essa forma heurística mostra que mover na direção
aumenta
se
for pequeno). Assim a subida por subgradiente
é a versão não-diferenciável da subida por gradiente. Se houver restrição
projetamos de volta para o conjunto factível.
- Como
, isso dá exatamente a regra para desigualdades, e para igualdades.
Passo 6
Exemplo curto e concreto (para fixar a ideia).
Considere o problema unidimensional:
- Lagrangiano:
, com . - Minimização em
: derivando . Assim . - Subgradiente do dual:
. - Atualização dual por subgradiente com passo
:
Isto ilustra concretamente a fórmula e a projeção em ação.
Resposta
(a) Problema com desigualdades
:
\nProblema com igualdades
:
\n(b) Subgradiente de
em
com
fixo:
(ou
no caso de igualdades).\nSubgradiente da função dual
em
:
(ou
para igualdades), onde
.