📂최적화이론

선형계획문제의 방정식 폼에서 최적해의 존재성 증명

정리 ¹

$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

행렬 $A \in \mathbb{R}^{m \times n}$ 과 $\mathbf{b} \in \mathbb{R}^{m \times 1}$ 와 $\mathbf{c} \in \mathbb{R}^{n}$ 에 대해 선형계획문제가 위와 같이 방정식 폼으로 나타난다고 하자. 만약 적어도 하나의 가용해가 존재하며, 가용해의 집합에서 $\mathbf{c}^{T} \mathbf{x}$ 가 위로 유계^{bounded Above}면 최적해가 존재한다.

---

• $\mathbf{c}^{T}$ 는 전치를 의미한다.
• 가용해란 최적화와 관계 없이 일단 제약 조건을 만족시키는 해를 말한다.

증명

전략: 이 증명은 본질적으로 최적해가 존재한다면 그 중 하나는 기저가용해다라는 정리의 증명과 같다.

기저가용해의 정의: 가용해 $\mathbf{x} \in \mathbb{R}^{n}$ 에 대해 기수가 $m$ 인 집합 $B \subseteq [n]$ 이 존재해서 $\exists A_{B}^{-1}$ 이고 $x_{j} = 0 \forall j \notin B$ 인 $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ 를 기저가용해라 한다. 이 집합 $B$ 를 기저라 부른다.

임의의 가용해 $\mathbf{x}_{0}$ 마다 $$ \mathbf{c}^{T} \mathbf{x}_{0} \le \mathbf{c}^{T} \mathbf{x} $$ 를 만족하는 $\mathbf{x}$ 들 중 성분에 $0$ 이 가장 많은 해를 $\tilde{\mathbf{x}}$ 라 하자.

• $\tilde{\mathbf{x}}$ 이 기저가용해임을 보이면 기저가용해가 유한히 많이 존재하므로 최적해의 존재성을 보일 수 있다.
• 그렇다면 어떤 최적해든 최적해이기 이전에 가용해기 때문에 최적해와 같은 목적 함수 값을 가지는 (최적)기저가용해가 존재할 것이다. 따라서 최적해 중 적어도 하나는 기저가용해다.

이제 인덱스의 집합 $$ K = \left\{ k \in [n] : \left( \tilde{\mathbf{x}} \right)_{k} > 0 \right\} $$ 을 정의했을 때 $A_{K}$ 의 열벡터들이 선형독립인지 아닌지에 따라 경우를 나누어 생각해보자.

---

Case 1. 선형독립

기저가용해의 정의에 따라 $\tilde{\mathbf{x}}$ 는 자연스럽게 기저가용해고, 더 이상 증명할 게 없다.

---

Case 2. 선형종속

선형독립이 아니라 선형종속이라면 다음을 만족시키는 어떤 $|K|$-차원 벡터 $\mathbf{v} \in \mathbb{R}^{|K|}$ 가 존재한다. $$ A_{K} \mathbf{v} = \mathbf{0} $$ 이에 대해 $\mathbf{w}_{K} = \mathbf{v}$ 와 $A \mathbf{w} = A_{K} \mathbf{v} = \mathbf{0}$ 를 만족시키게끔 확장시킨 벡터 $\mathbf{w} \in \mathbb{R}^{n}$ 을 생각해볼 수 있다. 예를 들어서 $K = \left\{ 2,3,5 \right\}$ 에 $\mathbf{v} = (-2,1,7)$ 이라면 $\mathbf{w}$ 는 $2,3,5$ 번째 성분이 $\mathbf{v}$ 와 같고 나머지가 $0$ 인 벡터 $\mathbf{w}= (0,-2,1,0,7)$ 이 되는 식이다. 이 때 $\mathbf{w}$ 는 원래 $\mathbf{v}$ 의 성분의 부호를 재조정함으로써 $$ \mathbf{c}^{T} \mathbf{w} > 0 $$ 역시 만족시킬 수 있다. 이후 언급되는 $\mathbf{w}$ 는 위 부등식을 만족하는 벡터로 생각하자.

이제 $\mathbf{w}$ 에 대해 $t \ge 0$ 에 종속된 다음의 벡터 $\mathbf{x}(t)$ 를 생각해보자. $$ \mathbf{x} (t) = \tilde{\mathbf{x}} + t \mathbf{w} $$ 일단 $\tilde{\mathbf{x}}$ 는 가용해고, $A \mathbf{w} = A_{K} \mathbf{v} = \mathbf{0}$ 를 만족시키게끔한 $\mathbf{w}$ 의 정의에 따라 모든 $t \ge 0$ 에 대해 $$ \begin{align*} A \mathbf{x} (t) =& A \tilde{\mathbf{x}} + t A \mathbf{w} \\ =& A \tilde{\mathbf{x}} \\ =& \mathbf{b} \end{align*} $$ 이다. 다시 말해, $\mathbf{x} (t)$ 역시 $\mathbf{x}(t) \ge 0$ 을 제외한 제약은 모두 만족시킨다. 한편 $\mathbf{x} (t)$ 의 $j$번째 성분 $x_{j}(t)$ 를 생각해보면 $x_{j}(t) = \tilde{x}_{j} + t w_{j}$ 과 같이 나타나고, 이들 중 적어도 하나는 $w_{j} < 0$ 여야한다. 만약 모든 $j$ 에 대해 $w_{j} > 0$ 이라면 모든 $t$ 에 대해 $\mathbf{x} (t) = \tilde{\mathbf{x}} + t \mathbf{w} \ge 0$ 이므로 모든 $\mathbf{x} (t)$ 도 가용해인데, $t \to \infty$ 일 때 $$ \mathbf{c}^{T} \mathbf{x} (t) = \mathbf{c}^{T} \tilde{\mathbf{x}} + t \mathbf{c}^{T} \mathbf{w} \to \infty $$ 이므로 목적 함수가 위로 유계라는 가정에 모순이기 때문이다. 이렇게 적어도 하나의 $w_{j_{0}}$ 가 음수라면 $t$ 를 $0$ 부터 $\infty$ 로 증가시켜감에 따라 언젠간 $$ x_{j_{0}} \left( t_{0} \right) = \tilde{x_{j_{0}}} + t_{0} w_{j_{0}} = 0 $$ 을 처음으로 만족하는 $t_{0} \ge 0$ 가 존재할 것이다. 그러면 $\mathbf{x} \left( t_{0} \right)$ 는 $\tilde{\mathbf{x}}$ 에 비해 성분으로써 $0$ 을 하나 더 가지고 있는 동시에 $$ \begin{align*} \mathbf{c}^{T} \mathbf{x} \left( t_{0} \right) =& \mathbf{c}^{T} \tilde{\mathbf{x}} + t_{0} \mathbf{c}^{T} \mathbf{w} \\ \ge & \mathbf{c}^{T} \mathbf{x}_{0} + t_{0} \mathbf{c}^{T} \mathbf{w} \\ \ge & \mathbf{c}^{T} \mathbf{x}_{0} \end{align*} $$ 도 만족한다. 이는 $\mathbf{c}^{T} \mathbf{x}_{0} \le \mathbf{c}^{T} \mathbf{x}$ 을 만족시키면서 성분 중 $0$ 이 가장 많아지도록 했던 $\tilde{\mathbf{x}}$ 의 정의에 모순이다.

---

기저가용해의 유일성: 기저가용해는 기저 $B$ 에 따라 유일하게 결정된다.

결과적으로 $A_{K}$ 는 선형종속이 될 수 없으므로 $\tilde{\mathbf{x}}$ 는 기저가용해여야만 하고, 기저의 선택에 따른 기저가용해는 유일하므로 기저가용해가 유한히 많이 존재해서 최적해도 존재한다. 모든 최적해들 역시 가용해기 때문에, 어떤 최적해에 대해서는 같은 목적 함수 값을 가지는 기저가용해가 존재하고 그들 역시 최적해기 때문에 최적해 중 적어도 하나는 기저가용해여야만 한다.

■

같이보기

선형계획법의 기본정리

이 정리는 선형계획법의 기본정리 증명에 사용된다.