📂최적화이론

심플렉스 메소드의 사이클링

정의

$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

행렬 $A \in \mathbb{R}^{m \times n}$ 과 $\mathbf{b} \in \mathbb{R}^{m \times 1}$ 와 $\mathbf{c} \in \mathbb{R}^{n}$ 에 대해 선형계획문제가 위와 같이 방정식 폼으로 나타난다고 하고, $i = 1 , \cdots , m$ 에 대해 그 딕셔너리를 다음과 같이 나타내자. $$ \begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*} $$

어떤 $i \in \mathcal{B}$ 에 대해 $b_{i} = 0$ 이면 이 딕셔너리가 타락했다^degenerate라 하고, 이 때문에 심플렉스 메소드에 진전이 없는 현상을 사이클링^cycling이라 한다¹.

설명

타락…?

네이버에 검색해보면 Degenerate는 악화되다, 퇴폐적인, 타락한, 퇴보한, 퇴화한 등으로 번역된다. 당연하지만 이공계에서 가장 유명한 용례는 서로 다른 두 파동함수가 같은 고유값을 가질 때를 말하는 양자역학에서의 축퇴고, 선형대수학에서도 어떤 벡터가 다른 벡터들의 선형결합으로 나타날 때 간혹 사용하기도 한다. 이러한 의미에서 영어 그대로를 받아들이자면 $b_{i} = 0$ 일 때 Degenerate라 하는 것은 굉장히 상식적이다. 문제는 한국어로 번역할 때 축퇴랑 의미가 전혀 안 맞다는 것이다. 아예 다른 표현을 찾을 수도 있었겠지만, 생각해보니 어차피 심플렉스 메소드가 잘 돌아가지 않는다는 의미에서 타락도 아주 틀린 말은 아닌 것 같아 그냥 타락으로 순화했다.

예시

$$ \begin{matrix} \text{Maximize} & & & & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 0 \\ & & 1_{2} & & & \le & 2 \end{matrix} $$

가령 위와 같은 선형계획문제를 딕셔너리로 적어보면 다음과 같다. $$ \begin{matrix} \zeta & = & & & & & & x_{2} \\ x_{3} & = & & & & x_{1} & - & x_{2} \\ x_{4} & = & & 2 & - & x_{1} & & \end{matrix} $$

이때 $i = 3$ 에 대해 $b_{i} = 0$ 인데, 이 때문에 변수를 치환해봐도 목적값^{objective value}은 변하지 않고 빙빙 돌게 된다. 다시 말해, $t$ 번째 딕셔너리를 $D_{t}$ 라 했을때 다음을 만족하는 어떤 $k \in \mathbb{N}$ 이 존재하게 되는 것이다. $$ D_{t} = D_{t+k} $$

이게 아주 간단한 예시로 보니까 저런 일이 왜 있나 싶지만 사람의 눈으로 한번에 읽기 힘들 정도로 큰 $A$ 만 돼도 언제 어떤 사이클이 일어날지 알 수가 없다. 예를 들어보면 치환을 하다가 기가 막히게 $b_{i_{1}} = -b_{i_{2}}$ 가 맞물려서 $0$ 이 생겨나는 식이다. 프로그래밍적으로 이것을 감지하는 것 자체는 별로 어렵지 않겠지만, 이를 어떻게 헤쳐나갈지가 문제다.

해법: 브랜드 룰

진입 변수^{entering variable}과 이탈 변수를^{leaving variable}을 각각의 $\mathcal{N}$ 과 $\mathcal{B}$ 에서 인덱스가 가장 작은 걸로 고르면 사이클에 빠지지 않는다. 이러한 선택법을 브랜드 룰^{Brand’s rule}이라 부른다.

반대로는 심플렉스 메소드가 끝나지 않을 때 딕셔너리가 사이클에 빠졌음을 다음의 정리로 보장할 수 있다.

정리

만약 심플렉스 메소드가 끝나지 않는다면, 딕셔너리가 사이클에 빠진 것이다.

증명

선형계획문제에서 기저가용해가 되는 모든 경우를 그리디 알고리즘으로, 다시 말해 우리가 상상할 수 있는 최악의 방법으로 찾는다고 생각해보자. $n+m$ 개의 변수 중 $n$ 개의 기저변수를 찾는 경우의 수는 $$ \binom{n+m}{n} = {{ (n+m)! } \over { n!m! }} $$ 으로, 상당히 큰 수지만 어쨌든 유한하다. 이 모든 경우를 다 계산해보면 반드시 최적화를 끝낼 수 있음에도 불구하고 심플렉스 메소드가 멈추지 않는다는 것은 사이클에 빠져있다는 의미가 된다.

■

선형계획법의 기본정리

이 정리는 선형계획법의 기본정리 증명에 사용된다.