LP를 푸는 대표적인 방법으로 심플렉스 알고리즘이 있다.
학부 과정에서는 tableau를 이용해서 심플렉스 알고리즘으로 해를 찾는 방법을 배웠지만,
대학원 과정에서 그 원리에 대해 이론적으로 배우고 있다. 내용이 다소 복잡하지만 가볍게 정리해두고자 한다.
Simplex method
최적화를 하기 위해서는 거리와 방향을 알아야 한다.
어떤 지점에서 어떤 방향으로, 얼마나 가야 해가 더 좋아지는 지를 찾는 것이다.
심플렉스 알고리즘에서도 마찬가지다.
심플렉스 알고리즘은 BFS(Basic Feasible Solution)를 돌아다니면서 optimal을 찾는데,
하나의 BFS에서 다른 BFS로 이동할때의 거리와 방향을 알아야 한다.
Polyhedron의 꼭지점들을 돌아다니는 것이다.
어떤 feasible solution \(x\)가 있을 때, \(x\)의 주변에 해를 개선시킬 수 있는 곳을 찾는다.
만약 주변에 그런 feasible solution이 없다면, local optimal을 찾은 것이다.
local optimal은 대개 global optimal이 아니다.
하지만 문제가 Convex하다면 local optimal이 곧 global optimal이다.
LP는 Convex이기 때문에 local optimal을 찾기만 하면 된다. 기회가 된다면 Convex에 대해서도 다뤄보려고 한다.
standard form
이야기는 standard form에서부터 시작한다.
\[\eqalignno{ minimize \quad c'x &\ \\ subject \quad to \quad Ax &\ = b \\ x &\ \geq 0 \\ }\]이때, \(A\)는 full row rank \(m \times n\) matrix를 의미한다.
full row rank는 각 row가 linearly independent한 matrix를 의미한다.
direction : 어디로 보낼 것인가?
Def : \(P\) is polyhedron. Given \(x \in P, d \in R^n\) is a feasible direction at \(x\) if \(\exists \theta \gt 0\) such that \(x + \theta d \in P\)
위 정의를 이해한대로 설명해보자면, Polyhedron안에 있는 점에 대해 어떤 방향으로 조금 움직였을때 그 점이 여전히 Polyhedron안에 있다면 해당 방향으로 이동이 가능하다는 것이다.
하지만 우리는 더 좋은 방향으로 이동을 해야한다.
즉, \(Ax = b\)와 \(x \geq 0\)을 만족하고, 더 좋은 objective value를 갖는 새로운 점 \(x+\theta d\)를 찾아야 하는 것이다.
일단 점 \(x\)를 다음과 같이 이동시킨다고 생각해보자. 이때 \(B\)는 basic variable, \(N\)은 non-basic variable이다. 참고로, \(m \times n\)의 full row rank matrix이기에 m개의 basic variable이 생길테고, n-m개의 non-basic variable이 생긴다.
\[x+\theta d = \begin{pmatrix} x_B \\ x_N \end{pmatrix} + \theta \begin{pmatrix} d_B \\ d_N \end{pmatrix}\]그리고 이때 non-basic variable의 방향 중 \(d_j\)만 값이 1이고 나머지는 0이라고 하자.
위에서 말했듯이, \(Ax = b\)와 \(x \geq 0\)는 feasible한 솔루션을 위해 기본적으로 만족을 해야하는데, 특정 방향을 부여해도 이 조건은 만족해야할 것이다. 즉, \(A(x+\theta d) = b\) for \(\theta > 0\)역시 만족해야할 것이다.
하지만 이를 만족하기 위해서는 \(Ad = 0\)이어야만 한다. \(\theta\)가 0보다 크기 때문이다.
이는 다음과 같이 전개할 수 있다.
\[\eqalignno{ 0 &\ = Ad \\ &\ = \sum^n_{i=1}A_id_i \\ &\ = \sum^m_{i=1}A_{B(i)}d_{B(i)} + A_j \\ &\ = Bd_B + A_j \\ \Rightarrow d_b &\ = -B^{-1}A_j }\]이때 matrix \(A\)의 컬럼을 \(\begin{bmatrix} B, N \end{bmatrix}\)으로 구분하고 해를 \(x = (x_B, x_N)\), 방향을 \(d = (x_B, x_N)\)으로 나누었을 때,
\[d=\begin{bmatrix} -B^{-1}A_j \\ e_j \end{bmatrix}\]으로 표현이 가능하다. 이를 j-th basic direction이라 부르고, 이는 모서리를 따라 움직이게 하는 방향이다.
잠깐 정리를 좀 하자면, \(B^{-1}\)은 \(m \times n\) matrix, \(A\)는 \(n \times 1\) matrix이다. 따라서 이를 곱하면 m차원의 벡터가 된다. 그리고 \(e_j\)는 \(j\)번째만 값이 1이고 나머지는 0인 n-m차원의 벡터다. 결국 \(d\)는 n차원의 벡터가 된다.
이때, \(j\)는 n-m개 만큼 있기 때문에, basic direction 역시 n-m개가 있다.
사실 이 방향은 tableau를 통해 심플렉스를 풀때 칼럼에서 그대로 볼 수 있다.
그리고, 비음제약식에서도 \(Ax = b\)를 성립해야 하는데, non-basic variable에 대해서 이때 음의 거리만큼 움직일 시에 비음제약(non-negativity constraint)을 즉시 위반하기 때문에 음의 거리로 움직이는 것은 제외하도록 한다.
그렇기에 우리가 움직일 수 있는 방향은 non-negative한 n-m개의 basic direction들의 선형 조합이다. 그리고 심플렉스 알고리즘에서는 이 basic direction 중에서 하나의 방향을 선택한다.
추가적으로, basic direction은 extreme ray인데.. 추후에, extreme ray, cone 등에 대해 따로 알아보는 시간을 가져보겠다.
Note that if a direction satisfies \(d_B = -B^{-1}A_j \geq 0\), it is an extreme ray of recession cone of \(P\)
그럼 basic direction 중 어떤 방향을 선택할 것인가?
우리는 목적함수를 개선하는 방향을 찾고자 한다.
\[c'(x+\theta d^j) - c'x = \theta c'd^j < 0\]\(c'\)이 목적함수의 계수일 때, 어떤 방향 \(d^j\)로 \(\theta\)만큼 이동했을 때 목적함수의 변화량이 음수라면(minimize문제일 때) 그 방향으로 이동할 가치가 있는 것이다.
\(\theta\)는 음수가 아니기에, \(c'd^j\)가 음수여야 하는데, 이는 다음과 같다.
\[c'd^j = (c'_B, c'_N)\begin{bmatrix}-B^{-1}A_j \\ e_j\end{bmatrix} = c_j - c'_{B}B^{-1}A_j \equiv \bar{c_j}\]여기서 \(e_j\)는 \(j\)번째만 1이기 때문에 \(c_j\)만 남게되고, 결국 \(c_j - c'_{B}B^{-1}A_j\)형태가 되는데, 이것이 reduced cost이다.
tableau로 심플렉스를 풀때, entering variable을 찾기 위해서 목적식 계수가 담긴 가장 위 칸에서 음수(minimize문제일 경우)를 찾고, 해당 칼럼에서 특정 low를 찾았던 기억이 있을 것이다. 이때, tableau가 변화되면서 목적함수의 계수는 reduced cost로 이미 계산이 되어 있었던 것이다.
즉, non-basic variable 중에서, reduced cost를 음수로 만드는 방향으로 가는 것이 목적함수를 개선시키는 것이다.
distance : 방향이 정해졌다면, 이제 얼마나 가야하는가?
여기까지, 우리는 어떤 방향으로 갈지는 알았다. 그렇다면 얼마나 가야할까?
non-degenerate한 BFS만이 있다고 가정했을 때, \(\bar{c_j} \geq 0, \forall j \in N\)이라면 현재 솔루션이 optimal이다. 어떤 reduced cost에도 음수가 없다면 현재 솔루션이 최적인 것인데,
그렇지 않다면, 음수의 reduced cost를 가지는 \(j\)를 찾고(maximize문제일 때), \(d\)벡터(j번째 basis direction)을 찾아야 한다.
이때 우리는 얼마나 갈 것인지를 의미하는 \(\theta\)값을 찾고 싶은 것이다.
polyhedron을 벗어나지 않을만큼 적절한 거리만큼을 가야하고, 움직였을 때 목적함수는 \(\theta^{*}c'd = \theta^{*}\bar{c_j}\)만큼 바뀌게 된다.
그리고 벡터 \(d\)는 \(A(x+\theta d) = b\)와 \((x+\theta d) \geq 0\)을 만족해야 한다.
이때,
if \(d \geq 0\), then \((x+\theta d) \geq 0, \forall \theta \geq 0\). Hence \(\theta^* = \infty\)
\(d\)가 0보다 크거나 같으면, 음수가 아닌 모든 \(\theta\)에 대해서 \(x+\theta d \geq 0\)를 만족하기 때문에 세타가 무한히 증가할 수 있다.
if \(d_i \lt 0\) for some \(i\), \((x_i + \theta d_i) \leq 0 \Rightarrow \theta \leq -x_i/d_i\)
어떤 \(i\)에 대한 \(d_i\)가 0보다 작다면, \((x_i+\theta d_i) \geq 0\)이기 위해서 세타는 \(-x_i/d_i\)보다 작거나 같아야 한다.
그래서 갈 수 있는 최대한의 거리가 다음과 같이 정의된다.
\[\theta^* = \min_{\{i=1,...,m:d_B(i)\lt0\}}(-\frac{x_{B(i)}}{d_{B(i)}})\]이를 minimum ratio test라고 부르며, 심플렉스를 tableau로 풀 때 leaving variable을 찾기 위해 쓰는 것이다.
그래서 이걸 언제까지 해야되나?
Polyhedron이 있고, 모든 BFS가 non-degenerate라면, 심플렉스 알고리즘은 언젠가 끝이 나게 되어 있다.
끝나는 경우는 두가지가 있다.
- 최적의 basis를 찾고, 최적의 BFS를 찾는 경우.
reduced cost가 음수인 것이 없는 것이다. (minimize 문제일 때)
- \(Ad = 0, d \geq 0, c'd < 0\)를 만족하는 벡터 \(d\)를 찾았지만 optimal이 \(-\infty\)인 경우.
unbounded direction을 찾은 것이다. 이 경우 목적함수가 무한히 좋아지게 된다.
수업 내용을 이해한대로 정리한 것이므로, 틀린 부분이 있을 수 있습니다.
혹시 그런 부분을 발견한다면 언제든 연락주시면 감사히 배우겠습니다.