선형 계획법의 기초
Scribed by Yeohyeon Lee
1. Preliminaries
1.1 Affine Sets
이 강좌에서 생각하는 벡터공간은 \(\mathbb{R}\) 위의 벡터공간 \(\mathbb{R}^{n}\)이다. 그리고 기본적인 벡터공간의 정의 등은 알고 있는 것으로 가정한다.
Definition. (Affine Set) A subset \(M\) of \(\mathbb{R}^{n}\) is called an affine set if \[ (1-\lambda)x+\lambda y\in M \] for all \(x, y\in M\) and for all \( \lambda\in\mathbb{R}\).
Example 1. 집합 \(S=\{ (a, b)\mid b-a=1\}\)는 affine set이다. \(v, w\in S\)일 때, \(v=(a, b), w=(a', b')\)으로 두면 \[ \begin{cases} b-a=1 \\[8pt] b'-a'=1 \end{cases} \] 이다. 따라서 \begin{align*} (1-\lambda)v+\lambda w & = ( (1-\lambda)a, (1-\lambda)b ) + (\lambda a', \lambda b') \\[8pt] & = ( a + (a' -a)\lambda, b+(b'-b)\lambda ) \end{align*} 이고 이때 \[ ( b+ (b'-b)\lambda) - ( a+(a'-a)\lambda) = 1\] 이므로 \((1-\lambda)v+\lambda w\in S\)이다. 즉 \(S\)는 affine set이다.
Example 2. 한 점 집합도 affine set이다. 그리고 공집합도 (재미는 없지만) affine set이다.
Theorem 1.1. The subspaces of \(\mathbb{R}^{n}\) are the affine sets which contain the origin.
Proof. Every subspace contains the origin and being closed under addition and scalar multiplication, is in particular an affine set.
Conversely, suppose \(M\) is an affine set containing the origin.
- \(\forall x\in M, \forall \lambda\in\mathbb{R},\quad (1-\lambda)0+\lambda x=0+\lambda x=\lambda x\in M\). i.e., \(M\) is closed under scalar multiplication.
- We have \[ \forall x, y\in M,\quad \left(1-\frac{1}{2}\right)x+\frac{1}{2}y=\frac{1}{2}(x+y)\in M. \] Thus \(2\left(\frac{1}{2}(x+y)\right)=1(x+y)=x+y\in M\). i.e., \(M\) is closed under addition.
Therefore \(M\) is a subspace.
Definition. An affine set \(M\) is said to be parallel to an affine set \(L\) if \(M=L+a\) for some \(a\in\mathbb{R}^{n}\).
Definition. For $M\subset \mathbb{R}^n$ and $a\in\mathbb{R}^n$, the translate of $M$ by $a$ is defined to be the set \[ M+a=\{ x+a\mid x\in M\} \]
Theorem 1.2. $\mathbb{R}^n$의 affine subset들의 모임 위의 관계 $\sim_p$를 \[ A\sim_pB\quad \Leftrightarrow\quad [ \mbox{$A=B+u$ for some $u\in\mathbb{R}^n$] } \] 으로 정의하면, $\sim_p$는 동치관계이다. 즉 $A$가 $B$와 parallel하다는 관계는 동치관계이다.
Proof.
- (Reflexive) $A$가 $\mathbb{R}^n$의 affine subset일 때, $A+0=A$이다. 즉 $A\sim_p A$이다.
- (Symmetric) $\mathbb{R}^n$의 두 affine subsets $A, B$에 대하여 $A\sim_p B$라 하자. [$B=A+v$ for some $v\in\mathbb{R}^n$]임을 보이면 된다. $A\sim_p B$의 정의에 의해 적당한 $u\in\mathbb{R}^n$에 대하여 $A=B+u$로 둘 수 있다. 이제 $B=A+(-u)$임을 보이자. $b$가 $B$의 임의의 원소라고 하면, $A=B+u$이기 때문에 $b+u$는 $A$의 원소이다. 이때 $(b+u)+(-u)=b+(u+(-u))=b+0=b$이므로 $b\in A+(-u)$이다. 즉 $B\subset A+(-u)$이다. 또한 임의의 $A$의 원소 $a$에 대하여 $A=B+u$이기 때문에 적당한 $b\in B$가 있어서 $a=b+u$로 둘 수 있고 따라서 $a+(-u)=(b+u)+(-u)=b+(u+(-u))=b+0=b\in B$이다. 즉 $A+(-u)$의 임의의 원소 $a+(-u)$는 $B$의 원소이다. 따라서 $B=A+(-u)$이고 이는 $B\sim_p A$를 뜻한다.
- (Transitive) $A, B, C$가 모두 $\mathbb{R}^n$의 affine subset이고 \( A\sim_p B\)와 \(B\sim_p C\)를 만족시킨다고 하자. 그러면 적당한 $u, v\in\mathbb{R}^n$가 있어서 \[ A=B+u,\quad B=C+v \] 로 둘 수 있다. $w=u+v$라 하고 $A=C+w$, 즉 $A\sim_p C$를 보이자. 임의의 $a\in A$에 대하여, $a=b+u$인 $b\in B$가 존재한다. 그리고 $B=C+v$이므로 $b=c+v$인 $c\in C$도 존재한다. 이때 $a=b+u=(c+v)+u=c+(v+u)=c+w\in C+w$이므로 $A\subset C+w$이다. 이제 $C$의 임의의 원소 $c$에 대하여 $c+w\in A$를 보이자. $c+w=c+(u+v)=c+(v+u)=(c+v)+u$인데, $c+v$는 $B$의 원소이므로 $(c+v)+u$는 $B+u$의 원소, 즉 $A$의 원소이다.
Theorem 1.3. Each non-empty affine set $M$ is parallel to a unique subspace $L$. This $L$ is given by \[ L=M-M=\{ x-y\mid x\in M, y\in M\}. \]
증명.
- (Existence) 적당한 $M$의 원소 $m^*$를 하나 잡고, $L=M-m^*$가 $M$과 parallel인 subspace임을 보이자. $M-m^*$가 subspace임이 보여지면, $M-M=M-m^*$인 것은 바로 얻어진다.
정리 1.1에 의해 $L=M-m^*$가 $0$을 갖는 affine set임을 보이면 충분하다. 우선 $0\in M-m^*$임은 정의에 의해 자명하다. $\forall x, y\in M-m^*$에 대하여 \[ x=m_1-m^*,\quad y=m_2-m^* \] 로 두고, $\lambda$가 임의의 실수라 하자. \begin{align*} (1-\lambda)x+\lambda y&= (1-\lambda)(m_1-m^*)+\lambda(m_2-m^*) \\[8pt] & = \left( (1-\lambda )m_1+\lambda m_2\right)-m^* \end{align*} 이고, 이때 $(1-\lambda)x+\lambda y\in M$이므로 $(1-\lambda)x+\lambda y\in M-m^*$를 얻는다. 즉 $L=M-m^*$는 $0$을 원소로 갖는 affine set이다. - (Uniqueness) $L_1$과 $L_2$가 모두 $M$과 parallel인 subspace들이라고 하자. 정리 1.2에 의해, 적당한 $a\in\mathbb{R}^n$이 있어서 $L_1=L_2+a$로 쓸 수 있다. 이때 $0\in L_1$이므로 $-a\in L_2$이고 이는 $a\in L_2$를 뜻한다. 따라서 $L_1=L_2+a\subset L_2$이 성립하고, $L_2\subset L_1$는 마찬가지 방법으로 증명할 수 있다.
Hyperplane
Affine set의 차원은 주어진 affine set과 parallel인 subspace의 차원으로 정의한다. \(\mathbb{R}^{n}\)의 \((n-1)\)-dimensional affine set을 \(\mathbb{R}^{n}\)에서의 hyperplane이라 부른다.
Remark. Hyper plane은 \(n\)차원 기하에서 한 점의 dual의 역할을 하므로 중요한 개념이다.
Definition. Given a subspace \(L\) of \(\mathbb{R}^{n}\), the set of vectors \(x\) such that [$\forall y\in L, x\perp y$], i.e. $x\perp L$, is called orthogonal complement of \(L\), and denoted $L^{\perp}$.
The orthogonal complement of \(L\) is another subspace and \[ \dim L +\dim L^{\perp}=n. \]
Theorem 1.4. Given \(\beta\in\mathbb{R}\) and a non-zero \(b\in\mathbb{R}^{n}\), the set \[ H=\{ x\mid \langle x, b\rangle=\beta \} \] is a hyperplane in $\mathbb{R}^{n}$. Moreover, every hyperplane may be represented in this way, with \(b\) and \(\beta\) unique up to a common non-zero multiple.
Proof. 집합 \(H\)가 affine set이며, \(H\)의 차원이 \((n-1)\)임을 보이면 된다. 내적의 이중선형성에 의해, 임의의 \(x_{1}, y_{1}\in H\)와 임의의 실수 \(\lambda\)에 대하여 \begin{align*} \langle (1-\lambda)x_{1}+\lambda x_{2}, b\rangle & = \langle x_{1}, b\rangle -\lambda\langle x_{1}, b\rangle +\lambda\langle x_{2}, b\rangle \\[8pt] & =\beta -\lambda\beta +\lambda\beta =\beta \end{align*} 이므로 \((1-\lambda )x_{1}+\lambda x_{2}\in H\), 즉 \(H\)는 affine set이다. 한편 \(H\)의 차원이 \(n-1\)이라는 것은, \(H\)가 subspace \(L=\{ x\mid \langle x, b\rangle = 0\}\)와 parallel이라는 것을 보이는 방식으로 쉽게 보일 수 있다.
위의 정리 1.4에서의 벡터 \(b\)를 \(H\)의 normal vector라고 부른다.
Remark. 모든 non-trivial affine set은 hyperplane들의 교집합으로 나타낼 수 있다.
Theorem 1.5. Given \(b\in\mathbb{R}^{m}\) and an \(m\times n\) real matrix \(B\), the set \(M=\{ x\in \mid Bx=b\}\) is an affine set in \(\mathbb{R}^{n}\). Moreover, every affine set may be represented in the way.
1.2 Convex Sets and Cones
Definition. A subset \(C\) of \(\mathbb{R}^{n}\) is convex if and only if \((1-\lambda)x+\lambda y\in C\) whenever $ x, y\in C$ and \( 0<\lambda <1\).
Example 1.
Theorem 2.1. The intersection of an arbitrary collection of convex sets is convex.
Proof. Let \(\{ C_{\alpha}\}\) be a collection of convex sets. And let \(x, y\in\bigcap_{\alpha}C_{\alpha}, 0<\lambda<1\). Since \((1-\lambda)x+\lambda y\in C_{\alpha}\) for all \(\alpha\), we have \((1-\lambda)x+\lambda y\in \bigcap_{\alpha}C_{\alpha}\), i.e. \(\bigcap_{\alpha}C_{\alpha}\) is convex.
Corollary 2.2. Let \(b_{i}\in\mathbb{R}^{n}, \beta_{i}\in \mathbb{R}\) for \(i\in I\), where \(I\) is an arbitrary index set. Then the set \[ C=\{ x\in\mathbb{R}^{n}\mid \forall i\in I, \langle x, b_{i}\rangle \leq \beta_{i}\} \] is convex.
Remark. Given any system of simultaneous linear inequalities and equations in \(n\) variables, the set \(C\) of solutions is a convex set in \(\mathbb{R}^{n}\). This is a significant fact both in theory and in applications.
Definition. A set which can be expressed as the intersection of finitely many closed half spaces of \(\mathbb{R}^{n}\) is called polyhedral convex set.
Polyhedral convex set은 휘어짐이 없기 때문에 비교적 다루기 쉬울 것 같다.
Definition. A vector sum \[ \lambda_{1}x_{1}+\cdots +\lambda_{m}x_{m} \] is called a convex combination of \(x_{1}, \ldots, x_{m}\) if the coefficients \(\lambda_{i}\) are all non-negative and \(\lambda_{1}+\cdots +\lambda_{m}=1\).
In many situations where convex combinations occur in applied mathematics, \(\lambda_{i}\) can be interpreted as probablilities or propertions.
Theorem 2.3. A subset of \(\mathbb{R}^{n}\) is convex if and only if contains all the convex combinations of its elements.
Proof. Actually by definition, a set \(C\) is convex if and only if \(\lambda_{1}x+\lambda_{2}x_{2}\in C\) whenever \(x_{1}, x_{2}\in C, \lambda_{1}\geq 0, \lambda_{2}\geq 0\) and \(\lambda_{1}+\lambda_{2}=1\). In other words, the convexity of \(C\) means that \(C\) is closed under taking convex combinations with two vectors. Take \(m>2\), and make the induction hypothesis that \(C\) is closed under taking all convex combinations of fewer than \(m\) vectors. Given a convex combination \[ x=\lambda_{1}x_{1}+\cdots+\lambda_{m}x_{m} \] of elements of \(C\), at least one of the scalars \(\lambda_{i}\) differs from 1; let it be \(\lambda_{1}\) for convenience. Let \[ y=\lambda_{2}'x_{2}+\cdots +\lambda_{m}'x_{m},\quad x_{i}=\frac{\lambda_{i}}{1-\lambda_{1}}. \] Then \(\lambda_{i}'\geq 0\) for \(i=2, \ldots, m\) and \[ \lambda_{2}'+\cdots+\lambda_{m}'=\frac{\lambda_{2}+\cdots+\lambda_{m}}{1-\lambda_{1}}=\frac{\lambda_{2}+\cdots+\lambda_{m}}{\lambda_{2}+\cdots+\lambda_{m}} = 1. \] Thus \(y\) is a convex combination of \(m-1\) elements of \(C\), and \(y\in C\) by induction hypothesis. Since \(x=(1-\lambda_{1})y+\lambda_{1}x_{1}\), it now follows that \(x\in C\).
Definition. The intersection of all the convex sets containing a given subset \(S\) of \(\mathbb{R}^{n}\) is called the convex hull of \(S\) and is denoted \(\operatorname{conv}\!S\).
Theorem 2.4. For ant \(S\subset \mathbb{R}^{n}\), \(\operatorname{conv}\!S\) consists of all the convex combinations of the elements of \(S\).
[증명 스케치] (증명내용이 어렵진 않지만, 오랜만에 수학 공부를 하는만큼 스케치를 기술해본다.) 다음 사실을 상기하자.
- 정리 2.3에 따르면 \(A\)가 convex일 필요충분조건은 \(A\)가 \(A\)의 원소들로 만든 모든 convex combination들을 원소로 갖는 것이다.
- \(\operatorname{conv}\!S\)는 \(S\)를 포함하는 모든 convex set들의 intersection이다. 즉 \(\operatorname{conv}\!S\)는 \(S\)를 포함하는 가장 작은 convex set이다.
정리 2.4를 증명하기 위해선 \(S\)의 원소들의 convex combination들을 모두 모아 놓은 집합을 \(S^{*}\)라 할때, \(S^{*}=\operatorname{conv}\!S\)를 보이면 된다. \(x\in S^{*}\)라 할 때, \(x\)는 \(S\)의 원소들의 convex combination이다. 그런데 \(S\)의 원소들은 \(\operatorname{conv}\! S\)의 원소들이고, \(\operatorname{conv}\! S\)는 convex이므로 \(x\)는 \(\operatorname{conv}\! S\)의 원소이다. 즉 \(S^{*}\subset \operatorname{conv}\! S\)임을 알 수 있다. 또한 \(x, y\in S^{*}\)라 할 때, \((1-\lambda)x+\lambda y \in S^*, 0\leq \lambda\leq 1\)를 보이면 증명을 완성할 수 있다. 왜냐하면 \(\operatorname{conv}\! S\)는 \(S\)를 포함하는 가장 작은 convex set이고 \(S\subset S^{*}\)이기 때문이다.
Proof. The elements of \(S\) belong to \(\operatorname{conv}\! S\), so all their convex combinations belong to \(\operatorname{conv}\! S\) by theorem 2.3. On the other hand, given two convex combinations \[x=\lambda x_{1}+\cdots+\lambda_{m}x_{m}\] and \[y=\mu_{1}y_{1}+\cdots+\mu_{n}y_{n},\] where \(x_{i}\in S,\, y_{i}\in S\). The vector \begin{align*} (1-& \lambda)x + \lambda y \\[8pt] \quad & = (1-\lambda )(\lambda_{1}x_{1}+\cdots +\lambda_{m}x_{m})+\lambda (\mu_{1}y_{1}+\cdots + \mu_{n}y_{n}) \\[8pt] \quad & = (1-\lambda )\lambda_{1}x_{1}+\cdots +(1-\lambda)\lambda_{m}x_{m}+\lambda \mu_{1}y_{1}+\cdots +\lambda\mu_{n}y_{n}, \end{align*} where \(0\leq \lambda \leq 1\), is another convex combination of elements of \(S\). Thus the set of convex combinations of elements of \(S\) is itself a convex set. And it contains \(S\), so it must coincide with the smallest such convex set, $\operatorname{conv}\! S$.
Corollary 2.5. The convex hull of a finite subset \(\{ b_{0}, \ldots, b_{m}\}\) of \(\mathbb{R}^{n}\) consists of all the vectors of the form \(\lambda_{0}b_{0}+\cdots+ \lambda_{m}b_{m}\), with \(\lambda_{0}\geq 0, \ldots, \lambda_{m}\geq 0, \lambda_{0}+\cdots +\lambda_{m}=1\).
Proof. Every convex combination of elements selected from $\{ b_{0}, \ldots, b_{m}\}$ can be expressed as a convex combination of $b_{0}, \ldots, b_{m}$ by including the unneeded vectors $b_{i}$ with zero coefficients.
Definition. A set which is the convex hull of finitely many points is called a polytope. If $\{b_{0}, \ldots, b_{m}\}$ is affinely independent, its convex hull is called an m-dimensional simplex, and $b_{0},\ldots, b_{m}$ are called the vertices of the simplex.
Remark. The dimension of an affine set or simplex as already defined agree with its dimension as convex set.
Theorem 2.6. The dimension of a convex set \(C\) is the maximum of the dimension of the various simplices included in \(C\).
Proof. Elementary.
Definition. A subset \(K\) of \(\mathbb{R}^{n}\) is called a cone if it is closed under positive scalar multiplication, i.e. \(\lambda x\in K\) when \(x\in K\) and \(\lambda>0\).
Definition. A convex cone is a cone which is a convex set.
Remark. One should not necessarily think of a convex cone as being "pointed". Subspaces in $\mathbb{R}^{n}$ are in particular convex cones.
Example 2. Two of the most important convex cones are the non-negative orthant of $\mathbb{R}^{n}$, \[ \{ x=(\xi_{1}, \ldots, \xi_{n})\mid \xi_{1}\geq 0, \ldots, \xi_{n}\geq 0\}, \] and the positive orthant of $\mathbb{R}^{n}$, \[ \{ x=(\xi_{1}, \ldots, \xi_{n})\mid \xi>0, \ldots, \xi_{n}>0 \}. \] These cones are useful in the theory of inequalities. It is customary to write \(x\geq x'\) if \(x-x'\) belongs to the non-negative orthant, i.e. if \[ \xi_{j}\geq \xi_{j}'\quad \mbox{for}\quad j=1, \ldots, n. \] In this notation, the non-negative orthant consists of the vectors \(x\) such that \(x\geq 0\).
Theorem 2.7. The intersection of an arbitrary collection of convex cones is a convex cone.
Proof. Elementary.
Corollary 2.8. Let \(b_{i}\in \mathbb{R}^{n}\) for \(i\in I\), where \(I\) is an arbitrary index set. Then \[ K=\{ x\in\mathbb{R}^{n}\mid \forall i\in I, \langle x, b_{i}\rangle \leq 0 \} \] is a convex cone.
Proof. As in Corollary 2.2.
Of course, $\leq 0$ may be replaced by $\geq, >, <$ or $=$ in Corollary 2.8. Thus the set of solutions to a system of linear inequalities is a convex cone, rather than merely a convex set, if the inequalities are homogeneous.Theorem A subset of $\mathbb{R}^{n}$ is a convex cone if and only if it is closed under addition and positive scalar multiplication.
Proof. Let \(K\) be a cone. Let \(x\in K\) and \(y\in K\). If \(K\) is convex, the vector \(z=(1-1/2)x+(1/2) y=(1/2)(x+y)\) belongs to \(K\). Since \(K\) is a cone, \(2z=x+y\in K\), i.e. \(K\) is closed under addition. On the other hand, if \(K\) is closed under addition, and if \(0<\lambda <1\), the vectors \((1-\lambda)x\) and \(\lambda y\) belong to \(K\) and hence \((1-\lambda)x+\lambda y\in K\). Thus \(K\) is convex.