퍼르커시 보조정리

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

정의

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

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

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

에 속한다.

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

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

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

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

역사

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