Lema de Farkas - Farkas' lemma

O lema de Farkas é um teorema de solvabilidade para um sistema finito de desigualdades lineares em matemática. Foi originalmente provado pelo matemático húngaro Gyula Farkas . O lema de Farkas é o resultado chave que sustenta a dualidade da programação linear e tem desempenhado um papel central no desenvolvimento da otimização matemática (alternativamente, programação matemática ). É usado, entre outras coisas, na prova do teorema de Karush – Kuhn – Tucker em programação não linear . Notavelmente, na área dos fundamentos da teoria quântica, o lema também fundamenta o conjunto completo de desigualdades de Bell na forma de condições necessárias e suficientes para a existência de uma teoria de variável oculta local , dados dados de qualquer conjunto específico de medições.

As generalizações do lema de Farkas são sobre o teorema da solubilidade para desigualdades convexas, ou seja, sistema infinito de desigualdades lineares. O lema de Farkas pertence a uma classe de declarações chamadas "teoremas da alternativa": um teorema que afirma que exatamente um dos dois sistemas tem uma solução.

Declaração do lema

Existem várias formulações ligeiramente diferentes (mas equivalentes) do lema na literatura. O dado aqui é devido a Gale, Kuhn e Tucker (1951).

Lema de Farkas - Vamos e . Então, exatamente uma das duas afirmações a seguir é verdadeira: ${\ displaystyle \ mathbf {A} \ in \ mathbb {R} ^ {m \ vezes n}}$ ${\ displaystyle \ mathbf {b} \ in \ mathbb {R} ^ {m}}$

Existe um tal que e . ${\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {Ax} = \ mathbf {b}}$ ${\ displaystyle \ mathbf {x} \ geq 0}$
Existe tal que e . ${\ displaystyle \ mathbf {y} \ in \ mathbb {R} ^ {m}}$ ${\ displaystyle \ mathbf {A} ^ {\ mathsf {T}} \ mathbf {y} \ geq 0}$ ${\ displaystyle \ mathbf {b} ^ {\ mathsf {T}} \ mathbf {y} <0}$

Aqui, a notação significa que todos os componentes do vetor são não negativos. ${\ displaystyle \ mathbf {x} \ geq 0}$ ${\ displaystyle \ mathbf {x}}$

Exemplo

Seja m , n = 2 , e . O lema diz que exatamente uma das duas afirmações a seguir deve ser verdadeira (dependendo de b ₁ e b ₂ ): ${\ displaystyle \ mathbf {A} = {\ begin {bmatrix} 6 e 4 \\ 3 e 0 \ end {bmatrix}}}$ ${\ displaystyle \ mathbf {b} = {\ begin {bmatrix} b_ {1} \\ b_ {2} \ end {bmatrix}}}$

Existem x ₁ ≥ 0, x ₂ ≥ 0 tal que 6 x ₁ + 4 x ₂ = b ₁ e 3 x ₁ = b ₂ , ou
Existem y ₁ , y ₂ tais que 6 y ₁ + 3 y ₂ ≥ 0, 4 y ₁ ≥ 0 e b ₁ y ₁ + b ₂ y ₂ <0.

Aqui está uma prova do lema neste caso especial:

Se b ₂ ≥ 0 e b ₁ - 2 b ₂ ≥ 0, em seguida, uma opção é verdade, uma vez que a solução das equações lineares é X ₁ = b ₂ /3 e x ₂ = ( b ₁ -2 b ₂ ) / 4 . A opção 2 é falsa, uma vez que b ₁ y ₁ + b ₂ y ₂ ≥ b ₂ (2 y ₁ + y ₂ ) = b ₂ (6 y ₁ + 3 y ₂ ) / 3, então se o lado direito for positivo, o lado esquerdo também deve ser positivo.
Caso contrário, a opção 1 é falsa, uma vez que a solução única das equações lineares não é fracamente positiva. Mas, neste caso, a opção 2 é verdadeira:
- Se b ₂ <0, então podemos tomar, por exemplo, y ₁ = 0 ey ₂ = 1.
- Se b ₁ - 2 b ₂ <0, então, para algum número B > 0, b ₁ = 2 b ₂ - B, então: b ₁ y ₁ + b ₂ y ₂ = 2 b ₂ y ₁ + b ₂ y ₂ - B y ₁ = b ₂ (6 y ₁ + 3 y ₂ ) / 3 - B y ₁ . Assim, podemos tomar, por exemplo, y ₁ = 1, y ₂ = −2.

Interpretação geométrica

Considere o cone convexo fechado medido pelas colunas de ; isso é, ${\ displaystyle C (\ mathbf {A})}$ ${\ displaystyle \ mathbf {A}}$

{\ displaystyle C (\ mathbf {A}) = \ {\ mathbf {A} \ mathbf {x} \ mid \ mathbf {x} \ geq 0 \}.}

Observe que é o conjunto de vetores para os quais a primeira asserção no enunciado do lema de Farkas é válida. Por outro lado, o vetor na segunda asserção é ortogonal a um hiperplano que separa e . O lema segue da observação que pertence a se e somente se não há hiperplano que o separa de . ${\ displaystyle C (\ mathbf {A})}$ ${\ displaystyle \ mathbf {b}}$ ${\ displaystyle \ mathbf {y}}$ ${\ displaystyle \ mathbf {b}}$ ${\ displaystyle C (\ mathbf {A})}$ ${\ displaystyle \ mathbf {b}}$ ${\ displaystyle C (\ mathbf {A})}$ ${\ displaystyle C (\ mathbf {A})}$

Mais precisamente, vamos denotar as colunas de . Em termos desses vetores, o lema de Farkas afirma que exatamente uma das duas afirmações a seguir é verdadeira: ${\ displaystyle \ mathbf {a} _ {1}, \ dots, \ mathbf {a} _ {n} \ in \ mathbb {R} ^ {m}}$ ${\ displaystyle \ mathbf {A}}$

Existem coeficientes não negativos de tal forma . ${\ displaystyle x_ {1}, \ dots, x_ {n} \ in \ mathbb {R}}$ ${\ displaystyle \ mathbf {b} = x_ {1} \ mathbf {a} _ {1} + \ dots + x_ {n} \ mathbf {a} _ {n}}$
Existe um vetor tal que para , e . ${\ displaystyle \ mathbf {y} \ in \ mathbb {R} ^ {m}}$ ${\ displaystyle \ mathbf {a} _ {i} ^ {\ mathsf {T}} \ mathbf {y} \ geq 0}$ ${\ displaystyle i = 1, \ dots, n}$ ${\ displaystyle \ mathbf {b} ^ {\ mathsf {T}} \ mathbf {y} <0}$

As somas com coeficientes não negativos formam o cone medido pelas colunas de . Portanto, a primeira declaração diz que pertence a . ${\ displaystyle x_ {1} \ mathbf {a} _ {1} + \ dots + x_ {n} \ mathbf {a} _ {n}}$ ${\ displaystyle x_ {1}, \ dots, x_ {n}}$ ${\ displaystyle \ mathbf {A}}$ ${\ displaystyle \ mathbf {b}}$ ${\ displaystyle C (\ mathbf {A})}$

A segunda afirmação diz que existe um vetor tal que o ângulo de com os vetores é no máximo 90 °, enquanto o ângulo de com o vetor é mais de 90 °. O hiperplano normal a este vetor possui os vetores de um lado e o vetor do outro lado. Portanto, esse hiperplano separa o cone medido por do vetor . ${\ displaystyle \ mathbf {y}}$ ${\ displaystyle \ mathbf {y}}$ ${\ displaystyle \ mathbf {a} _ {i}}$ ${\ displaystyle \ mathbf {y}}$ ${\ displaystyle \ mathbf {b}}$ ${\ displaystyle \ mathbf {a} _ {i}}$ ${\ displaystyle \ mathbf {b}}$ ${\ displaystyle \ mathbf {a} _ {1}, \ dots, \ mathbf {a} _ {n}}$ ${\ displaystyle \ mathbf {b}}$

Por exemplo, deixar que n , m = 2, a ₁ = (1, 0) ^t , e um ₂ = (1, 1) ^T . O cone convexo medido por um ₁ e um ₂ pode ser visto como uma fatia em forma de cunha do primeiro quadrante no plano xy . Agora, suponha b = (0, 1). Certamente, b não está no cone convexo a ₁x ₁ + a ₂x ₂ . Portanto, deve haver um hiperplano de separação. Vamos y = (, 1 -1) ^T . Podemos ver que a ₁ · y = 1, a ₂ · y = 0 e b · y = −1. Portanto, o hiperplano com y normal realmente separa o cone convexo a ₁x ₁ + a ₂x ₂ de b .

Interpretação lógica

Uma versão particularmente sugestiva e fácil de lembrar é a seguinte: se um conjunto de desigualdades não tem solução, então uma contradição pode ser produzida a partir dele por combinação linear com coeficientes não negativos. Nas fórmulas: se ≤ é insolúvel, em seguida , , ≥ tem uma solução. Observe que é uma combinação dos lados esquerdo, uma combinação do lado direito das desigualdades. Como a combinação positiva produz um vetor zero à esquerda e a -1 à direita, a contradição é aparente. ${\ displaystyle Ax}$ ${\ displaystyle b}$ ${\ displaystyle y ^ {\ mathsf {T}} A = 0}$ ${\ displaystyle y ^ {\ mathsf {T}} b = -1}$ ${\ displaystyle y}$ ${\ displaystyle 0}$ ${\ displaystyle y ^ {\ mathsf {T}} A}$ ${\ displaystyle y ^ {\ mathsf {T}} b}$

Assim, o lema de Farkas pode ser visto como um teorema da completude lógica : ≤ é um conjunto de "axiomas", as combinações lineares são as "regras de derivação", e o lema diz que, se o conjunto de axiomas for inconsistente, então pode ser refutado usando as regras de derivação. ${\ displaystyle Ax}$ ${\ displaystyle b}$

Variantes

O Farkas Lemma tem várias variantes com diferentes restrições de sinal (a primeira é a versão original):

Ou o sistema tem uma solução com ou o sistema tem uma solução com . ${\ displaystyle \ mathbf {Ax} = \ mathbf {b}}$ ${\ displaystyle \ mathbf {x} \ geq 0}$ ${\ displaystyle \ mathbf {A} ^ {\ mathsf {T}} \ mathbf {y} \ geq 0}$ ${\ displaystyle \ mathbf {b} ^ {\ mathsf {T}} \ mathbf {y} <0}$
Ou o sistema tem uma solução com ou o sistema tem uma solução com e . ${\ displaystyle \ mathbf {Ax} \ leq \ mathbf {b}}$ ${\ displaystyle \ mathbf {x} \ geq 0}$ ${\ displaystyle \ mathbf {A} ^ {\ mathsf {T}} \ mathbf {y} \ geq 0}$ ${\ displaystyle \ mathbf {b} ^ {\ mathsf {T}} \ mathbf {y} <0}$ ${\ displaystyle \ mathbf {y} \ geq 0}$
Ou o sistema tem uma solução com ou o sistema tem uma solução com e . ${\ displaystyle \ mathbf {Ax} \ leq \ mathbf {b}}$ ${\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {A} ^ {\ mathsf {T}} \ mathbf {y} = 0}$ ${\ displaystyle \ mathbf {b} ^ {\ mathsf {T}} \ mathbf {y} <0}$ ${\ displaystyle \ mathbf {y} \ geq 0}$
Ou o sistema tem uma solução com ou o sistema tem uma solução com . ${\ displaystyle \ mathbf {Ax} = \ mathbf {b}}$ ${\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {A} ^ {\ mathsf {T}} \ mathbf {y} = 0}$ ${\ displaystyle \ mathbf {b} ^ {\ mathsf {T}} \ mathbf {y} \ neq 0}$

A última variante é mencionada para ser completa; não é realmente um "lema de Farkas", pois contém apenas igualdades. Sua prova é um exercício de álgebra linear .

Generalizações

Lema generalizada Farkas' - Let , , é um cone convexo fechado , ea dupla cone de é . Se o cone convexo estiver fechado, exatamente uma das seguintes afirmações é verdadeira: ${\ displaystyle \ mathbf {A} \ in \ mathbb {R} ^ {m \ vezes n}}$ ${\ displaystyle \ mathbf {b} \ in \ mathbb {R} ^ {m}}$ ${\ displaystyle \ mathbf {S}}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {S}}$ ${\ displaystyle \ mathbf {S} ^ {*} = \ {\ mathbf {z} \ in \ mathbb {R} ^ {n} \ mid \ mathbf {z} ^ {\ mathsf {T}} \ mathbf {x } \ geq 0, \ forall \ mathbf {x} \ in \ mathbf {S} \}}$ ${\ displaystyle C (\ mathbf {A}) = \ {\ mathbf {A} \ mathbf {x} \ mid \ mathbf {x} \ in \ mathbf {S} \}}$

Existe um tal que e . ${\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {Ax} = \ mathbf {b}}$ ${\ displaystyle \ mathbf {x} \ in \ mathbf {S}}$
Existe tal que e . ${\ displaystyle \ mathbf {y} \ in \ mathbb {R} ^ {m}}$ ${\ displaystyle \ mathbf {A} ^ {\ mathsf {T}} \ mathbf {y} \ in \ mathbf {S} ^ {*}}$ ${\ displaystyle \ mathbf {b} ^ {\ mathsf {T}} \ mathbf {y} <0}$

O lema de Farkas generalizado pode ser interpretado geometricamente da seguinte maneira: ou um vetor está em um dado cone convexo fechado , ou existe um hiperplano separando o vetor do cone; não há outras possibilidades. A condição de fechamento é necessária, veja o teorema da separação I no teorema da separação do hiperplano . Para o lema de Farkas original, é o não negativo orthant , portanto, a condição de fechamento se mantém automaticamente. De fato, para o cone convexo poliédrico, ou seja, existe um tal que , a condição de fechamento se mantém automaticamente. Na otimização convexa , vários tipos de qualificação de restrição, por exemplo, a condição de Slater , são responsáveis pelo fechamento do cone convexo subjacente . ${\ displaystyle \ mathbf {S}}$ ${\ displaystyle \ mathbb {R} _ {+} ^ {n}}$ ${\ displaystyle \ mathbf {B} \ in \ mathbb {R} ^ {n \ times k}}$ ${\ displaystyle \ mathbf {S} = \ {\ mathbf {B} \ mathbf {x} \ mid \ mathbf {x} \ in \ mathbb {R} _ {+} ^ {k} \}}$ ${\ displaystyle C (\ mathbf {A})}$

Definindo e no lema de Farkas generalizado, obtemos o seguinte corolário sobre a solvabilidade para um sistema finito de igualdades lineares: ${\ displaystyle \ mathbf {S} = \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {S} ^ {*} = \ {0 \}}$

Corolário - Let e . Então, exatamente uma das duas afirmações a seguir é verdadeira: ${\ displaystyle \ mathbf {A} \ in \ mathbb {R} ^ {m \ vezes n}}$ ${\ displaystyle \ mathbf {b} \ in \ mathbb {R} ^ {m}}$

Existe tal que . ${\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {Ax} = \ mathbf {b}}$
Existe tal que e . ${\ displaystyle \ mathbf {y} \ in \ mathbb {R} ^ {m}}$ ${\ displaystyle \ mathbf {A} ^ {\ mathsf {T}} \ mathbf {y} = 0}$ ${\ displaystyle \ mathbf {b} ^ {\ mathsf {T}} \ mathbf {y} \ neq 0}$

Outras implicações

O lema de Farkas pode ser variado para muitos outros teoremas de alternativa por meio de modificações simples, como o teorema de Gordan : Ou tem uma solução x , ou tem uma solução diferente de zero y com y ≥ 0. ${\ displaystyle Ax <0}$ ${\ displaystyle A ^ {\ mathsf {T}} y = 0}$

Aplicações comuns do lema de Farkas incluem provar o teorema da dualidade forte associado à programação linear , teoria dos jogos em um nível básico e as restrições de Kuhn-Tucker . Uma extensão do lema de Farkas pode ser usada para analisar as fortes condições de dualidade e construir o dual de um programa semidefinito. É suficiente provar a existência das restrições de Kuhn-Tucker usando a alternativa de Fredholm, mas para que a condição seja necessária, deve-se aplicar o teorema minimax de Von Neumann para mostrar que as equações derivadas de Cauchy não são violadas.

Veja também

Programa linear duplo
Eliminação de Fourier-Motzkin - pode ser usada para provar o lema de Farkas.

Notas

Leitura adicional

Goldman, AJ; Tucker, AW (1956). "Cones Convexos Poliédricos" . Em Kuhn, HW; Tucker, AW (eds.). Desigualdades lineares e sistemas relacionados . Princeton: Princeton University Press. pp. 19–40. ISBN 0691079994.
Rockafellar, RT (1979). Análise convexa . Princeton University Press. p. 200
Kutateladze SS O lema Farkas revisitado. Siberian Mathematical Journal , 2010, Vol. 51, No. 1, 78-87.

Languages

In other projects