Lema de Farkas

Author: Igor dos Santos Montagner
Date: 25/02/2015

O lema de Farkas é parte importante da Teoria de Otimização Convexa pois apresenta uma "alternativa": dados um cone convexo e um ponto $g \in R^n$, ou $g$ pertence ao cone ou existe um hiperplano que os separa. Construindo um cone adequado podemos usar este resultado para provar as condições de otimalidade de primeira ordem KKT (que serão alvo do próximo texto).

Definição:

Sejam $B \in R^{n\times m}, C \in R^{n \times p}$ duas matrizes que contém vetores de $R^n$ em suas colunas e $y \in R^m, w \in R^p$. O conjunto $K$ definido abaixo é um cone convexo.

$$K = \{ By + Cw | y \geq 0 \}$$

Lema:

Dado um ponto $g \in R^n$ e um cone convexo $K$, então somente uma das alternativas abaixo é verdadeira:

1. $g \in K$
2. Existe $d \in R^n$ tal que:
   1. $d^T g < 0$
   2. $B^T d \geq 0$
   3. $C^T d = 0$

O interessante da prova do lema é que ela mostra como construir a direção $d$ que satisfaz estas condições.

Prova:

Primeiro iremos provar que as duas alternativas não podem ocorrer juntas.

Suponha que as duas alternativas valham, ou seja, que $g \in K$ e existe $d \in R^n$ que satisfaz as condições acima.

Primeiramente, $g = By + Cw$ para algum $y \in R^m, y \geq 0$ e $w \in R^n$. Logo, $0 > g^T d = (By + Cw)^T d = y^T B^T d + w^T C^T d$. Porém, como $C^T d = 0$, isto é igual a

$$0 > g^T d = (By + Cw)^T d = y^T B^T d \geq 0,$$

pois $B^T d \geq 0$ e $y \geq 0$. Logo, chegamos em uma contradição e as duas condições são disjuntas.

Vamos mostrar agora como construir a direção $d$ no caso em que $g \notin K$. Primeiramente, seja $\hat{s} \in K$ o elemento do cone com menor distância euclidiana até $g$. Logo, $\hat{s}$ é a solução do seguinte problema de minimização:

$$min_{s \in K} ||s - g||_2^2$$

Definimos então $d = \hat{s}-g$ e, consequentemente, $g=\hat{s}-d$.

Figura: A direção d em relação a $g$ e $s$.

Condição 1:

Como o valor mínimo da função acima encontra-se em $\hat{s}$, sabemos que a função $|| t \hat{s} - g||_2^2$ possui mínimo em $t=1$, pois $t \hat{s} \in K, \forall t \geq 0$. Logo,

$$\frac{||t\hat{s} - g||_2^2}{dt} |_{t=1} = 0 \\ \frac{t^2 \hat{s}^T \hat{s} - 2t\hat{s}^Tg + ||g||_2^2}{dt} |_{t=1} = 0 \\ 2t\hat{s}^T \hat{s} - 2\hat{s}^Tg |_{t=1} = 0 \\ 2\hat{s}^T(t\hat{s} - g)|_{t=1} = 0 \\ \hat{s}^T(\hat{s} - g) = 0$$

Logo,

$$d^Tg = d^T(\hat{s}-d) = d^T\hat{s} - d^T d = \\ \hat{s}^T(s - d) - ||d||_2^2 = -||d||_2^2 < 0$$

Condições 2 e 3:

Para mostrar que $d$ satisfaz as condições 2 e 3 vamos primeiramente analisar o que acontece quando consideramos, em vez de $\hat{s}$, $\hat{s} + \theta(\hat{s} - s), s \in K$.

$$||\hat{s} + \theta(\hat{s} - s) - g ||_2^2 \geq ||\hat{s} - g||_2^2 \\ ||\hat{s} - g||_2^2 +2\theta(\hat{s} - g)^T(\hat{s} - s) + \theta^2||\hat{s} - s||_2^2 \geq ||\hat{s} - g||_2^2 \\ 2\theta(\hat{s} - g)^T(\hat{s} - s) + \theta^2||\hat{s} - s||_2^2 \geq 0 \\ 2(\hat{s} - g)^T(\hat{s} - s) + \theta||\hat{s} - s||_2^2 \geq 0 \\ \theta \rightarrow 0 \\ 2(\hat{s} - g)^T(\hat{s} - s) \geq 0 \\ 2(\hat{s} - s)^T(\hat{s} - g) = \hat{s}^T(\hat{s} - g) - s^T(\hat{s} - g) \geq 0 \\ s^T(\hat{s} - g) = d^Ts \geq 0 \forall s \in K \\ $$

Logo, $d^Ts = d^T(By + Cw) \geq 0, y \geq 0$. Isto vale para todos os $s \in K$ e, em especial para os casos abaixo:

1. $y = 0$, $d^TCw \geq 0 \rightarrow d^TC = C^T d = 0$
2. $w = 0$, $d^TBy \geq 0 \rightarrow B^Td \geq 0$, pois $y \geq 0$.

Portanto, a direção $d = \hat{s} - g$ satisfaz as propriedades do lema se $g \notin K$ e tudo está provado :)

---