Questão 2: Produzindo expressões para atualização das variáveis duais Lagrangeanas e para o subgradiente de L(x, u)
(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 L(x, u).

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 L(x,u) (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 f(x) sujeita a g(x)\le 0, onde g:\mathbb{R}^n\to\mathbb{R}^m tem componentes g_i(x).
  • Problema II (igualdades): minimização de f(x) sujeita a h(x)=0, onde h:\mathbb{R}^n\to\mathbb{R}^p tem componentes h_j(x).
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
L(x,u)=f(x)+u^{\!T}g(x),
onde:
  • x\in\mathbb{R}^n é a variável primal;
  • u\in\mathbb{R}^m é o vetor de multiplicadores (variáveis duais), com a restrição u\ge 0 (componentewise);
  • g(x)\in\mathbb{R}^m tem as m funções de desigualdade g_i(x)\le 0.
  • Para o Problema II (igualdades) define-se o Lagrangiano
L(x,u)=f(x)+u^{\!T}h(x),
onde agora u\in\mathbb{R}^p é livre (sem restrição de sinal) e h(x)\in\mathbb{R}^p são as funções de igualdade h_j(x)=0.
O dual (função dual) é definido, em ambos os casos, por
q(u)=\inf_{x}L(x,u).
O problema dual é \max_{u\in\mathcal{U}} q(u), com \mathcal{U}=\{u\ge0\} no caso de desigualdades e \mathcal{U}=\mathbb{R}^p no caso de igualdades.

Passo 3

Subgradiente do Lagrangiano e do dual — conceito e derivação didática passo a passo.
Primeiro: subgradiente de L(x,u) visto como função de u com x fixo.
  • Observação: L(x,u) é linear em u. Portanto, quando x está fixo,
\frac{\partial L(x,u)}{\partial u}=g(x)\quad\text{(componentwise)}
no caso de desigualdades, e
\frac{\partial L(x,u)}{\partial u}=h(x)
no caso de igualdades. Em termos de subgradiente (caso de não diferenciabilidade), a coleção de subgradientes de L(\cdot,u) em u contém exatamente esses vetores.
Agora: subgradiente da função dual q(u)=\inf_x L(x,u).
  • Seja \hat x\in\arg\min_x L(x,u) (ou um minimizador aproximado). Então, para qualquer v,
q(v)\le L(\hat x,v)=f(\hat x)+v^{\!T}g(\hat x).
Também q(u)=L(\hat x,u)=f(\hat x)+u^{\!T}g(\hat x). Subtraindo,
q(v)-q(u)\le (v-u)^{\!T}g(\hat x).
Isto mostra que g(\hat x) é um subgradiente de q em u; em notação,
g(\hat x)\in\partial q(u).
  • Analogamente, no caso de igualdade, se \hat x\in\arg\min_x L(x,u) então
h(\hat x)\in\partial q(u).
Resumo didático: o subgradiente do dual q no ponto u é dado avaliando as restrições no minimizador primal correspondente \hat x. Em fórmulas:
\partial q(u)=\{\,g(\hat x)\mid \hat x\in\arg\min_x L(x,u)\,\}
(no caso de desigualdades) e
\partial q(u)=\{\,h(\hat x)\mid \hat x\in\arg\min_x L(x,u)\,\}
(no caso de igualdades).

Passo 4

Regra de atualização das variáveis duais — ideia da subida por subgradiente (dual ascent).
Queremos resolver \max_{u\in\mathcal{U}} q(u). Como q é concava (em problemas convexos de primal), podemos aplicar um método de subida por subgradiente: a iteração básica é
u^{k+1}=\Pi_{\mathcal{U}}\big(u^k+\alpha_k s^k\big),
onde:
  • s^k\in\partial q(u^k) é um subgradiente do dual em u^k;
  • \alpha_k>0 é o passo (step-size);
  • \Pi_{\mathcal{U}} é a projeção ortogonal no conjunto factível de u (por exemplo, projeção na ortant não-negativo quando necessário).
Substituindo a expressão do subgradiente obtida no passo anterior, tomando \hat x^k\in\arg\min_x L(x,u^k) (ou um minimizador aproximado x^k), obtemos as fórmulas concretas:
  • Para o Problema I (desigualdades g(x)\le0):
    • subgradiente do dual: s^k=g(\hat x^k);
    • projeção em \mathcal{U}=\{u\ge0\} é a projeção componente a componente, isto é [z]_+ = \max\{0,z\} aplicado componente a componente;
    • atualização prática:
    u^{k+1}=\big[\,u^k+\alpha_k\,g(\hat x^k)\,\big]_{+},
    onde a projeção [\cdot]_+ é aplicada componente a componente.
  • Para o Problema II (igualdades h(x)=0):
    • subgradiente do dual: s^k=h(\hat x^k);
    • não há restrição de não-negatividade, logo \mathcal{U}=\mathbb{R}^p e a projeção é identidade;
    • atualização prática:
    u^{k+1}=u^k+\alpha_k\,h(\hat x^k).
Explicação das notações importantes:
  • \hat x^k é tipicamente o minimizador exato de x\mapsto L(x,u^k). Na prática de prova pode-se também usar um x^k aproximado (por exemplo obtido por uma etapa de otimização primal) — então substitui-se \hat x^k por x^k.
  • A escolha do passo \alpha_k pode ser: pequena fixa, ou sequência que satisfaça \alpha_k\to0 e \sum_k\alpha_k=\infty (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 q(u). Pela desigualdade de subgradiente, para qualquer s^k\in\partial q(u^k),
q(u^k+\alpha s^k)\ge q(u^k)+\alpha\,\|s^k\|^2 + o(\alpha)
(essa forma heurística mostra que mover na direção s^k aumenta q se \alpha for pequeno). Assim a subida por subgradiente u^{k+1}=u^k+\alpha_k s^k é a versão não-diferenciável da subida por gradiente. Se houver restrição u\ge0 projetamos de volta para o conjunto factível.
  • Como s^k=g(\hat x^k), isso dá exatamente a regra u^{k+1}=[u^k+\alpha_k g(\hat x^k)]_+ para desigualdades, e u^{k+1}=u^k+\alpha_k h(\hat x^k) para igualdades.

Passo 6

Exemplo curto e concreto (para fixar a ideia).
Considere o problema unidimensional:
\min_{x\in\mathbb{R}} \; \tfrac{1}{2}x^2 \quad\text{sujeito a}\quad x-1\le0.
  • Lagrangiano: L(x,u)=\tfrac{1}{2}x^2+u(x-1), com u\ge0.
  • Minimização em x: derivando x+\!u=0\Rightarrow x=-u. Assim \hat x(u)=-u.
  • Subgradiente do dual: g(\hat x)=\hat x-1=-u-1.
  • Atualização dual por subgradiente com passo \alpha:
u^{k+1}=\big[u^k+\alpha(-u^k-1)\big]_+ =\big[(1-\alpha)u^k-\alpha\big]_+.
Isto ilustra concretamente a fórmula e a projeção em ação.

Resposta

(a) Problema com desigualdades g(x)\le0: \displaystyle u^{k+1}=\big[\,u^k+\alpha_k\,g(\hat x^k)\,\big]_{+}.\nProblema com igualdades h(x)=0: \displaystyle u^{k+1}=u^k+\alpha_k\,h(\hat x^k).\n(b) Subgradiente de L(x,u) em u com x fixo: \displaystyle \frac{\partial L(x,u)}{\partial u}=g(x) (ou h(x) no caso de igualdades).\nSubgradiente da função dual q(u)=\inf_x L(x,u) em u: \displaystyle s\in\partial q(u)\iff s=g(\hat x) (ou s=h(\hat x) para igualdades), onde \hat x\in\arg\min_x L(x,u).

Exercícios relacionados