퍼르커시 보조정리
퍼르커시 보조정리는 선형 계획법 및 최적화 이론에서 중요한 역할을 하는 정리 중 하나입니다. 이 정리는 선형 부등식 시스템의 해 존재 여부와 관련된 조건을 제시하며, 쌍대성 이론과 밀접한 관련을 갖습니다.
구체적으로, 퍼르커시 보조정리는 다음과 같이 표현될 수 있습니다:
정리 (퍼르커시 보조정리): 행렬 A와 벡터 b가 주어졌을 때, 다음 두 명제 중 정확히 하나만 성립한다.
- Ax = b, x ≥ 0을 만족하는 벡터 x가 존재한다.
- ATy ≥ 0, bTy < 0을 만족하는 벡터 y가 존재한다.
여기서 AT는 행렬 A의 전치 행렬을 나타냅니다.
의미:
- 첫 번째 명제는 A와 b로 정의되는 선형 부등식 시스템이 해를 갖는다는 것을 의미합니다. 즉, A의 열 벡터들의 비음수 선형 결합으로 벡터 b를 표현할 수 있다는 것입니다.
- 두 번째 명제는 ATy ≥ 0을 만족하는 벡터 y에 대해, bTy가 항상 음수가 된다는 것을 의미합니다. 이는 어떤 벡터 y가 AT의 열 벡터들과 이루는 각도가 모두 90도 이하이지만, 벡터 b와는 90도 이상이라는 의미로 해석될 수 있습니다.
응용:
퍼르커시 보조정리는 선형 계획법의 쌍대성 정리 증명, 최적화 문제의 해 존재 여부 판별, 게임 이론 등 다양한 분야에서 활용됩니다. 특히, 제약 조건이 주어진 최적화 문제에서 최적해의 존재성을 증명하거나, 최적해를 구하는 알고리즘의 타당성을 입증하는 데 중요한 도구로 사용됩니다.
참고:
퍼르커시 보조정리는 Farkas' Lemma 또는 Farkas Lemma라고도 불립니다. 이 정리는 헝가리의 수학자 줄리어스 퍼르커시 (Julius Farkas)에 의해 처음 제시되었습니다.