📂최적화이론

심플렉스 메소드의 초기화와 보조문제

Initialization and Auxiliary Problem of Simplex Method

빌드업

$$ \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}$ 에 대해 선형계획문제가 위와 같이 방정식 폼으로 나타난다고 하자. 그리고 모든 $j = 1 , \cdots , n+m$ 에 대해 $x_{k} \ge 0$ 이고, $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*} $$

선형계획문제의 첫 딕셔너리가 위와 같이 주어져 있다고 하자. 심플렉스 메소드는 기본적으로 이렇게 주어진 연립방정식들의 해를 바꿔가면서 최적화를 하는 방법인데, 처음부터 바꿔갈 해가 없다면 어떻게 해야할까? ¹ 언뜻 생각해보면 앞으로 최적화는 어떻게든 될테니 아무 값이나 넣어서 대충 시작하면 될 것 같은데, 가령 $x_{1} , \cdots , x_{n} = 0$ 으로 두면 $x_{n+i} = b_{i}$ 가 되므로 $$ \left( x_{1}, \cdots , x_{n} , x_{n+1} , \cdots , x_{n+m} \right) = \left( 0, \cdots , 0 , b_{1} , \cdots , b_{m} \right) $$ 는 제약조건을 반드시 만족시키는것 같지만 당장 $b_{i} < 0$ 이 되면 $\mathbf{x} \ge \mathbf{0}$ 에 위배된다. 한편 심플렉스 메소드는 심플렉스의 모든 버텍스를 탐색하면 반드시 최적화에 성공할 수는 있는데, 이러한 전략 하에서 아무 가용해를 찾는 것은 실제 최적해를 찾는 것과 같은 정도로 어렵다. ² 물론 이는 아무런 대책이 없을 때고, 당연히 수학자들은 그 대책을 마련해놓았다.

용어

보조 문제

우리는 심플렉스 메소드의 초기화^{Initialization}에 있어서 위와 같은 어려움을 비가용성^{Infeasibility}이라 부르고, 새로운 변수를 도입하는 트릭으로 비가용성을 해소한 딕셔너리를 간단히 보조 문제^{Auxiliary Problem}라 부른다.

페이즈

보조문제를 만들고 그 첫번째 가용해를 구하는 과정을 페이즈 1^{Phase 1}이라 하고, 실제 심플렉스 메소드를 적용해서 최적화하는 과정을 페이즈 2^{Phase 2}라 한다.

예시

간단한 문제로써 보조 문제가 어떤 것인지 실제로 확인해보자. $x_{1} , x_{2} , x_{3} \ge 0$ 에 대해 다음과 같은 선형계획문제가 주어져 있다고 하자. $$ \begin{matrix} \text{Maximize} & & x_{1} & + & 2x_{2} \\ \text{subject to} & & x_{1} & + & 3x_{2} & + & x_{3} & = & 4 \\ & & & & 2x_{2} & + & x_{3} & = & 2 \end{matrix} $$

이 문제는 심플렉스의 아무 버텍스나 찍는다고 초기화가 잘 되지 않는다는 걸 보여준다. 예를 들어 가장 기본적인 점인 $\left( x_{1} , x_{2} , x_{3} \right) = (0,0,0)$ 을 생각해보면 제약조건을 만족시키지 못하는 것이다. 물론 사람에 따라서는 예리하게 $(1,1,0)$ 를 바로 찾을지도 모르겠지만, 이 문제는 어디까지나 예를 들기 위해 만들어진 아주 간단한 문제라는 것을 감안해야한다. 실제 문제에서 $A \in \mathbb{R}^{100 \times 30}$ 같은 게 주어졌다면 암산이나 직관은 전혀 도움이 되지 않는다.

이를 해결하는 아이디어는 간단하다. 부등식 꼴 선형계획문제의 방정식 폼을 만들때 슬랙 변수^{Slack Variable}를 도입했던 것처럼 보조 변수^{Auxiliary Variable}를 넣어 완충제와 같은 역할을 시키는 것이다. 새로운 $x_{4} , x_{5} \ge 0$ 를 $$ \begin{matrix} \text{Maximize} & & & & & & & - & x_{4} & - & x_{5} & \\ \text{subject to} & & x_{1} & + & 3x_{2} & + & x_{3} & + & x_{4} & & & = & 4 \\ & & x_{1} & & 2x_{2} & + & x_{3} & & & + & x_{5} & = & 2 \end{matrix} $$ 과 같이 넣어보면 아주 간단하게 $(0,0,0,4,2)$ 라는 초기값을 찾을 수 있다. 우리는 이 점에서 심플렉스 메소드를 시작하면 되고, 여기까지를 페이즈 1이라 부르기로 했다.