Otimização/KKT

Origem: Wikilivros, livros abertos por um mundo aberto.

Neste capítulo o objetivo é desenvolver algumas ideias e provar o teorema de Karush–Kuhn–Tucker (também chamado simplesmente de teorema KKT) que será utilizado no capítulo seguinte para explorar os métodos duais. O teorema KKT é bem útil para resolver problemas do tipo

$(P)\left\{\begin{matrix} \min f(x)\\ g_i(x) \le 0; i = 1, \ldots, p\\ h_j(x) = 0; j = 1, \ldots, q \end{matrix}\right.$

Índice

1 Cones
2 Caracterização das direções de descida
3 O cone viável linearizado
4 O cone tangente
- 4.1 Exemplo de cone tangente
- 4.2 Propriedades do cone tangente
5 Teorema KKT

[editar] Cones

Definição

Um conjunto $C \in \mathbb{R}^n$ é um cone quando

$d \in C \Rightarrow td \in C, \forall t \in \mathbb R_{+}$

Exemplo de um cone no $\mathbb{R}^2$ .

Em outras palavras, a propriedade que caracteriza um cone é que este tipo de conjunto contém todos os múltiplos não nulos de qualquer de seus elementos.

Definição

Dado um subconjunto $C \subset \mathbb{R}^n$ , o cone dual de $C$ é o conjunto definido por

$C^{*}=\{ p\in \mathbb{R}^n : p^{\top}x\leq 0,\ \forall x \in C \}$ .

Observações:

$C *$ é um cone: Se $d \in C^{*}$ tem-se que $d^{\top}x\leq 0,\ \forall x\in C$ . Logo, para qualquer $t\in \mathbb R_+$ , vale $(td)^{\top}x=t d^{\top}x\leq 0,\ \forall x\in C$ . Disto segue que $td\in C^{*}$ , mostrando que $C *$ é um cone.
Sempre se tem que $C\subseteq (C^{*})^{*}$ (Verifique).

Na segunda propriedade a igualdade pode não ocorrer (exemplo?). Para o objetivo deste texto, o ideal seria que a igualdade valesse. Mas será que isso ocorre para algum conjunto? A resposta é sim e, conforme o próximo lema, basta que $C$ seja um cone convexo fechado.

Este livro tem a seguinte tarefa pendente: Incluir a definição de projeção antes deste ponto, pois ela será usada durante a demonstração

Lema (Farkas)

Se $C\subset \mathbb{R}^n$ um cone convexo fechado, então $C = (C *) *$ .

Demonstração

Seja $y\in (C^{*})^{*}$ e

w = proj C (y)

. Sabendo que a projeção de um ponto sobre um conjunto convexo é única, será mostrado que

w = y

e então ficará provada a inclusão $C \supset (C^{*})^{*}$ . Disto seguirá a igualdade entre os dois conjuntos, já que

C

é sempre um subconjunto de

(C *) *

.

Pelo teorema da projeção (ver Izmailov & Solodov (2007)), tem-se que $(y-w)^{\top}(x-w)\leq 0,\ \forall x\in C$ . Usando o fato de que $C$ é cone, segue que $0\in C$ e $2w\in C$ e substituindo isto na equação acima obtem-se

$(y-w)^{\top}(-w)\leq 0$ e $(y-w)^{\top}w\leq 0$ .

Dessas desigualdades, conclui-se que $(y-w)^{\top}w=0$ .

De $(y-w)^{\top}(x-w)=(y-w)^{\top}x -(y-w)^{\top}w\leq 0$ , tem-se que $(y-w)^{\top}x\leq 0,\ \forall x\in C$ .

Usando a definição de cone dual, isso implica que $y-w\in C^{*}$ .

Uma vez que $y\in (C^{*})^{*}$ , significa que $(y-w)^{\top}y\leq 0$ .

Desses fatos acima se conclui que

$\|y-w\|^2=(y-w)^{\top}(y-w)=(y-w)^{\top}y-(y-w)^{\top}w\leq 0$

Isso mostra que $y = w$ .

Definição

Dado $x\in C$ , se diz que $d\in \mathbb{R}^n$ é uma direção viável em $x$ , com respeito a $C$ , quando existe $ε > 0$ tal que

$x+td \in C,\ \forall t\in [0, \epsilon]$ .

O conjunto de todas as direções viáveis em

x

, com respeito ao conjunto

C

, será denotado por

V C (x)

.

Esse conjunto $V C (x)$ é o cone das direções viáveis em $x$ , com respeito a $C$ .

Definição

Uma direção $d\in \mathbb{R}^n$ é uma direção de descida da função $f$ em $x$ , se existe $ε > 0$ tal que

$f(x+td) < f(x),\ \forall t\in (0, \epsilon]$ .

O conjunto das direções de descida será denotado por

D (x)

.

[editar] Caracterização das direções de descida

Lema

Seja $f: \mathbb{R}^n \rightarrow \mathbb{R}$ uma função diferenciável em $x\in \mathbb{R}^n$ . Então

$\nabla f(x)^{\top}d \leq 0,\ \forall d\in D(x)$ .
$d\in \mathbb{R}^n$ satisfaz $\nabla f(x)^{\top}d < 0 \ \Rightarrow d\in D(x)$ .

Demonstração

1) Seja $d\in D(x)$ . Então, $\forall t \in (0, \epsilon]$ tem-se

f (x + t d) < f (x)

.

Usando a série de Taylor, tem-se

$f(x)+t\nabla f(x)^{\top}d + o(t)< f(x)$

Sendo $t\neq 0$ ,

$\nabla f(x)^{\top}d + \frac{o(t)}{t}< 0$ .

Passando o limite com $t\rightarrow 0$ tem-se que $\nabla f(x)^{\top}d\leq 0$ .

2) Novamente aplicando Taylor em $f (x + t d) - f (x)$ tem-se

$f(x+td)-f(x)=t\nabla f(x)^{\top}d + o(t)$ .

Como $t\neq 0$ , tem-se

$f(x+td)-f(x)=t(\nabla f(x)^{\top}d +\frac{o(t)}{t} )$ .

Pela hipótese $\nabla f(x)^{\top}d<0$ , com isto

$\lim_{t\rightarrow 0}{(\nabla f(x)^{\top}d +\frac{o(t)}{t})}=\nabla f(x)^{\top}d<0$ .

Pelo teorema da conservação do sinal, existe $ε > 0$ tal que $\nabla f(x)^{\top}d +\frac{o(t)}{t}<0,\ \forall t\in (0, \epsilon]$ .

Portanto,

$t(\nabla f(x)^{\top}d +\frac{o(t)}{t})<0$

$f(x+td)<f(x)\ \forall t\in (0, \epsilon]$ .

Conclui-se então que $d\in D(x)$ .

[editar] O cone viável linearizado

Definição

Dado $x \in C = \{ x \in \mathbb{R}^n; g_i(x) \le 0 \text{ e } h_j(x) = 0\}$ , a desigualdade $g_i(x) \le 0$ é uma restrição ativa em $x$ se $g i (x) = 0$ .

Observações

O conjunto formado pelos índices das restrições de desigualdade ativas é denotado por $I (x)$ . Assim,

I (x) = {i : g i (x) = 0}

Definição

Dado um ponto $x\in C$ e o conjunto $I (x)$ , se define o cone viável linearizado de $C$ a partir de $x$ como

$L(x, C)=\{d\in \mathbb{R}^n: \nabla g_{j}(x)^{\top}d\leq 0,\ \forall j\in I(x) \ \text{e} \ \nabla h_{i}(x)^{\top}d=0,\ \forall i=1, \dots, q\}$ .

$L (x, C)$ é um cone não-vazio convexo e fechado pois, $0\in L(x, C)$ . E se $y, w \in L(x, C)$ , tem-se

$\nabla h_{i}(x)^{\top}(\alpha y+(1-\alpha)w)= \alpha \nabla h_{i}(x)^{\top}y +(1-\alpha)\nabla h_{i}(x)^{\top}w=\alpha 0 +(1-\alpha)0=0$ e

$\nabla g_{j}(x)^{\top}(\alpha y+(1-\alpha)w)= \alpha \nabla g_{j}(x)^{\top}y +(1-\alpha)\nabla g_{j}(x)^{\top}w\leq \alpha 0 +(1-\alpha)0\leq 0$ .

Portanto $\alpha y+(1-\alpha)w \in L(x, C)$ mostrando que $L (x, C)$ é convexo.

Para mostrar que $L (x, C)$ é fechado, pode-se pegar uma sequência convergente $(d^{k})\in L(x, C)$ e mostrar que o ponto de acumulação dela esta em $L (x, C)$ .

Tem-se que $\nabla h_{i}(x)^{\top}d^{k}=0 \ \text{e}\ \nabla g_{j}(x)^{\top}d^{k}\leq 0,\ \forall k\in \mathbb{N}$ .

Passando o limite com $k \rightarrow \infty$ , obtem-se

$0=\lim_{k \rightarrow \infty}{\nabla h_{i}(x)^{\top}d^{k}}=\nabla h_{i}(x)^{\top}\lim_{k \rightarrow \infty}{d^{k}}=\nabla h_{i}(x)^{\top}d$ e

$0\ge \lim_{k \rightarrow \infty}{\nabla g_{j}(x)^{\top}d^{k}}= \nabla g_{j}(x)^{\top}\lim_{k \rightarrow \infty}{d^{k}}=\nabla g_{j}(x)^{\top}d$ .

Isso mostra que $L (x, C)$ é fechado.

Lema (Caratheodory)

Sejam $y_1, \dots, y_m, w_1, \dots, w_p \in \mathbb{R}^n$ . Seja $x\in \mathbb{R}^n$ com $x\neq 0$ e $\alpha_1, \dots, \alpha_m, \beta_1, \dots, \beta_p$ escalares tais que $\beta_j\ge 0\ \forall j=1, \dots, p$ e

$x=\sum_{i=1}^m \alpha_{i}y_{i}+\sum_{j=1}^p \beta_{j}w_j$ .

Então existem subconjuntos $I\subset \{1, \dots, m\}\text{, } J\subset\{1, \dots, p\}$ e escalares $\alpha_{i}^{*}$ com $i\in I$ e $\beta_{j}^{*}\ \forall j\in J$ tais que

$x=\sum_{i\in I} \alpha_{i}^{*}y_{i}+\sum_{j\in J} \beta_{j}^{*}w_j$ e os vetores $\{y_i\}_{i\in I}\cup \{w_j\}_{j\in J}$ são linearmente independentes.

Demonstração

Sem perda de generalidade, suponha que $\alpha_{i}\neq 0\ \forall i=1, \dots, m$ e $\beta_j>0,\ \forall j=1, \dots, p$ . Considere que $\{y_1, \dots, y_m, w_1, \dots, w_p\}$ sejam linearmente dependentes.

Portanto existem escalares $λ i$ com $i=1, \dots, m$ e $δ j$ com $j=1, \dots, p$ não todos nulos tais que

$0=\sum_{i=1}^m \lambda_{i}y_{i}+\sum_{j=1}^p \delta_{j}w_j$

Multiplicando a igualdade acima por $t$ e subtraindo de

$x=\sum_{i=1}^m \alpha_{i}y_{i}+\sum_{j=1}^p \beta_{j}w_j$ tem-se

$x=\sum_{i=1}^m (\alpha_{i}-t\lambda_i)y_{i}+\sum_{j=1}^p (\beta_{j}-t\delta_j)w_j$

Para $t = 0$ certamente nenhum dos coeficientes acima se anula.

Seja $\bar{t}$ o $t$ de menor módulo que anula pelo menos um dos coeficientes $α i - t λ i$ ou $β j - t δ j$ . Então

$x=\sum_{i=1}^m (\alpha_{i}-\bar{t}\lambda_i)y_{i}+\sum_{j=1}^p (\beta_{j}-\bar{t}\delta_j)w_j$

Assim, se escreve $x$ como combinação linear de no máximo $m + p - 1$ vetores já que $\beta_{j}-\bar{t}\delta_j\ge 0$ .

Repetindo esse processo obtem-se uma combinação linearmente independente.

Definição

Dado um ponto $x\in C$ , se define o cone $G (x)$ por

$G(x)=\{\sum_{i=1}^q \alpha_{i}\nabla h_{i}(x) +\sum_{j\in I(x)} \beta_{j}\nabla g_{j}(x):\beta_{j}\ge 0,\ \forall j\in I(x)\}$ .

A seguir, serão mostradas algumas propriedades deste cone.

Lema

Para qualquer $x\in C$ , $G (x)$ é um cone convexo e fechado.

Demonstração

Primeiro será mostrado que

G (x)

é de fato um cone. Seja $d\in G(x)$ e $t\ge 0$ . Então tem-se

$td=\sum_{i=1}^q t\alpha_{i}\nabla h_{i}(x) +\sum_{j\in I(x)} t\beta_{j}\nabla g_{j}(x)$ .

Como $t\beta_{j}\ge 0$ tem-se que $td\in G(x)$ .

Agora, será provado que $G (x)$ é convexo. Para isso seja $y, w\in G(x)$ , isto é,

$y=\sum_{i=1}^q \alpha_{i}\nabla h_{i}(x) +\sum_{j\in I(x)} \beta_{j}\nabla g_{j}(x)$ e

$w=\sum_{i=1}^q \lambda_{i}\nabla h_{i}(x) +\sum_{j\in I(x)} \delta_{j}\nabla g_{j}(x)$ e $t\in [0, 1]$ .

Logo tem-se,

$ty+(1-t)w=\sum_{i=1}^q (t\alpha_{i}+(1-t)\lambda_{i})\nabla h_{i}(x) +\sum_{j\in I(x)} (t\beta_{j}+(1-t)\delta_{j})\nabla g_{j}(x)$ .

Como $t\beta_{j}+(1-t)\delta_{j}\ge 0$ visto que $\beta_{j}\ge 0$ e $\delta_{j}\ge 0$ . Com isso concluímos que $ty+(1-t)w\in G(x)$ mostrando que $G (x)$ é convexo.

Para mostrar que $G (x)$ é fechado, toma-se uma sequência convergente em $G (x)$ e se mostra que o ponto de acumulação dela pertence a $G (x)$ .

Para isso seja $(z^k)\subset G(x)$ com $z^k\rightarrow z \in \mathbb{R}^n$ . Será mostrado que $z\in G(x)$ .

Escrevendo $G (x)$ em forma matricial tem-se $G(x)=\{A\Delta+B\Omega:\Omega\ge 0 \}$ .

Pelo Lema de Caratheodory podemos assumir que $C=(A\ B)$ tem colunas linearmente independentes, e portanto $C^{\top}C$ é não singular.

Uma vez que $(z^k)\subset G(x)$ , existem $\Gamma^{k}=(\Delta^{k}\ \Omega^{k})^t$ com $\Omega^{k}\ge 0$ tais que $z k = C Γ k$ .

Uma vez que $C^{\top}C$ é não singular, $\Gamma^{k}=(C^{\top}C)^{-1}C^{\top}z^k$ .

Passando o limite obtem-se,

$(\Delta \ \Omega)^t=\Gamma=\lim_{k\rightarrow \infty}{\Gamma^{k}}=(C^{\top}C)^{-1}C^{\top}z$ com $\Omega\ge 0$ .

Isso mostra que $C\Omega \in G(x)$ .

Agora passando o limite em $z k = C Ω k$ obtém-se $z = C Ω$ , mostrando que $z\in G(x)$ .

Lema

Para qualquer $x\in C$ , $G (x) = L (x, C) *$ .

Demonstração

Como

L (x, C)

e

G (x)

são convexos e fechados, tem-se que

L (x, C) = (L (x, C) *) *

e

G (x) = (G (x) *) *

. Será mostrado então que

L (x, C) = G (x) *

.

Seja $d\in L(x, C)$ . Assim, dado $y\in G(x)$ tem-se

$d^{\top}y=d^{\top}(\sum_{i=1}^q \alpha_{i}\nabla h_{i}(x) +\sum_{j\in I(x)} \beta_{j}\nabla g_{j}(x))$

$d^{\top}y=\sum_{i=1}^q \alpha_{i}d^{\top}\nabla h_{i}(x) +\sum_{j\in I(x)} \beta_{j}d^{\top}\nabla g_{j}(x)$

Mas $\beta\ge 0$ e $d^{\top}\nabla h_i(x)=0$ e $d^{\top}\nabla g_j(x)\leq 0$ .

Conclui-se então que $d^{\top}y\leq 0$ . Como $y$ é arbitrário, $d\in G(x)^{*}$ .

Agora a volta, seja $d\in G(x)^{*}$ , isto é, $d^{\top}y\leq 0\ \forall y\in G(x)$ .

Em particular, uma vez que $\nabla h_i(x)$ e $-\nabla h_i(x)\in G(x)\ \forall i=1, \dots, q$ , tem-se que $d^{\top}\nabla h_i(x)=0$ .

Além disso, uma vez que $\nabla g_j(x)\in G(x)\ \forall j\in I(x)$ , tem-se que $d^{\top}\nabla g_j(x)\leq 0$ .

Logo $d\in L(x, C)$ .

[editar] O cone tangente

Definição

Um vetor $d\in \mathbb{R}^n$ é chamado direção tangente em $C$ a partir de $x\in C$ quando ou $d = 0$ ou $\exist (x^k)\subset C$ tal que

$x^k\rightarrow x$ e $\frac{x^k-x}{\|x^k-x\|}\rightarrow \frac{d}{\|d\|}$ .

Observações

O conjunto de todas as direções tangentes no ponto $x \in C$ , é denominado cone tangente, e denotado por $T (x, C)$ .
Se $a \in C$ , então $T (a, C)$ também pode ser descrito como

$T(a, C) = \left\{d \in; \exists \{d_k\} \text{ com } d_k \to d;\quad \exists \{t_k\} \text{ com } t_k \to 0 \text{ tais que } x = a + t_k d_k \in C, \, \forall k \right\}$

Exercício

Verifique que $T (a, C)$ é de fato um cone (e portanto merece ser chamado de "cone tangente").

Resolução
A resolução deste exercício é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

[editar] Exemplo de cone tangente

Determinar o cone tangente ao ponto $a = (0,0)$ do quadrado unitário com vértices $(0,0)$ , $(0,1)$ , $( - 1,1)$ e $( - 1,0)$ .

Resolução

Cone tangente a um quadrado unitário com vértice na origem.

Dado qualquer ponto $d = (d 0, d 1)$ do 2º quadrante (formado pelos pontos $(x, y)$ tais que $x < 0$ e $y > 0$ ), pode-se definir:

$t_k = \left(\frac{1}{2}\right)^k$

d k = d

Com essas escolhas, tem-se:

$t_k \to 0$

~~$d_k \to d$~~

Logo, $a + t_k d_k = a + \left(\frac{1}{2}\right)^k d = (0, 0) + \left(\frac{d_0}{2^k}, \frac{d_1}{2^k}\right) = \left(\frac{d_0}{2^k}, \frac{d_1}{2^k}\right) \in C$ .

[editar] Propriedades do cone tangente

A Wikipédia tem mais sobre este assunto:

Cone tangente

O cone tangente definido anteriormente tem as seguintes propriedades:

$T (a, C)$ é fechado e $0 \in T(a, C)$
Se $C \subset D$ então $T(a, C) \subset T(a, D)$
Se $V$ é uma vizinhança de $a$ , então $T(a, C) = T(a, V \cap C)$

Observação

A terceira propriedade indica que o cone tangente só depende do que ocorre bem perto de $a$ , no conjunto $C$ .

Lema

Para qualquer $x\in C$ , $T (x, C)$ é fechado.

Demonstração

Seja $(d^k)\subset T(x, C)$ com $d^k\rightarrow d\in \mathbb{R}^n$ . Será mostrado que $d\in T(x, C)$ .

Caso $d = 0$ , $d\in T(x, C)$ . Então, suponha-se que $d\neq 0$ .

Neste caso, sem perda de generalidade pode-se considerar que $d^k\neq 0,\ \forall k\in \mathbb{N}$ , pois $d^k\rightarrow d$ .

Fixando $k\in \mathbb{N}$ tem-se que $d^k\in T(x, C)$ . Portanto, existe $(x^{k, j})_{j\in \mathbb{N}}\subset C$ tal que $x^{k, j}\rightarrow x$ e $\frac{x^{k, j}-x}{\|x^{k, j}-x\|}\rightarrow \frac{d^k}{\|d^k\|}$ quando $j\rightarrow \infty$ .

Assim para $\epsilon=\frac{1}{k}$ existe $j_k\in \mathbb{N}$ tal que para $j\ge j_k$ , tal que $\|x^{k, j}-x\|<\frac{1}{k}$ e $\bigg|\frac{x^{k, j}-x}{\|x^{k, j}-x\|}- \frac{d^k}{\|d^k\|}\bigg|<\frac{1}{k}$ .

Em particular, tomando $j = j k$ tem-se

$\|x^{k, j_k}-x\|<\frac{1}{k}$ e $\bigg|\frac{x^{k, j_k}-x}{\|x^{k, j_k}-x\|}- \frac{d^k}{\|d^k\|}\bigg|<\frac{1}{k}$ .

Tomando o limite quando $k\rightarrow \infty$ , obtem-se que $x^k\rightarrow x$ e

$\bigg|\frac{x^{k, j_k}-x}{\|x^{k, j_k}-x\|}- \frac{d}{\|d\|}\bigg|\leq \bigg|\frac{x^{k, j_k}-x}{\|x^{k, j_k}-x\|}- \frac{d^k}{\|d^k\|}\bigg|+\bigg|\frac{d^k}{\|d^k\|}- \frac{d}{\|d\|}\bigg|\rightarrow 0$ .

Logo $\frac{x^k-x}{\|x^k-x\|}\rightarrow \frac{d}{\|d\|}$ .

Isso mostra que $d\in T(x, C)$ .

Exercício

Verificar que:

$T(a, C) \subset L(a, C)$ .
Se $C = \{(x, y) \in \mathbb{R}^2; x^2 + y \le 0;\quad x^2 - y \le 0\}$ e $a = (0,0)$ , então $T(a, C) \not = L(a, C)$ .

Demonstração

1) Seja $d\in T(a, C)$ , $d\neq 0$ . Logo $\exist (x^k)\subset C$ tal que $x^k\neq a$ , $x^k\rightarrow a$ e $\frac{x^k-a}{\|x^k-a\|}\rightarrow \frac{d}{\|d\|}$ .

Usando Taylor em torno de $a$ tem-se

$0=h_j(x^k)=h_j(a)+\nabla h_j(x)^{\top}(x^k-a)+o(\|x^k-a\|)$ .

Já que $x^k\neq a$ , então $\|x^k-a\|\neq 0$ logo pode-se dividir e obtem-se

$\nabla h_j(a)^{\top}\frac{(x^k-a)}{\|x^k-a\|}+\frac{o(\|x^k-a\|)}{\|x^k-a\|}=0$ .

Passando o limite quando $k\rightarrow \infty$ , tem-se $\nabla h_j(a)^{\top}\frac{d}{\|d\|}=0$ .

Novamente usando Taylor em torno de $a$ para $i\in I(x)$ tem-se

$g_i(a)+\nabla g_i(a)^{\top}(x^k-a)+o(\|x^k-a\|)\leq 0$

$\nabla g_i(a)^{\top}\frac{(x^k-a)}{\|x^k-a\|}+\frac{o(\|x^k-a\|)}{\|x^k-a\|}\leq 0$

Passando o limite quando $k\rightarrow \infty$ tem-se $\nabla g_i(a)^{\top}\frac{d}{\|d\|}=\leq 0$ .

Donde se conclui que $d\in L(a, C)$ .

2)

Este livro tem a seguinte tarefa pendente: Colocar figura

Lema

Se $a\in C$ é um mínimo local do problema (P), então $\nabla f(a)^{\top}d\ge 0,\ \forall d\in T(a, C)$ .

Demonstração

Por Taylor tem-se

$0\ge f(x^k)-f(a)=\nabla f(a)^{\top}(x^k-a)+o(\|x^k-a\|)$

$0\ge \nabla f(a)^{\top}\frac{(x^k-a)}{\|x^k-a\|}+\frac{o(\|x^k-a\|)}{\|x^k-a\|}$

Passando o limite quando $k\rightarrow \infty$ obtem-se

$0\ge \nabla f(a)^{\top}\frac{d}{\|d\|}$

Donde $\nabla f(a)^{\top}d\leq 0\ \forall d\in T(a, C)$ .

[editar] Teorema KKT

Teorema (Condições de KKT)

Seja $C = \{ x \in \mathbb{R}^n; g_i(x) \le 0 \text{ e } h_j(x) = 0\}$ e considere $a\in C$ um minimizador local do problema

$(P)\left\{\begin{matrix} \min f(x)\\ x \in C \end{matrix}\right.$

Se

T (a, C) * = L (a, C) *

, então existem $u \in \mathbb{R}^p$ e $v \in \mathbb{R}^q$ tais que:

$-\nabla f(a) = \sum_{i=1}^p u_i\nabla g_i(a) + \sum_{j=1}^q v_j\nabla h_j(a)$
$u_i \ge 0,\ \forall i=1, \dots, p$
$u_ig_i(a)=0,\ \forall i=1, \dots, p$ .

Demonstração

Considere

a

um minimizador local do problema (P). Então $(-\nabla f(a))^{\top}d\leq 0,\ \forall d\in T(a, C)$ . Pela definição de cone dual isso significa que $-\nabla f(a)\in T(a, C)^{*}$ .

Pela hipotése tem-se $-\nabla f(a)\in L(a, C)^{*}$ . Como $L (a, C) = G (a) *$ obtem-se que $-\nabla f(a)\in (G(a)^{*})^{*}$ .

Como foi visto acima $G (a)$ é um cone convexo e fechado. Portanto usando o Lema de Farkas obtem-se que $-\nabla f(a)\in G(a)$ .

Pela definição de $G (a)$ , existem escalares $δ i$ com $i\in I(a)$ e $λ j$ com $j=1, \dots, q$ tais que

$-\nabla f(a) = \sum_{i\in I(a)} \delta_i\nabla g_i(a) + \sum_{j=1}^q \lambda_j\nabla h_j(a)$ com $\delta_i\ge 0\ \forall i\in I(a)$ .

Como $\text{card}I(a)\leq p$ , define-se $v_j = \lambda_j,\ \forall j=1, \dots, q$ e $u_i=\begin{cases} \delta_i & \forall i\in I(a) \\ 0 & \forall i\notin I(a) \end{cases}$