퍼르커시 보조정리

수학적 최적화에서 퍼르커시 보조정리(영어: Farkas’s lemma)는 어떤 볼록뿔과 이에 속하지 않는 벡터 사이를 초평면으로 분리할 수 있다는 정리다.

정의

$A$가 $m\times n$ 실수 행렬이며, $\mathbf {b} \in \mathbb {R} ^{m}$가 $m$차원 실수 벡터라고 하자. 그렇다면, 다음 두 명제 가운데 정확히 하나만이 성립한다.

• $A\mathbf {x} =\mathbf {b}$이며 $\mathbf {x} \geq 0$인 $\mathbf {x} \in \mathbb {R} ^{n}$이 존재한다. 즉, $\mathbf {b}$는 볼록뿔

$\left\{\sum _{i=1}^{n}\mathbf {A} _{i}x_{i}|x_{i}\geq 0\right\}$

에 속한다.

• $A^{\top }\mathbf {y} \geq 0$이며 $\mathbf {b} ^{\top }\mathbf {y} <0$인 $\mathbf {y} \in \mathbb {R} ^{m}$이 존재한다. 즉, $(n-1)$차원 초평면

$\operatorname {Span} \{\mathbf {y} \}^{\perp }=\left\{\mathbf {z} \in \mathbb {R} ^{m}|\mathbf {z} ^{\top }\mathbf {y} =0\right\}$

이 존재하여, $\mathbf {b}$와 볼록뿔 $\{\sum _{i=1}^{n}\mathbf {A} _{i}x_{i}|x_{i}\geq 0\}$은 이 초평면의 양쪽에 각각 존재한다.

여기서 $\mathbf {x} \in \mathbb {R} ^{m}$이 $\mathbf {x} \geq 0$라는 것은 $\mathbf {x}$의 모든 성분이 음수가 아니라는 것이다.

역사

헝가리의 과학자 퍼르커시 줄러(헝가리어: Farkas Gyula)가 1894년 증명하였다.

각주

• Berkovitz, Leonard D. (2001). 《Convexity and Optimization in $\mathbb {R} ^{n}$》 (영어). New York: John Wiley & Sons. ISBN 978-0-471-35281-5. 
• Kutateladze, S. (2010). “The Farkas lemma revisited” (PDF). 《Siberian Mathematical Journal》 (영어) 51 (1): 78–87. doi:10.1007/s11202-010-0010-y. 

외부 링크

• Weisstein, Eric Wolfgang. “Farkas’s lemma”. 《Wolfram MathWorld》 (영어). Wolfram Research.