본 포스팅에서는 현재 코스웍으로 듣고 있는 최적화 강의 중 일부를 정리해보려고 한다. Algorithm에 대한 자세한 설명은 다루지 못할 않을 예정이지만, 전반적으로 어떻게 동작하는지 이해하는 데 도움이 되었으면 좋겠다.

Standard form for the simplex algorithm

Linear program (LP)를 풀기 위한 algorithm에는 크게 다음의 세 방법이 있다.

1. Kantorovich's algorithm

2. Simplex algorithm

3. Interior point method (based on strong duality)

이 중에서 simplex algorithm에 대해 알아보자.

이에 앞서, LP의 standard form을 떠올리면 다음과 같다.

Simplex algorithm은 위의 식 형태와 달라 보이지만 사실은 동일한, 다음과 같은 형태를 기본으로 한다. 주목할 점은 equality constraint 대신 $x$의 부호에 대한 제한 조건이 추가되었다는 것이다.

LP의 standard form을 A, simplex algorithm은 B 로 두자. 이때 B 에서 A 로의 변환은 쉽게 받아들일 수 있다.

(B 의 두 constraint 식을 한 쪽으로 정리하면, A 의 '$Ax-b \leq 0$' inequality constraint로 한번에 정리할 수 있기 때문이다.)

그렇다면 이제 A 에서 B 로의 conversion을 알아보자. 이것이 성립하면 우리는 A 가 B 와 동치임을 알 수 있다.

$\min$에서 $\max$ problem 으로의 변환은 단순히 부호를 flip하면 되는 문제이므로 간단하다. 여기서 핵심은 'A 에서의 equality constraint가 B 에서의 $x \geq 0$으로 어떻게 바뀌는지' 이다.

이를 간단한 예를 통해 설명해보겠다. 다음의 LP를 보자.

우선 두 단계를 통해 equality constraint가 없는 $\max$ problem으로 바꿔볼 것이다.

• Flipping the sign of objective function: $\max \textrm{ } -(x_1 + x_2 + x_3)$
• Equality to inequality: '=' $\rightarrow$ '$\leq$' + '$\geq$'

이제 $x \geq 0$ 즉, non-negativity constraint를 얻기 위한 방법을 생각해보자. 이를 위해서는 기존의 각 변수들을 새로운 변수들로 표현해주면 된다.

이후 $x_1, x_2, x_3$를 새로운 변수 ($x_4 \sim x_9$)들로 표현해주면, conversion이 성립한다.

한편 simplex algorithm의 전체 과정은 복잡하기 때문에, 보다 간단한 예시로 이를 설명하려 한다.

Simplex algorithm

Standard form:

Example:

Conversion into the 'slack form'

이 단계에서는 slack variable 이라는 non-negative 변수를 새로 추가하여 inequality constraint를 equality constraint로 바꿀 것이다.

즉, 위의 예시에서 slack variable ($s_1, s_2 \geq 0$) 2개를 추가하면 문제를 다음과 같이 바꿔풀 수 있다.

식을 살펴보면 우선 objective function이 $z$ 로 대체되었고 slack variable $s_1, s_2$ 가 추가되었다. 여기서 중요한 점은 $\mathbf{78}, \mathbf{36}$ 자리에 위치한 숫자가 non-negative 여야 한다는 것이다. 만약 그렇지 않다면, 기존 부등식의 부호를 바꾼 다음 slack variable을 빼는 형태로 식을 구성해야 한다. (e.g. $-2x_1 -4x_2 \leq -34$ 는 $2x_1 + 4x_2 - s_1 = 34$ 의 형태가 되도록)

Iterative algorithm (Key idea)

이번에는 각 iteration 마다 다음의 단계들을 수행할 것이다.

Step 1. Initial feasible solution 을 선택

• Choose an initial feasible solution.

Step 2. Z-maximizing direction 을 따라 solution을 약간 바꿈 (perturb)

• Perturb the solution along a z-maximizing direction.

이 역시 예제를 통해 이해해보자.

Iteration #1

먼저, 다음의 두 constraint를 보자.

이는 미지수 4개, 식 2개로 구성되어 있기 때문에 근의 개수가 무한히 많은 상태이다. 여기서 가장 간단한 feasible solution 을 생각해보면 $x_1 = x_2 = 0$ 일 때이고, 그때의 ($x_1, x_2, s_1, s_2$) = (0, 0, 78, 36) 이다. ($\Rightarrow$ Step 1, $z=0$ here)

한편 우리는 $x_1$ 이나 $x_2$를 증가시키면 $z$ 값이 커진다는 것을 알고 있다. 둘 ($x_1$ or $x_2$)을 증가시키는 방법의 수는 총 세 가지가 있는데 (하나 씩 키우는 경우 2가지 + 둘 다 키우는 경우 1가지) 이때, 각각을 키우는 2가지 case만 고려하더라도 optimal 값에 도달할 수 있다. (이는 일단 받아들이자) 이제 이 두 가지 case를 비교해보자.

1. ($x_1, x_2$) = ($\delta, 0$) $(\delta \geq 0)$

따라서 $\delta \leq \min(26,9)$, $\delta$의 최대값은 9 이므로 이때의 $z_{\textrm{max}} = 45$ 이다.

2. ($x_1, x_2$) = ($0, \delta$)

따라서 $\delta \leq \min(78/5,36)$, $\delta$의 최대값은 $78/5$ 이므로 이때의 $z_{\textrm{max}} = 62.4$ 이다. 즉, 이때의 $z_{\textrm{max}}$가 더 크기 때문에 이 perturbation 을 선택한다. ($\Rightarrow$ Step 2)

Iteration #2

앞선 iteration에서 얻은 두 번째 feasible solution 은 ($x_1, x_2, s_1, s_2$) = (0, 78/5, 0, 102/5) 이다. 이 solution을 보면 0 값을 가지고 있는 $x_1$ 이나 $s_1$을 건들여야 할 단계임을 알 수 있는데, $z$ 값이 $x_1$과 $x_2$로만 이루어져 있는 상황이라 $s_1$이 $z$ 값에 어떤 영향을 주는지 알기가 쉽지 않다. 따라서 이런 경우에는 Gaussian elimination을 사용한다.

이제, z-maximizing direction 을 구해보자.

1. ($x_1, s_1$) = ($\delta, 0$) $(\delta \geq 0)$

이때 두번째 조건은 두 개의 변수 $x_2, s_2$를 포함하고 있기 때문에 condition이 loose 할 수 있다. 따라서 현재 $4x_1 + x_2 + s_2$의 형태로 구성된 조건을 '$?\cdot x_1+?\cdot s_1+?\cdot s_2$' 와 같이 바꿀 수 있으면 좋을 것인데, 이때도 이전과 같이 Gaussian elimination을 적용한다.

이제 아래의 식에서 Iteration #1 의 step 2 같이 perturbation 을 진행하면, (initial: ($x_1, x_2, s_1, s_2$) = (0, 78/5, 0, 102/5), z = 62.4)

따라서 $\delta \leq \min(26,102/17)$, $\delta$의 최대값은 6 이므로 이때의 $z_{\textrm{max}} = 78$ 이다. 이렇게 구한 $z$ 값은 기존의 값 (62.4) 보다 큰 것을 확인할 수 있다.

2. ($x_1, s_1$) = ($0, \delta$)
   해당 case는 $s_1$이 증가함에 따라 $z$ 값이 감소하기 때문에 고려하지 않는다.

Iteration #3

세 번째 feasible solution 은 ($x_1, x_2, s_1, s_2$) = (6, 12, 0, 0) 이다. ($z_{\textrm{max}} = 78$)

이번에는 $s_1$과 $s_2$를 건들여 볼 것인데, 이전의 경우와 같이 $5z - 13x_1 + 4s_1$ 만으로는 $s_2$가 $z$에 미치는 영향을 보기 어려우니 Gaussian elimination을 이용하자.

이제 기존의 문제는 아래와 같이 정리된다.

그런데 이번 objective function을 보면 $s_1$이 커지든 $s_2$가 커지든 $z$는 감소한다. 따라서 iteration은 멈추고 optimal 한 $(x_1^*, x_2^*) = (6,12)$, 그때의 $z^*$ 값은 78 이다.

Reference

카이스트 서창호 교수님 강의 - EE424: 최적화개론 lecture 6.