Linear Problem 선형 계획법

 

Linear Problem의 정의는 다음과 같다.

1. Optimizing Objective Function
2. Linear Constraints

수식(canonical form)으로 나타내면

$$\begin{align}
\min_{x} & \; c^T x \\
\text{subject to} \quad & Ax = b \quad (Equality Constraints)\\
& Gx \leq h \quad (Inequality Constraints)
\end{align}$$

이다. 여기서 $\mathbf{c}, \mathbf{x} \in \mathfrak{m}_{n, 1} (\mathbb{F} )$ 이고, equality constraint matrix와 inequality constraint matrix는 각각 $A ∈ \mathfrak{m}_{m, n} (\mathbb{F}), G ∈ \mathfrak{m}_{r, n} (\mathbb{F})$, 우변 벡터는 $b \in \mathfrak{m}_{m, 1} (\mathbb{F}), h \in \mathfrak{m}_{r, 1} (\mathbb{F})$ 가 된다.

 이 문제를 푸는 방법을 알기 위한 관련 개념들을 살펴보자. Linear Problem 에서 그러면 나올 수 있는 solution 의 형태가 어떤 것이 있을지 예측할 수 있다.

• Unbounded
• Infinite Solution
• Only One Solution
• None Solution

 

Fundamental Theorem of Linear Programming

 최적화 문제에서 다면체 Ax ≤ b가 나타내는 feasible region 위의 extreme point 에서 "min z" 가 되게 하는 최적의 solution 이 무조건 extreme point 중에 존재함을 보이자(이때 다면체 bounded polyhedron 은 convex 하다). 위키를 참고했다.

 x* ∈ int(P), 즉 feasible region의 internal에 있다고 가정한다면, x*을 중심으로 하는 반지름 ϵ > 0 인 B_ϵ (x*) 가 존재하며, 이 순서쌍의 집합은 feasible region P에 포함된다(B* = B_ϵ(x*) ⊂ P). 여기서 B* 안의 특정 점 $x^* - \frac{ϵ}{2} \frac{c}{||c||}$ 을 생각할 수 있으며 이 또한 feasible region 안에 있다. 이때,

$$c^T (x^* - \frac{\epsilon}{2} \frac{c}{||c||}) = c^T x^* - \frac{\epsilon }{2} \frac{c^T c}{||c||} = c^T x^* - \frac{\epsilon}{2} ||c|| < c^T x^* $$

이다. 따라서 결과적으로 z라는 목표치는 내부점에 있을때, c^T x^* 라는 점은 B* 안의 적당한 점을 잡아서 그보다 더 optimizing하게 만들 수 있다는 뜻이다. 귀류법에 의해 optima는 항상 경계에 있어야 함을 이제 알 수 있다.

 이제 x*라는 것은 경계 위에 있다. 이제 경계 위에서 extreme point에 될 수 밖에 없음을 보이자. x* 라는 것은 경계 위에 있기 때문에 extreme points의 linear combination으로 표현 될 것이다. 따라서 다음과 같이 식을 세울 수 있다(x_i 는 x*와 맞닿아 있는 hyperplane의 모든 vertex(extreme point)).

$$x^*= \sum_{i=1}^t \lambda_i x_i$$

이때 sum lambda는 1이 되어야 할 터이다. 어떤 극점들 사이의 공간을 표현하는 hyperplane은 vertex의 선형결합으로 표현되기 때문, 이제 이 optima point 를 나타내는 x*와 경계선 위의 점과 그 경계선을 extreme points 을 나타내는 점 x_i 들 간의 차이를 보자.

$$0 = c^T ((\sum_{i=1}^t \lambda_i x_i ) - x^* ) = c^T ( \sum_{i=1}^t \lambda_i (x_i - x^* ) ) = \sum_{i=1}^t \lambda_i (c^T x_i - c^T x^* )$$

 이것이 의미하는 바는 optima가 속해 있는 hyperplane에 대한 extreme point를 solution으로 잡을 때 항상 그 z-score 가 optima 일 때의 z-score와 동일하다는 의미이다. 따라서 "우리는 경계면이 아닌 경계점만 보면 된다." feasible region 위의 extreme point 에서 min z 가 되게 하는 최적의 solution 이 무조건 extreme point 중에 존재함을 보이게 된 것이다.

 

Solution

Simplex Algorithm, 단체법

 우선 조건들을 행렬 형태로 변환하여 계산을 편리하게 하는 방법이다.

 

Simplex Table, Simplex Matrix

𝑥_1	𝑥_2	𝑥_3	...	𝑥_𝑛	slack variable	Right Hand Side, RHS
a_11	a_12	a_13	...	a_1n	s_1	𝑏_1
a_21	a_22	a_23	...	a_2n	s_2	𝑏_2
a_31	a_32	a_33	...	a_3n	s_3	𝑏_3
...	...	...	...	...	...	...
a_m1	a_m2	a_m3	...	a_mn	s_m	𝑏_m
c_1	c_2	c_3	...	c_m		z

위와 같이 정리할 수 있는데, 여기서 slack variable은 부등식에 대한 간격을 매워주는 역할을 한다. 만약 x+y 〈= 10 이고 실제로 x+y가 10이 아니라 더 적은 값인 8 이라고 쳤을 때, 그 간격 2를 매워주게 된다. 이때 slack variable 또한 0 이상이어야 한다.

 따라서 Ax ≤ b 에서 A (x, s) = b 의 테크닉을 쓸 것이다. 또한 z라는 것은 c^T x 과 동일한 값이어야 하므로 그 등식 또한 추가해준다. 그렇게 되면 linear equation system에서의 (m+1) by (n+m) 의 선형 방정식을 풀게 되는 것이다. 여기서는 non-negative constraints 때문에 일반적인 역함수를 구하는 과정이 아니라 gauss-jordan elimination을 조금 변형시켜 적용한다.

 

Algorithm

1. z-score에 영향을 가장 크게 끼치는 변수 선택
2. bias 를 해당 변수의 coefficient 로 나누어서 우변이 최소값을 가지는 행을 기준으로 하여
3. 나머지 행에 대한 elementary row operations을 실행하여 해당 변수를 0으로 만들어버린다.
4. 위를 마지막 행의 z를 제외한 각 coefficient가 음수가 될 때까지 반복

 

이를 문제에 적용시켜보자. 문제는 밑의 링크를 토대로 풀어보았다.

5.3 선형계획법 문제와 이차계획법 문제 — 데이터 사이언스 스쿨

 

Constraints

• 제품 A, B 각각 100개 이상 생산
• 제품 A, B 를 생산하는데 500시간 제공
• 제품 A, B 를 생산하는데 부품 9800개 제공
• 제품 A를 생산하는데 1시간 소요
• 제품 B를 생산하는데 2시간 소요
• 제품 A를 생산하는데 부품 4개 소요
• 제품 B를 생산하는데 부품 5개 소요
• 제품 A의 이익 3만원, B의 이익 5만원

수식으로 나타내자.

• x_A + 2x_B ≤ 500
• 4x_A + 5x_B ≤ 9800
• x_A ≥ 100
• x_B ≥ 100
• 3x_A + 5x_B = z (maximizing)

Linear Problem에 맞도록 변형시키자( y_A + 100 = x_A, y_B + 100 = x_B ).

• y_A + 2y_B + s_1 = 200
• 4y_A + 5y_B + s_2 = 8900
• -3y_A -5y_B + z = 800 (maximizing)

Binding Linear Equation System (Simplex Matrix)로 표현하자.

$$ \begin{pmatrix}
1 & 2 & 1 & 0 & 0 \\
4 & 5 & 0 & 1 & 0 \\
-3 & -5 & 0 & 0 & 1
\end{pmatrix} \cdot \begin{pmatrix} y_A & y_B & s_1 & s_2 & z \end{pmatrix}^T = \begin{pmatrix} 200 & 8900 & 800 \end{pmatrix}^T$$

가우스 요르단 소거법의 변형된 elementary row operations를 augmented matrix에 실시하면 된다.

 

Dual Simplex Method, 이중 단체법

 밑의 글을 참고하자.

Duality in General Programs · 모두를 위한 컨벡스 최적화

 앞서 봤던 문제를 primal LP(primary problem)이라고 한다. 근데 그 문제에서 조건들이 굉장히 까다로워지면 어떻게 하는가? 가령, 원문제의 조건이 수천개일때 문제가 매우 복잡할 것이다. 여기서 기존 문제에서 약간 변형시켜서 다른 문제로 만들때, 그 문제가 원문제보다 더 풀기 쉬운 형태로 있다면, 그 문제로 변환해서 풀것이다(물론 솔루션은 같다). 그럼 그 다른 문제의 조건은 어떻게 만들어지는가가 관건이다. 위의 원래 형태를 다시 가져오자.

$$\begin{align}
\min_{x} & \; c^T x \\
\text{subject to} \quad & Ax = b \quad (Equality Constraints)\\
& Gx \leq h \quad (Inequality Constraints)
\end{align}$$

 여기서 우리가 하고 싶은 것은 제한 조건이 너무 많다면 이를 줄이고자 한다는 것이다. 이때, 이 constraints 보다 쓰이는 optimization variable(decision variable)들이 더 적을 경우 이 decision variable의 개수를 제약으로 쓰겠다는 말이 된다. 그렇게 되면 제약조건의 개수가 decision variable 의 개수가 될 것이고 결론적으로 제약조건이 적어지기 때문에 문제는 간단해진다. 그래서 위 식을 다음과 같이 변형한다.

$$\begin{align}
& \begin{cases}
& Ax = b \quad (Equality Constraints) \\
& Gx \leq h \quad (Inequality Constraints)
\end{cases} \\
& ⇒ \begin{cases}
& u^T Ax = u^T b \\
& v^T Gx \leq v^T h \\
\end{cases} \\
& ⇒ (u^T A + v^T G)x \leq u^T b + v^T h \\
& ⇒ c^T x \geq - u^T b - v^T h \\
\end{align}$$

이를 말로 표현하면 제약 조건들을 합쳐서 수식적인 테크닉을 썼을 때 나오는 조건 또한 원래 조건과 동치이기에 , 이때 $c = - A^T u - G^T v$ 이면, 기존 primal 문제에 대한 lower bound를 얻게 된다. 여기서 u, v 의 크기는 제약 조건의 개수와도 맞먹으며, 다음과 같이 적을 수 있다.

$$\begin{align}
\max_{u, v} & \; -b^T u - h^T v \\
\text{subject to} \quad & -A^T u - G^T v = c \quad (Equality Constraints)\\
& v \geq 0 \quad (Inequality Constraints)
\end{align}$$

이제 저 c가 정말 저 값을 가지는지만 보이면 primal problem을 dual problem으로 바꿔서 풀 수 있을 터이다.

 

Lagrange Multiplier 를 이용한 Dual Problem

c가 -A^T - G^T v 가 되는지 보자. primal 문제에서 lagrange multiplier을 추가(u, v 말하는 것)하여

$$L(x, u, v) = c^T x + u^T (Ax - b) + v^T (Gx - h) ≤ c^T x$$

가 되고, 위의 중간 변에서 두번째 항의 값이 항상 0이고, 세번째 항은 항상 0 이하의 값을 가질 것이다.

 

 

Karush-Kuhn-Tucker Conditions, KKT 조건

 

 

Duality Theorem

 

 

Interior-Point Method, 내부점법