Otimização/KKT

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.$

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 polar 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 módulo 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=\text{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 polar, 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 $\epsilon > 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 $\epsilon >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)$.

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

1. $\nabla f(x)^{\top}d \leq 0,\ \forall d\in D(x)$.
2. $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+td)<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+td)-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 $\epsilon >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)$.

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 $\lambda_i$ com $i=1, \dots, m$ e $\delta_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 $\alpha_{i}-t\lambda_i$ ou $\beta_{j}-t\delta_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\Gamma^{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\Omega^k$ obtém-se $z=C\Omega$, 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)$.

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.

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$.

Propriedades do cone tangente

O cone tangente definido anteriormente tem as seguintes propriedades:

1. $T(a, C)$ é fechado e $0 \in T(a, C)$
2. Se $C \subset D$ então $T(a, C) \subset T(a, D)$
3. 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:

1. $T(a, C) \subset L(a, C)$.
2. 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 módulo 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)$.

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:

1. $-\nabla f(a) = \sum_{i=1}^p u_i\nabla g_i(a) + \sum_{j=1}^q v_j\nabla h_j(a)$
2. $u_i \ge 0,\ \forall i=1, \dots, p$
3. $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 polar 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 $\delta_i$ com $i\in I(a)$ e $\lambda_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}$ Como $g_i(a)=0,\ \forall i\in I(a)$ obtem-se $u_ig_i(a)=0\ \forall i=1, \dots, p$. Com isso fica provado o Teorema de KKT.