AI를 위한 필수 수학

438

AI

를 위한 필수 수학

활성 제약 조건

점

x

)

v

의 좌표를 제약 조건

ax b

ii

$ $

v

v

v

에 대입했을 때 등식이 성립한다면, 즉

ax b

ii

$ =

)

v

v

v

면 이 제

약 조건은 점

x

)

v

에서 활성 상태다. 기하학적으로 이는

x

)

v

가 반공간의 내부가 아닌 경계에 위치

한다는 것을 의미한다.

다면체의 꼭짓점

기하학적으로 꼭짓점을 형성하려면 적절한 수의 초평면이 교차해야 한다. 대수적으로 꼭짓점

에서는 적절한 수의 제약 조건이 활성 상태다. 이것이 바로 기본 실행 가능 해이며 단체법을 논

의할 때 자세히 다룰 것이다.

인접 꼭짓점을 찾기 위한 인접 기저

인접 기저

adjacent

base

는 행렬

A

의 열 중 한 열을 제외한 모든 열을 공유하는 두 개의 부분 집합이

다. 인접한 꼭짓점의 좌표를 계산하기 위해 인접 기저를 사용한다. 단체법에서는 기하학적으로

한 꼭짓점에서 인접한 꼭짓점으로 이동해야 하며, 인접 기저를 사용하면 이를 체계적인 대수적

방법으로 수행할 수 있다. 이에 대해서도 단체법을 논의할 때 자세히 다룰 것이다.

퇴화 사례

이를 시각화하기 위해

2

차원에서 두 직선이 교차하여 꼭짓점을 형성한다고 가정해보자. 이제

만약 세 번째 직선이 정확히 같은 점에서 교차한다면 다시 말해

2

차원의 동일한 점에서 둘 이

상의 제약 조건이 활성 상태라면 이는 퇴화 사례다.

n

차원에서는 점

x

)

v

를 통과하는 초평면이

n

개 이상이거나

n

개 이상의 제약 조건이 활성 상태다. 대수적으로 이러한 퇴화 사례로 인해 최

적화 알고리즘에 다음과 같은 문제가 발생한다.