네트워크에서 flows는 cuts보다 작습니다. 그러나 maximum flow와 minimum cut이 정확히 일치하는 것을 지난 포스팅에서 살펴봤습니다. 따라서 각각은 서로의 최적성의 검증이 됩니다. maximum flow을 선형계획법에 의해 해결될 수 있는 어떤 문제로 일반화하는 현상을 주목할 만합니다. 모든 linear maximization 문제는 dual minimization(쌍대 최소화) 문제를 가진다는 것을 알 수 있습니다. 그리고 이들은 flows와 cuts과 같은 방식으로 서로 관련이 있습니다.
쌍대성(duality)가 무엇인지 이해하기 위해, 첫 번째 포스팅에서 예제로 살펴봤던 A와 B의 상품을 파는 상점 예제를 다시 가져와보겠습니다.
심플렉스(simplex)는 목표값(objective value)이 1900을 가지는 (\(x_1\), \(x_2\)) = (100, 300)이 되는 최적의 해답을 찾았습니다. 이렇게 찾은 해답이 어떤 방법으로 검사될 수 있는지 살펴보겠습니다.
먼저 두 번째 부등식에 6을 곱하고 첫 번째 부등식에 더하면 다음을 얻을 수 있습니다.
\[x_1 + 6x_2 \leq 2000\]
이 식은 2000보다 더 많은 이익을 얻는 것이 불가능하다는 것을 보여줍니다. 그러면, LP 제약 조건의 다른 조합을 어떻게 추가하면 이 상한을 1900에 더 가깝도록 얻을 수 있을까요? 몇 가지 실험 이후에, 처음 3개의 부등식에 각각 0, 5, 1을 곱하고 모두 더하면 다음의 식을 얻을 수 있습니다.
\[x_1 + 6x_2 \leq 1900\]
따라서 1900이 실제 가장 좋으면서 가능한 값이 되어야 합니다. 승수(multiplier) (0, 5, 1)은 마법처럼 최적성의 검증을 구성합니다. 이 같은 검증이 LP에 대해 존재한다는 것은 놀랄만한 일입니다. 그리고 이러한 검증이 있다는 것을 알지라도 이 값들은 어떻게 체계적으로 발견할 수 있을까요?
이 세 가지의 승수에 대해 우리가 기대하는 것을 설명하면서 이 문제를 살펴보겠습니다. \(y_1, y_2, y_3\)를 세 가지의 승수라고 하겠습니다.
이 식으로 시작하기 위해서, \(y_i\)들은 음이 아닌 값이어야 하는데 그렇지 않으면 이들은 부등식을 곱하기에는 적당하지 않습니다(음수를 부등식에 곱하면 \(\leq\)가 \(\geq\)로 바뀌기 때문). 각 부등식을 승수와 곱해 모두 더한 후에는 아래의 부등식을 얻을 수 있습니다.
위 식에서 우리는 우변이 최적의 솔루션이 상한이 되도록 좌변이 목적 함수 \(x_1 + 6x_2\)처럼 보이길 원합니다. 이렇게 하기 위해서는 \(y_1 + y_3\)은 1이 되어야 하고, \(y_2 + y_3\)은 6이 되어야 합니다.
따라서, 우리는 다음의 식과 같은 상한을 얻게 됩니다.
단순히 \(y_i\) 값들을 크게 만들어서 오른쪽의 부등식을 만족하는 y를 쉽게 찾을 수 있습니다. 예를 들어, (\(y_1, y_2, y_3\)) = (5, 3, 6)이 될 수 있습니다. 그러나 이 숭수들은 LP의 최적 솔루션이 최대 200x5 + 300x3 + 400x6 = 4300이며, 그 상한이 너무 멀다는 것을 말해줍니다. 우리는 가능한 한 타이트한 상한을 원하기 때문에 앞의 부등식에서 제시된 \(200y_1 + 300y_2 + 400y_3\)을 최소화해야 합니다. 그리고 이는 새로운 선형계획법입니다.
따라서, 원래 LP에서 가장 베스트인 상한을 만드는 승수들의 집합을 발견하는 것은 새로운 LP를 해결하는 것과 같습니다.
디자인에 의해, 이 쌍대 LP의 어떤 가능한 값은 원래(original primal) LP에서 상한입니다. 따라서 우리가 어떻게든 서로 같은 원 문제(Primal)과 쌍대 문제(Dual)의 가능한 값들의 쌍을 구한다면, 이들은 둘 다 최적이 됩니다. 위의 문제에서는 다음과 같은 쌍을 구하였습니다.
이 솔루션 쌍은 둘 다 값 1900을 갖고 그리하여 이들은 각자 서로의 최적성을 검증합니다(아래 그림).
놀랍지만, 이는 운이 좋아서 그런게 아닌 일반적 현상입니다.
이를 이용하기 위해서 먼저 각 원(primal) 제약들에 대한 승수를 만들고, 상응되는 원 변수들의 목적 계수를 원 문제의 모든 변수들에 대하여 쌍대 문제의 제약을 작성하고, 원 문제의 우변에 의해 가중치가 부여된 승수의 합을 최적화하는 과정입니다. 이는 아래 그림에서 보는 것과 같이 임의의 LP에 대해 실행될 수 있으며,
아래 식처럼 더 보편적으로 실행될 수 있습니다.
바로 위 그림에는 한 가지 주목할 만한 사항이 있습니다. 원 문제에 등식(equality) 제약이 있는 경우, 대응되는 승수(또는 쌍대 변수)는 non-negative일 필요가 없습니다. 이는 음수를 곱할 때에도 방정식의 유효성이 유지되기 때문입니다. 따라서, 항등식의 승수는 제한이 없는 변수입니다. 또한 행렬 \(A = (a_{ij})\)는 각 행들에 원 문제의 제약으로, 그리고 각 열이 쌍대 문제의 제약으로 정의된다는 것에 주목합니다. 이때 행렬에서 두 LP들 사이에 단순 대칭이 있음을 알 수 있습니다.
이러한 구성에 의해, 쌍대의 어떤 가능한 해답은 원 문제의 어떤 가능한 해답에서의 상한입니다. 그러나 이들 최적 조건들은 일치합니다.
Duality Theorem : 만약 선형 계획법에 제한된(bounded) 최적이 있다면, 이는 쌍대에도 마찬가지이며 두 최적 값들은 일치한다.
원 문제가 max-flow 문제를 표현하는 LP였을 때, minimum-cut 문제로 나타내는 쌍대 변수에 대한 해석을 사용하는 것이 가능합니다. flows와 cuts의 관계는 쌍대성 이론의 특정 사례일 뿐입니다. 그리고 사실상, 이 정의의 증명은 max-flow min-cut theorem이 max-flow 알고리즘에서 판명되는 것과 같은 방식으로 심플렉스 알고리즘의 증명에서 판명됩니다.
Zero-sum games
행렬 게임(matrix game)을 통해 삶에서 충돌하는 여러 상황을 표현할 수 있습니다. 예를 들면, 학교 운동장에서 하는 가위-바위-보 게임은 여기서 설명하는 payoff matrix(보수 행렬)에 의해 설명될 수 있습니다. 행(row)과 열(column)이라고 불리는 두 명의 선수가 있고, 그들은 각각 {r, p, s}로부터 움직임(move)를 선택합니다. 이들은 움직임들에 해당하는 행렬 항목을 찾고, 열이 행에게 이 양을 지불합니다. 이는 행의 이득(Row's gain)이고 열의 손실(Column's loss) 입니다.
그들 중 두 명이 이 게임을 반복적으로 한다고 가정해봅시다. 만약 행이 항상 같은 움직임을 선택한다면 열은 빨리 이를 알아내고 항반 반대 움직임을 선택해 매번 이길 수 있습니다. 따라서 행은 선택할 움직임을 섞어야 합니다. 즉, 확률 \(x_1\)을 갖는 r과 확률 \(x_2\)를 갖는 p, 그리고 확률 \(x_3\)을 갖는 s를 각 차례에서 수행하는 mixed strategy를 가지도록 하여 설계할 수 있습니다. 이 전략은 모두 양수인 벡터 \(\mathbf{x} = (x_1, x_2, x_3)\)에 의해 지정되고, 벡터는 모두 더하면 1이 됩니다. 비슷하게 열의 mixed strategy는 어떤 벡터 \(\mathbf{y} = (y_1, y_2, y_3)\) 입니다.
게임의 어떤 한 라운드에서, 행과 열은 각각 i번째와 j번째 움직임을 수행하는 기회 \(x_i y_j\)가 있습니다. 그리하여 기대되는(평균) 보수는 다음과 같습니다.
행은 이를 최대화하길 바라고, 반면 열은 이것을 최소화하기를 바랍니다. 가위-바위-보에서 이들이 성취하길 원하는 보수는 무엇일까요?
이제, 행이 '완전 무작위' 전략 \(\mathbf{x} = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})\)을 수행하는 예시를 살펴보겠습니다. 만약 열이 r을 수행한다면 그때 평균(기대) 보수는 다음과 같습니다.
이는 또한 열이 p와 s를 수행한다면 true입니다. 그리고 어떤 mixed strategy (\(y_1, y_2, y_3\))의 수익은 r, p 그리고 s를 수행하기 위한 가중된 개별적인 보수의 평균이기 때문에 이는 0이 되어야 합니다. 이는 위에서 살펴본 공식에 의해 아래처럼 됩니다.
그리고 마지막에서 두 번째 항등식에서 G의 모든 열을 더하면 0이 된다는 것을 확인할 수 있습니다. 따라서, '완전 무작위' 전략을 수행함으로써, 열이 무엇을 하더라도 행은 0의 기대 보수를 만들 수 있습니다. 이는 열이 음의 기대 보수를 바랄 수 없다는 것을 의미합니다(열은 가능한 작은 수익을 원함). 그러나 대칭적으로 만약 열이 '완전 무작위' 전략을 수행한다면, 열은 또한 0의 기대 보수를 만들고 그리하여 행은 기대 보수를 바랄 수 없습니다. 정리하면, 최고의 각 선수가 할 수 있는 것은 0의 기대 보수를 갖는 '완전 무작위'로 게임을 하는 것입니다.
그럼 다음의 두 가지 시나리오를 고려하여 비슷한 다른 방법에 대해 생각해보겠습니다.
첫 번째 행은 자신의 전략을 발표하고, 열은 그의 전략을 가져온다.
첫 번째 열은 자신의 전략을 발표하고, 그때 행은 열의 전략을 선택한다.
참가자들이 최적으로 게임을 한다면 평균 보수는 서로의 경우에서 0이 된다는 것을 봤습니다. 하지만 이는 가위-바위-보에서의 높은 대칭성 때문에 나타납니다. 일반적인 게임에서는 열은 행의 전략을 알고, 선택하는 동안 행의 전략을 이용하기 때문에 열은 첫 번째 전략을 선호할 것으로 예상합니다. 마찬가지로 행은 두 번째 옵션을 선호할 것이라고 예상합니다. 하지만 이는 사실이 아닙니다. 만약 둘다 최적으로 게임을 한다며나, 그때 미리 자신의 전략을 발표해도 문제가 되지 않습니다. 게다가 이 놀라운 속성은 선형계획법의 쌍대 정리의 결과입니다.
비대칭적인 게임에서 이 문제를 더 살펴봅시다. 사무실에 두 명의 후보(행과 열)가 있는 대표 선출 시나리오를 상상해보겠습니다. 그리고 그들의 각 움직임은 그들이 초점을 맞추는 공약 주제(economy, society, morality, tax cut)에 대응된다고 가정합니다. 여기서 보수(payoff)는 열(Column)에 의해 잃은 수백만의 표 입니다.
행은 자신이 mixed strategy \(\mathbf{x} = (\frac{1}{2}, \frac{1}{2})\)를 사용한다고 발표했다고 가정해봅시다. 그렇다면 열이 할 수 있는 것은 무엇일까요? m에는 \(\frac{1}{2}\)의 기대 손실이 발생할 것입니다. 반면에 t는 0의 기대 손설이 발생합니다. 그러므로, 행의 최선의 대응은 pure strategy \(\mathbf{y} = (0, 1)\) 입니다.
더 일반적으로, 행의 전략 \(\mathbf{x} = (x_1, x_2)\)가 고정되면, 열에 대해 최적인 pure strategy는 항상 존재합니다. 즉, 보수가 \(3x_1 - 2x_2\)를 갖는 움직임 m과 \(-x_1 + x_2\)의 보수를 갖는 움직임 t, 어느 쪽을 선택해도 더 적습니다. 결국 모든 mixed strategy 전략 \(\mathbf{y}\)는 이 두 가지 pure strategy의 가중 평균이므로 둘 중(m이나 t) 더 나은 전략을 이길 수 없습니다.
그러므로, 만약 행이 열이 행동하기 전에 \(\mathbf{x}\)를 알리도록 한다면, 행은 열의 가장 좋은 대응인 min{\(3x_1 - 2x_2, -x_1 + x_2\)}의 기대 보수를 성취한다는 것을 알게 됩니다. 이 최선의 대응에 대한 행의 보수를 최대화하려면 행은 방어적으로 x를 다음과 같이 선택해야 합니다.
이러한 \(x_i\)들에 대한 선택은 행에게 예상되는 결과에 대한 최상의 보수를 제공합니다. 그리고 이제 우리는 LP를 통해 이를 찾을 수 있다는 것을 확인할 수 있습니다. 주요 트릭은 고정된 \(x_1, x_2\)에 대해 아래의 식이 같다는 것을 인지하는 것입니다.
그리고 행은 이 z를 최소화하는 \(x_1, x_2\)를 선택할 필요가 있습니다.
이와 대칭으로 만약 열이 그의 전략을 먼저 알려야 한다면, 그의 최선의 베팅은 행의 최선의 대응 하에 손실을 최소화하는 mixed strategy \(\mathbf{y}\)를 선택하는 것입니다. 다시 말해, 다음와 같습니다.
LP 형태를 이를 표현하면 다음과 같습니다.
여기서 중요한 관찰은 이들 두 LP들은 서로에게 쌍대라는 것입니다. 따라서, 이들은 V라고 부르는 동일한 최적값들을 가집니다.
요약하면, LP를 풀기 위해서, 행(최대화하려는 사람)은 열이 무엇을 하더라도 적어도 V의 기대 결과를 보장하는 전략을 선택할 수 있습니다. 그리고 쌍대 LP를 풀기 위하여, 열(최소화하려는 사람)은 행이 무엇을 하더라도 많아야 V의 기대 결과를 보장할 수 있습니다. 이는 선험적으로 이러한 플레이가 존재하는지조차 확실하지 않은 유일하게 정의된 최적의 플레이입니다. V는 게임의 값으로서 알려져 있습니다. 이 예에서는 \(\frac{1}{7}\)이고, 행의 최적의 mixed 전략은 (\(\frac{3}{7}, \frac{4}{7}\))을 수행하고 열은 최적의 mixed 전략 (\(\frac{2}{7}, \frac{5}{7}\))을 수행합니다.
이 예제는 임의의 게임을 쉽게 일반화했고, 두 선수들에 대한 최적이 되는 mixed strategy의 존재를 보여줍니다. 그리고 mixed strategy가 동일한 값, 즉, min-max theorem이라 부르는 게임 이론(game theory)의 기초적인 결과를 얻었습니다. 이는 다음과 같이 항등식으로 쓸 수도 있습니다.
이는 행이 자신의 전략을 먼저 알려야 하는 좌변의 식이 아마 열이 먼저 전략을 알려야 하는 우변의 식보다 열에게 더 좋게 될 것이기 때문에 이는 놀랍습니다. 쌍대 정리는 maximum flows와 minimum cuts에서 했던 것처럼 둘을 같게 합니다.
Simplex Algorithms
심플렉스 알고리즘의 역할은 선형계획법을 효율적으로 푸는 것입니다.
높은 수준에서, 심플렉스 알고리즘은 일련의 선형 부등식과 선형 목적 함수를 갖고 다음의 전략에 의해 최적의 가능한 포인트를 찾습니다.
첫 번째 포스팅에서의 2D와 3D 예제들에서, 이는 시각화하기 쉽고 직관적으로 이해하기 쉽습니다. 그러나 n개의 변수 \(x_1, \cdots, x_n\)들이 있다면 어떨까요?
\(x_i\) 모든 세팅들은 실수(real number)들의 n-tuple로 표현되고 n차원 공간에 표현될 수 있습니다. \(x_i\)를 포함하는 선형 방정식은 동일한 공간(space) \(\mathbb{R}^n\)에서 초평면(hyperplane)을 정의하고 대응되는 부등식은 half-space를 정의하는데, 모든 포인트는 초평면에 정확히 있거나 특정 측면에 있습니다. 마지막으로 선형계획법의 feasible region은 일련의 부등식들로 지정되므로 해당되는 half-space들의 교차점인 볼록 다면체(convex polyhedron)입니다.
그러나 일반적인 맥락에서 정점(vertex)와 이웃(neighbor)의 개념은 무엇을 의미할까요?
Vertices and neighbors in n-dimensional space
위의 그림은 첫 번째 포스팅에서의 3D 예제(상품 A, B, C)의 LP를 나타낸 것입니다. 이 그림을 면밀히 살펴보면, 각 정점이 초평면들의 어떤 부분집합과 만나는 곳에서의 유일한 점이라는 것을 볼 수 있습니다. 예를 들어, 정점 A는 제약 2, 3, 7이 항등식에서 만족되는 단일 점(point)입니다. 다시 말하면, 부등식 4, 6에 대응되는 초평면들을 정점을 정의하지 않는데, 이는 그들의 교차점이 단일 점이 아닌 선이기 때문입니다.
이 정의를 자세하게 표현하면 다음과 같습니다.
부등식들의 부분집합을 선택한다. 만약 항등식을 사용하여 이들을 만족하는 유일한 점이 적합하다면, 그때 이것은 정점(vertex)이다.
유일한 점을 식별하기 위해 얼마나 많은 식들을 필요로 할까요? n개의 변수가 있을 때, 만약 유일한 해답을 원한다면 적어도 n개의 선형 항등식이 필요합니다. 다시 말해, n개의 항등식보다 많이 갖고 있는 것은 불필요합니다. 적어도 이들 중 하나는 다른 것들의 선형 조합으로 표현될 수 있고, 따라서 무시할 수 있습니다. 정리하면 다음과 같습니다.
각 정점은 n개의 부등식들의 집합에 의해 지정된다. (동일한 정점이 다른 부등식들의 부분집합에 의해서 만들어지는 것이 가능합니다. 이 예에서 정점 B는 2,3,4에 의해서 만들어질 수 있고 또한 2,4,5에 의해서도 만들어질 수 있습니다. 이와 같은 정점들을 퇴화(degenerate)한다고 하며 특별하게 고려되어야 합니다. 여기서는 이와 같은 것은 존재하지 않는다고 가정합니다)
자연스럽게 이웃(neighbor)은 다음과 같이 정의됩니다.
만약 두 개의 정점이 동일한 n-1개의 정의된 부등식을 가진다면 이 정점은 이웃들(neighbors)이다.
예를 들어, 위 그림에서 A와 C 정점은 두 개의 정의된 부등식 3, 7을 공유합니다. 따라서 이 정점들은 서로 이웃입니다.
The Algorithm
각 반복에서 심플렉스는 아래의 2개의 작업을 수행합니다.
현재 정점이 최적인지 검사한다. 만약 최적이라면 반복을 중단한다.
다음으로 이동할 곳을 결정한다.
만약 정점이 원점에 있다면, 이 두 작업들은 쉽게 해결됩니다. 그리고 만약 정점이 다른 곳에 있다면 좌표계를 변환하여 이를 원점으로 이동시킵니다.
먼저 왜 원점이 편리한지 살펴보겠습니다. 만약 다음과 같은 일반적인 LP가 있다고 가정해보겠습니다.
여기서, \(\mathbf{x}\)는 변수들의 벡터 \(\mathbf{x} = (x_1, \cdots, x_n)\) 입니다. 그리고 원점이 feasible하다고 가정합니다. 이때 n개의 부등식 {\(x_1 \geq 0, \cdots, x_n \geq 0\)}에 의해 원점은 확실한 정점이 됩니다. 이제 심플렉스의 두 가지 작업을 풀어보겠습니다.
Task 1: 원점이 최적이 되는 필요충분 조건은 모든 \(c_i \leq 0\)이다.
만약 모든 \(c_i \leq 0\)이라면, 그때 제약들 \(x \geq 0\)을 고려하여 더 나은 목적값(objective value)를 기대할 수 없습니다. 결과적으로, 만약 어떤 \(c_i > 0\)이라면, 그때 원점은 최적이 되지 않습니다. 그 이유는 \(x_i\)가 증가함으로써 목적 함수를 증가시킬 수 있기 때문입니다.
그러므로 Task 2에 대해, \(c_i > 0\)에 대한 어떤 \(x_i\)를 증가시킴으로써 이동할 수 있습니다. 그렇다면 얼마나 이동시켜야 할까요? 이는 다른 제약에 도달할 때까지 입니다. 즉, 타이트한 제약인 \(x_i \geq 0\)을 해제(느슨하게)하고 이전에 느슨했던 제약이 타이트해질 때까지 \(x_i\)를 증가시킵니다. 그 점(point)에서 이제 다시 정확하게 우리는 n개의 타이트한 부등식을 가지게 되며, 그래서 새로운 정점에 있게 됩니다.
예를 들어, 다음의 선형계획법을 처리한다고 가정해봅시다.
심플렉스는 제약 4, 5에 의해서 지정된 원점에서 시작될 수 있습니다. 이동하기 위해, 타이트한 제약인 \(x_2 \geq 0\)을 해제합니다. 이제 \(x_2\)가 점점 증가되면서, 첫 번째 제약은 이제 \(-x_1 + x_2 \leq 3\)이 되고, 그러므로 이 부등식이 타이트해지는 점인 \(x_2 = 3\)에서 멈추어야 합니다. 따라서 새로운 정점은 제약 3, 4에 의해서 주어집니다.
만약 우리가 원점에 있다면 무엇을 해야할 지 알게 됩니다. 그러나 현재 정점 \(u\)가 다른 곳에 있다면 어떻게 될까요? 이를 해결하는 방법은 일반적인 \(x_1, \cdots, x_n\)에서 'local view(국부적 관점)'으로 좌표계를 이동함으로써 u를 원점으로 변환하는 것입니다. 이 지역 좌표들은 u를 정의하고 둘러싸는 n개의 초평면(부등식)에 대한 적절하게 스케일링된 거리 \(y_1, \cdots, y_n\)으로 구성됩니다.
구체적으로, 만약 둘러싸는 부등식 중 하나가 \(\mathbf{a}_i \cdot \mathbf{x} \leq b_i\)라면, 그때 \(\mathbf{x}\) 점으로부터 특정 벽(wall)까지의 거리는 다음과 같습니다.
\[y_i = b_i - \mathbf{a}_i \cdot \mathbf{x}\]
이 유형은 n개의 방정식은 벽마다 하나씩 \(y_i\)를 \(x_i\)의 선형 함수로 정의하며, 이 관계는 \(x_i\)를 \(y_i\)의 선형 함수로 표현하기 위해 반전될 수 있습니다. 따라서 전체 LP를 y들에 대해 다시 작성할 수 있습니다. 이렇게 하면 기본적인 것들(실제로 최적값은 동일하게 유지됨)은 변경되지 않으면서 다른 좌표 프레임으로 표현됩니다. 이렇게 개선된 'local' LP는 다음의 세 가지 특성을 갖습니다.
단순히 \(\mathbf{u}\)를 정의하는 부등식의 변환된 버전인 부등식 \(\mathbf{y} \geq 0\)을 포함한다.
\(\mathbf{u}\) 자체는 \(\mathbf{y}\)-space에서 원점이다.
비용 함수(cost function)은 \(\text{max }c_{\mathbf{u}} + \tilde{\mathbf{c}}^T\mathbf{y}\)가 된다. 여기서 \(c_{\mathbf{u}}\)는 \(\mathbf{u}\)에서 목적 함수의 값이며, \(\tilde{\mathbf{c}}\)는 변환된 비용 벡터(cost vector)이다.
요약하자면, 우리가 어떻게 해결해야 하는지 알고 있는 상황으로 되돌아가는 것입니다. 아래 그림은 앞서 본 예제에서 이 알고리즘을 사용하는 실제 예를 보여줍니다.
Simplex in action
이렇게 심플렉스 알고리즘은 정의됩니다. 정점으로부터 이웃된 정점까지 이동하고 목적 함수가 local에서 최적이었을 때 멈춥니다. 즉, local cost vector의 좌표가 모두 0이거나 음수일 때 멈춥니다. 방금 살펴본 것처럼, 이 특성을 갖는 정점은 전역에서 또한 최적이 되어야 합니다. 반면에, 만약 현재 정점이 국부적(locally)으로 최적이 아니라면, 그때 local 좌표계는 목적 함수를 개선할 수 있는 일부 차원을 포함합니다. 따라서 이웃 정점에 도달할 때까지 다면체의 간선을 따라 이동합니다. nondegeneracy(비퇴화)라고 가정하면, 이 간선은 0이 아닌 길이를 가지며, 그래서 목적값은 개선됩니다.
Loose ends
심플렉스 알고리즘에는 아직 언급하지 않은 몇 가지 중요한 이슈들이 있습니다.
The starting vertex
심플렉스에서 시작 정점은 어떻게 찾을 수 있을까요?
2D와 3D 예제에서는 원점에서 항상 시작했는데, 이는 선형계획법이 우연히 양의 우변을 가진 부등식을 가지고 있었기 때문에 효과가 있었습니다. 일반적인 LP에서는 항상 운이 좋지는 않습니다. 그러나, 시작 정점을 찾는 것은 LP로 치환(reduced)될 수 있고 심플렉스로 해결할 수 있다는 것이 밝혀졌습니다.
이것이 어떻게 수행되는지 살펴보기 위해, 어떤 선형계획법을 표준 형태로 시작해보겠습니다. 여기서 우리는 LP들이 항상 이 방법으로 다시 작성될 수 있다는 것을 알고 있습니다.
첫 번째로 항등식들의 우변이 모두 non-negative라는 것을 확신합니다. 만약 \(b_i < 0\)이라면, i번째 항등식의 양쪽에 -1을 곱합니다.
그러면 다음과 같은 새로운 LP를 만듭니다.
m개의 새로운 인위적인 변수 \(z_1, \cdots, z_m \geq 0\)을 만든다. 여기서 m은 항등식의 수이다.
i번째 항등식의 좌변에 \(z_i\)를 더한다.
최소화하기 위해 objective는 \(z_1 + z_2 + \cdots + z_m\)이 된다.
이 새로운 LP에 대해, 시작 정점, 즉 모든 i에 대해 \(z_i = b_i\)이고 다른 모든 변수는 0인 정점을 찾는 것은 쉽습니다. 따라서 우리는 최적해를 얻기 위해 심플렉스를 사용하여 풀 수 있습니다.
여기에는 두 가지 케이스가 있습니다. 먄약 \(z_1 + \cdots + z_m\)의 최적해가 0이라면, 그때 심플렉스로부터 얻을 수 있는 모든 \(z_i\)는 0입니다. 따라서, 새로운 LP의 최적 정점에서 우리는 \(z_i\)의 값을 무시함으로써 원래의 LP의 시작 정점을 얻습니다. 그러면 심플렉스를 시작할 수 있습니다.
그러나 최적의 목적이 positive가 되도록 바꾸면 어떻까요? 한 번 생각해봅시다.
우리는 \(z_i\)의 합을 최소화화려고 시도했지만, 심플렉스는 0이 될 수 없다고 결정했습니다. 그러나 이는 원래의 선형계획법이 불가능하다는 것을 의미합니다. 이것이 가능해지려면 0이 아닌 \(z_i\)들이 필요합니다. 이것이 심플렉스가 LP가 infeasible하다고 발견하고 보고하는 방법입니다.
Degeneracy (퇴화)
위 그림의 다면체에서 정점 B는 degenerate(퇴화)입니다. 기하학적으로 이는 n = 3개 이상의 다면체의 면의 교집합이라는 것을 의미합니다(B의 경우에는 2,3,4,5의 교집합이 됩니다). 대수적으로(algebraically), 3개의 부등식으로 구성된 4개의 조합({2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}) 중 하나를 선택하고, 3개의 미지수를 3개의 선형 방정식의 대응되는 시스템을 푼다면 4개의 조합들에서 모두 동일한 답 (0, 300, 100)을 얻을 수 있습니다. 이것은 심각한 문제입니다. 이는 정점의 모든 이웃들이 해당 정점과 동일하고 더 이상 더 나은 목표가 없기 때문에 심플렉스가 단순히 차선의 퇴화 정점(degenerate vertex)을 반환할 수 있습니다. 그리고 만약 우리가 심플렉스를 수정해서 퇴화(degeneracy)를 감지하고 어떠한 개선없이 정점에서 정점으로 계속 점프한다면, 이는 영원히 반복하게 됩니다.
이 문제를 해결하는 한 가지 방법은 perturbation(섭동론)을 사용하는 것입니다. 즉, 각 \(b_i\)를 \(b_i \pm \epsilon_i\)로 아주 작은 임의의 양으로 변경하는 것입니다. \(\epsilon_i\)들은 작기 때문에 LP의 본질은 변하지 않지만, 선형 시스템의 해답들 사이에 미분의 효과가 있습니다.
Unboundedness
경우에 따라서는 LP의 목적 함수를 임의로 크게(최소화 문제라면 작게) 만들 수 있기 때문에 LP가 unbounded한 경우도 있습니다. 만약 이런 경우라면, 심플렉스는 정점의 이웃을 탐색할 때 부등식을 제거하고 다른 것을 더하는 것은 무한대의 해를 갖는 비결정적인 항등식 시스템으로 유도한다는 것을 알아차립니다. 그리고 실제로 해답들의 공간은 목표가 점점 더 커질 수 있는 전체 선을 포함하고 있습니다. 이러한 경우에, 심플렉스는 중단되고 불평(complains...) 합니다.
The running time of simplex
아래의 일반적인 선형 계획법에 대한 실행 시간은 어떻게 될까요?
여기서 n개의 변수들이 있으며, \(\mathbf{A}\)는 n개의 부등식 제약을 포함합니다. 이는 정점에서 정점으로 진행되는 반복 알고리즘이므로, 단일 반복에 걸리는 시간을 계산하는 것부터 시작해보겠습니다.
현재 정점이 \(\mathbf{u}\)라고 가정해보겠습니다. 정의에 의해서, 이는 항등식을 만족하는 n개의 부등식 제약들에서 유일한 점입니다. 이 정점의 이웃들은 이 부등식들 중 n-1개를 공유하기 때문에, 최대 \(n \cdot m\)개의 이웃들을 가집니다.
반복을 수행하기 위한 단순한 방법은 잠재적인 이웃을 확인하여 이것이 정말로 다면체의 정점인지 확인하고 비용(cost)을 결정하는 것입니다. 비용을 찾는 것은 한 번의 내적(dot product)이면 되기 때문에 빠르지만, 이것이 진짜 정점인지 확인하는 것은 n개의 미지수들의 n개의 방정식들의 시스템을 푸는 것을 포함하고, 그 결과가 feasible한 지 검사합니다. 가우스 소거법(gaussian elimination)을 통해 이 작업은 \(O(n^3)\)의 시간이 걸리면, 반복당 \(O(mn^4)\)의 실행 시간을 제공합니다.
gaussian elimination 대수적 정의 하에서, 단지 정점의 좌표를 작성하는 것은 선형 항등식들의 시스템을 푸는 것을 의미합니다. 어떻게 이를 수행하는 것일까요? n개의 미지수를 갖는 n개의 선형 항등식의 시스템이 아래처럼 주어졌을 때를 살펴보겠습니다. 여기서 n = 4 입니다.
이 같은 시스템을 풀기 위한 기본적인 방법(고등학교 수준)은 다음의 규칙을 반복적으로 적용하는 것입니다: 만약 한 항등식의 배수를 다른 항등식에 더하면, 항등식들의 전체 시스템은 동일하게 유지된다. 예를 들어, 첫 번째 항등식에 -1을 곱하고 세 번째 항등식에 더하면, 다음과 같은 동일한 시스템을 얻을 수 있습니다.
이러한 변환은 세 번째 항등식에서 변수 \(x_1\)을 제거하여, \(x_1\)을 포함하는 항등식 하나만 남깁니다. 다시 말해서, 우리는 첫 번째 방정식을 무시하고 3개의 미지수를 갖는 3개의 항등식의 시스템을 갖게 됩니다. 즉, n을 하나 줄였습니다. 그러면 우리는 축소된 시스템을 풀어 \(x_2, x_3, x_4\)를 얻을 수 있고, 이를 첫 번째 방정식과 연결해서 \(x_1\)을 얻을 수 있습니다.
가우스에 의해서 아래의 알고리즘이 제안됩니다. 가우스 소거법은 n에서 n-1로 문제의 크기를 줄이기 위해 \(O(n^2)\)의 산술 연산을 사용합니다. 그리하여 전체 \(O(n^3)\)의 연산을 사용합니다. 이 또한 총 러닝 타임에 대해 좋은 추정치라는 것을 보여주기 위해, 우리는 관련된 수들이 다항식적으로 한정되어 있다는 논쟁이 필요합니다. 예를 들면, 솔루션 (\(x_1, \cdots, x_n\))은 원래의 계수 \(a_{ij}\)와 \(b_{i}\)보다 더 높은 정밀도를 요구하지 않습니다. (...? 무슨 의미인지는 잘 모르겠습니다 ㅠㅠ)
다행히, 더 좋은 방법들이 많이 있고, \(mn^4\)라는 factor는 심플렉스를 더 실용적인 알고리즘으로 만들어 \(mn\)으로 향상시킬 수 있습니다. 현재 로컬 좌표를 기준으로 LP를 다시 작성하는 작업은 반복당 \(O((m+n)n)\)에 불과하며, 이는 국부적 관점(local view)은 단지 정의된 부등식들 중 하나에서 반복 간에 약간만 변경된다는 것을 보여줍니다.
다음으로 최적의 이웃을 선택하기 위해, 목적 함수는 "\(\text{max } c_{\mathbf{u}} + \tilde{\mathbf{c}} \cdot \mathbf{y}\)"의 형태입니다. 여기서 \(c_{\mathbf{u}}\)는 \(\mathbf{u}\)에서 목적 함수의 값입니다. 이는 이동할 만한 방향을 즉시 식별합니다. 여기서는 \(\tilde{c}_i > 0\)을 선택하는데, 만약 이것이 없다면 현재 정점이 최적이 되고 심플렉스는 중단됩니다. 나머지 LP는 이제 \(\mathbf{y}\) 좌표로 다시 작성되었기 때문에, 어떤 다른 부등식이 위배되기 전에 \(y_i\)가 얼마만큼 증가할 수 있는지는 쉽게 결정할 수 있습니다. (만약 \(y_i\)를 무한히 증가시킬 수 있다면, 이는 LP가 unbounded하다는 것을 알 수 있습니다)
따라서 심플렉스의 각 반복당 실행 시간은 O(mn) 입니다. 하지만 얼마나 많은 반복이 있을 수 있을까요? 물론 정점들의 수의 상한인 \(\begin{pmatrix} m+n \\ n \end{pmatrix}\)보다 더 많이 반복될 수는 없습니다. 그러나 이 상한은 n에 대한 지수로 표현되고, 지수적인 수의 반복이 걸리는 실제 LP 예제들이 존재합니다. 다시 말해서, 심플렉스는 지수 시간 알고리즘(exponential-time algorithm)입니다. 그러나 이 같은 지수적인 예제들은 현실에서 발생하지 않으며, 이러한 사실 때문에 심플렉스가 매우 가치있고 널리 사용됩니다.
댓글