본 자료는 Bertsimas 형님의 Introduction to LINEAR OPTIMIZATION을 내가 알아보기 위해 정리한 글 입니다. 반박은 언제나 환영이고, 아마 그 말이 대부분 맞을 껍니다.

들어가는 글

표준형(standard form) 선형 계획 문제에서 최적해가 있다면, 그것은 최적 기저가능해(basic feasible solution)이다.
심플렉스 해법은 이를 기반으로 하고, cost가 적은 방향으로 가능해 집합의 꼭지를 따라서 기저 가능해를 이동하면서 최적해를 찾아나간다. 쉽게 말해서 가능해 집합의 꼭지점를 따라 이동하면서 비용이 감소하지 않는 기저가능해에서 정지하고 이것이 바로 최적해이다.

여기서 말하는 표준형은 아래와 같다.

3.1 Optimaltity conditions

현재 $\mathbf{x} \in P$에서 $\mathbf{x}$를 vector $\mathbf{d} \in \R^n$의 방향으로 이동할 예정이에요. 왜냐면 그 방향을 비용을 감소시키는 방향이고 비용이 감소되면서 최적해에 가까워지기 때문이죠. 그런데 그 방향은 당연히 기저가능해 집합에서 벗어나면 안되겠죠? 이걸 수학적으로 이야기하면 아래와 같아요.

Definition 3.1

• Let $\mathbf{x}$ be an element of a polyhedron $P$. A vector $\mathbf{d} \in \R^n$ is said to be a feasible direction at $\mathbf{x}$, if there exists a potitive scalar $\theta$ for which $\mathbf{x+\theta d} \in P$.

$P$라는 다면체 공간이 해집합이고 $\mathbf{x}$는 그 공간 안에 있어요. 그럼 위에서 말했던 것처럼 $\mathbf{x}$는 그 공간에서 꼭지점에서 꼭지점으로 이동하면서 비용이 감소하는 것을 찾아나간다고 했어요. 근데 그 방향이 다면체 바깥으로 이동하면 해집합을 벗어나기 때문에 해를 찾는 것이 아니겠죠? 위의 Definition 3.1은 그 방향을 정의해주는 이야기에요. 해집합을 벗어나지 않는 방향, 그 방향을 feasible direction이라고 해요.

추후에 이야기하겠지만, 우리는 이동이라는 단어에 주목해야해요. 이동이라는 말에는 어디로, 얼마나 이동해서 최적해를 빠르게 찾느냐 이게 바로 심플렉스의 핵심 개념입니다.
여기서 '어디로'는 바로 $\mathbf{d} \in \R^n$에 해당하고 '얼마나'는 $\theta$에 해당돼요. 각설하고 다시 '어디로'($\mathbf{d} \in \R^n$)에 집중해볼게요.

어디로 가는지 알기 위해서는 우리는 $\mathbf{x}$를 기저변수(basic variable)와 비기저변수(nonbasic variable), 둘로 나눌꺼에요. 기저변수는 해를 구성하는 변수이고, 비기저변수는 해를 구성하지 않고 0으로 표현되는 변수를 뜻해요.

• 기저변수(basic variable): 해를 구성
• 비기저변수(nonbasic variable): 해를 구성하지 않아 0으로 표현

기저변수임에도 0으로 표현되는 경우가 있어요. 그건 degenerate한 경우라고 해요. 추후에 또 설명이 나오니 현재 설명하는 것은 기저변수인 경우에는 0이 없음을 가정하고 이야기할게요.

• 기저변수의 인덱스: $B(1),...,B(m)$
• 상응하는 기저 행렬(basis matrix)를 $\mathbf{B= \begin{bmatrix} A_{B(1)} & \cdots & A_{B(m)} \end{bmatrix}}$
• 기저변수 벡터: $\mathbf{x}_{B}=(x_{B(1)},\cdots,x_{B(m)})$

여기서 우리가 알고 싶은 것은 해를 구성하는 기저변수 벡터이고 이는 아래와 같이 계산될 수 있어요.

심플렉스는 현재 $\mathbf{x}$가 위치한 곳에서 얼마나, 어디로 이동하면서 해를 개선해나간다고 했어요. 그럼 이동을 어떻게 하는지 알아볼게요.

여기서 이동한다는 것은 $\mathbf{x}$의 값이 변한다는 것이고 $\mathbf{x+\theta d}$로 값이 변하면서 해를 개선해나가는거에요. Definition 3.1 을 보면 $\mathbf{x+\theta d}$로 해가 변해도 해집합 안에 있다는 것을 알 수 있죠.

우리는 위쪽에서 기저변수와 비기저변수를 나눴고 비기저변수는 해를 구성하지 않는 0인 변수라고 했어요. 그럼 현재 $\mathbf{x}$를 $\theta$만큼 이동시키기 위해서 비기저변수 중 하나를 1로 바꿔줄거에요. 하나만 1로 변하고 나머지는 모두 0 그대로를 유지하고 있어요. 이를 교재와 같이 표현해볼게요.

비기저변수 $x_{j}$(원래는 0이었음)를 선택해서 $\mathbf{x}$를 $\mathbf{x+\theta d}$로 옮길꺼에요. Definition 3.1에 적혀있듯이 $\theta$인 양수만큼 변화될꺼에요. 이 때, 비기저변수 중 $x_{j}$가 아닌 애들은 모두 0을 유지해야해요. 대수학적으로 표현하면 $d_{j}=1$이고 $d_{i}=0$인데 여기서 $i$는 $j$가 아닌 모든 비기저변수의 인덱스를 말해요.

이를 통해서 벡터 $\mathbf{x_{B}}$는 $\mathbf{x_{B}+\theta d_{B}}$로 이동하는데, 여기서 $\mathbf{d_{B}}=(d_{B(1)}, d_{B(2)}, \cdots, d_{B(m)})$ 이고 이는 기저변수에 해당하는 $\mathbf{d}$의 원소로 구성된 벡터에요.

여기서 중요한 것은, $\mathbf{A(x+\theta d)}$나 $\mathbf{Ax}$나 모두 $\mathbf{b}$와 같아요. 왜냐면 Definition 3.1에서 보면 모두 polyhedron $P$ 안에 있기 때문이죠. $\theta>0$인 경우, $\mathbf{Ad=0}$이 되어야 해요. 위에서도 말했듯이 $d_{j}=1$이고 $d_{i}=0$($i$는 $j$가 아닌 모든 비기저변수의 인덱스)이면 아래와 같이 식이 정리될 수 있어요.

여기서 basis matrix $\mathbf{B}$는 가역하기(역행렬이 있기) 때문에

를 정리해서 아래와 같이 $\mathbf{d}_{B}$를 구할 수 있어요.

우리가 앞서 정의한 direction vector $\mathbf{d}$는 $j$번째 basic direction이라고 할 수 있어요. 지금까지는 equality constraints에 대해서만 확인해보았는데, nonnegative constraints에 대해서는 어떨까요? 우리는 $x_{j}$가 증가된다는데 주목해야해요. 여기서 다른 비기저변수는 여전히 0을 유지하고 있다는 걸 잊어서는 안돼요. 따라서 우리는 기저변수에 대해 확인을 해봐야하죠. 두 가지 케이스가 있고 한번 확인해보겠습니다.

(a) $\mathbf{x}$를 nondegenerate basic feasible solution이라 가정하면, $\mathbf{x}_{B}>0$ 이니까 $\mathbf{x}_{B}+ \theta \mathbf{d}_{b}\ge0$ 이고 feasibility는 유지가 되죠. 주의해야할 건 $\theta$가 충분히 작을(sufficiently small) 때 유지가 됩니다.

(b) $\mathbf{x}$를 degenerate한 경우에는 어떻게 될까요? 그럼 $\mathbf{x}$가 항상 feasible direction이 아닐 수도 있겠죠. $\mathbf{x}_{B(i)}$가 0인데 $\mathbf{d}_{B}=\mathbf{-B^{-1}}A_{j}$의 $d_{B(i)}$가 negative하게 될 수도 있게 되죠. 이런 경우에, $j$번째 basic direction을 따라간다면 $x_{B(i)}$에 대한 비음제약을 위배하게 되고 infeasible하게 됩니다.