1. simplex_method(シンプレックス法)

1.1. 冗長な制約式の除去

$K=R\text{or}C$,$A\in K^{m\times n}$とし

$$A=\left(\begin{array}{c}{a}_1^T\\ ⋮\\ a_m^T\end{array}\right)$$

と表されるとする。$r\equiv \mathrm{rank}\left(A\right)$と定義した時$\{a_j{\}}_{j=1}^m$から一次独立な$r$個のベクトル$a_{\sigma \left(1\right)},\dots ,a_{\sigma \left(r\right)}$を選び

$$A^{\prime }=\left(\begin{array}{c}{a}_{\sigma \left(1\right)}^T\\ ⋮\\ a_{\sigma \left(r\right)}^T\end{array}\right),b^{\prime }=\left(\begin{array}{c}{b}_{\sigma \left(1\right)}\\ ⋮\\ b_{\sigma \left(r\right)}\end{array}\right)$$

とおくと、$\{x\in R^n\mid Ax=b\}$が空集合でないならば

$\{x\in R^n\mid Ax=b\}=\{x\in R^n\mid A^{\prime }x=b^{\prime }\}$

(proof)

$r=\mathrm{rank}\left(A\right)$は一次独立な行ベクトルの最大個数と同じであるので、$\{a_j{\}}_{j=1}^m$から一次独立な$r$個のベクトル$a_{\sigma \left(1\right)},\dots ,a_{\sigma \left(r\right)}$をとることが出来る(具体的には追加した時に一次従属になるまで好きな順番で$\{a_j{\}}_{j=1}^m$からベクトルを取れば良い)

任意の$j\in \{1,\dots ,m\}$に対して$a_j$を$a_{\sigma \left(1\right)},\dots ,a_{\sigma \left(r\right)}$に加えると一次従属になるので、 $$a_j={\lambda }_{1j}{a}_{\sigma \left(1\right)}+\cdots +{\lambda }_{rj}{a}_{\sigma \left(r\right)}=\sum _{k=1}^r{\lambda }_{kj}{a}_{\sigma \left(k\right)}$$ を満たす定数${\lambda }_{kj}\in K$が存在する。

仮定より$\{x\in R^n\mid Ax=b\}$が空集合でないので、そこから１つ元$x^{\ast }$をとる。この時、集合の定義より任意の$j\in \{1,\dots ,m\}$に対して$a_j^T{x}^{\ast }=b_j$が成立するので、 $$b_j=a_j^T{x}^{\ast }={\left(\sum _{k=1}^r{\lambda }_{kj}{a}_{\sigma \left(k\right)}\right)}^T{x}^{\ast }=\sum _{k=1}^r{\lambda }_{kj}{a}_{\sigma \left(k\right)}^T{x}^{\ast }=\sum _{k=1}^r{\lambda }_{kj}{b}_{\sigma \left(k\right)}$$ ここまでが証明の準備で、最終的に示したいことは以下である。

$x\in R^n$が任意の$k\in \{1,\dots ,r\}$に対して$a_{\sigma \left(k\right)}^{T}x=b_{\sigma \left(k\right)}$となるならば、任意の$j\in \{1,\dots ,m\}$に対して$a_j^{T}x=b_j$である。

この事を式変形により示す。 $$a_j^{T}x={\left(\sum _{k=1}^r{\lambda }_{kj}{a}_{\sigma \left(k\right)}\right)}^{T}x=\sum _{k=1}^r{\lambda }_{kj}{a}_{\sigma \left(k\right)}^{T}x=\sum _{k=1}^r{\lambda }_{kj}{b}_{\sigma \left(k\right)}=b_j$$ 証明は以上で終了。ちなみに、$\{x\in R^n\mid Ax=b\}$が空集合の時は等式が成立しない。実際$A^{\prime }\in R^{n\times n}$を正則行列,$b^{\prime }\in R^n$ $$A=\left(\begin{array}{c}A\\ 0^T\end{array}\right),b=\left(\begin{array}{c}{b}^{\prime }\\ 1\end{array}\right)$$ とおくと$\{x\in R^n\mid Ax=b\}$は空集合だが、$\{x\in R^n\mid A^{\prime }x=b^{\prime }\}$は空集合でない。

1.2. 端点を持つことと直線を持たないことの同値性

Let $(H,⟨\cdot ⟩)$ be a finite-dimensional Hilbert space over $R$, and $C\subset H$ be a non-empty closed convex set. Then, $C$ has an extreme point iff $C$ does not contain line.

(proof)

($\Rightarrow$)$C$が端点$\overline{x}$を持つ時に直線を含まないことを背理法を用いて示す.$C$が直線を含むとすると,$x,d\in H,d\ne 0$が存在して$\{x+\alpha d\mid \alpha \in R\}\subset C$が成立する.任意の自然数$n\ge 1$に対して $$x^{\left(n\right)}=(1-\frac{1}{n})\overline{x}+\frac{1}{n}(x+nd)=\overline{x}+d+\frac{1}{n}(x-\overline{x})$$ と定義すると${lim}_{n\to \infty }{x}^{\left(n\right)}=\overline{x}+d$である.また,$C$の凸性より$x^{\left(n\right)}\in C$であり$C$は閉集合であるので$\overline{x}+d\in C$である.同様の議論を行うことで$\overline{x}-d\in C$が示される.ゆえに $$\overline{x}=\frac{1}{2}(\overline{x}+d)+\frac{1}{2}(\overline{x}-d)$$ となるが$\overline{x}$は端点なので$\overline{x}=\frac{1}{2}(\overline{x}+d)$もしくは$\overline{x}=\frac{1}{2}(\overline{x}-d)$が成立するがどちらの場合でも簡単な計算から$d=0$となるので矛盾.

($\Leftarrow$)$C$が直線を持たない時に端点を持つことを示す.$H$の次元に関する帰納法で示す.$0$次元の場合は$C=\left\{0\right\}$であるのでゼロベクトルの端点を持つ.$H$が$n-1$次元($n\ge 1$)で成立していると仮定して,$H$が$n$次元の場合を考える.$R$もしくは$C$上のノルム空間は弧状連結であるので特に連結である(証明略).また,連結である位相空間の空でない真部分集合は境界をもつので$C$の境界$\partial C$は空でない.今$C$の境界から元$x_0\in \partial C\subset C$を任意にとる.超平面分離定理より$a\in H,a\ne 0$が存在して,$\alpha \equiv ⟨a,x_0⟩\in R$と定義すると,任意の$y\in C$に対して,$⟨a,y⟩\le \alpha$を満たす.また,$H_{x_0}\equiv \{z\in H\mid ⟨a,z⟩=\alpha \}$と定義すると超平面の同値条件より$H_x$は超平面である.超平面の定義より$v_0\in H$と$n-1$次元の$H$の部分空間$Z$が存在して$H_x=Z+v_0$と表せる.$H$の部分空間$Z$は有限次元であるので,完備な体上の有限次元ベクトル空間は完備という定理を用いることで$Z$も完備であることがわかり,$n-1$次元のヒルベルト空間である.

この時,$C\cap H_x$は端点を持つ.

実際,$C^{\prime }\equiv C-v_0$と定義すると$x_0\in C\cap H_x$であるので $$(C^{\prime }\cap Z)+v_0=(C^{\prime }+v_0)\cap (Z+v_0)=C\cap H_x\ne \varnothing$$ であるので,$C^{\prime }\cap Z$も空集合でない.$C^{\prime }\cap Z$は$n-1$次元のヒルベルト空間$Z$上で閉集合かつ凸集合であり直線を含まないので帰納法の仮定から$C^{\prime }\cap Z$は$Z$上で端点を持つ.ゆえに$C\cap H_x=(C^{\prime }\cap Z)+v_0$であるので$C\cap H_x$は端点を持つ.

$C\cap H_x$の端点を任意に1つ選び$\overline{x}$とおき,これが$C$の端点であることを示す.今$x_1,x_2\in C$と$\lambda \in [0,1]$が存在して$\overline{x}=\lambda x_1+(1-\lambda )x_2$と表されたとする.

この時 $$\alpha =⟨a,\overline{x}⟩=\lambda ⟨a,x_1⟩+(1-\lambda )⟨a,x_2⟩$$ この時,$\overline{x}$は$C\cap H_x$の端点だったので$x_1,x_2$のどちらも$C\cap H_x$の元だとすると,端点の定義より$\overline{x}=x_1=x_2$となるので証明終了.よって,$x_1\notin C\cap H_x$と仮定する.この時,超平面の定義より$⟨a,x_1⟩<\alpha ,⟨a,x_2⟩\le \alpha$であるので,上の等式を満たすには$\lambda =0$となる.ゆえに$\overline{x}=x_2$となるので$\overline{x}$は$C$の端点となる.

参考資料

1.3. 線形最適化の最適解は端点である

Let $(H,⟨\cdot ⟩)$ be a finite-dimensional Hilbert space over $R$, $a_i\in H,c\in H,{\beta }_i\in R\forall i\in \{1,\dots ,m\}$. Let $P=\{x\in H\mid ⟨a_i,x⟩\le {\beta }_i,\forall i\in \{1,\dots ,m\left\}\right\}$, and consider LP:$max\{⟨c,x⟩\mid x\in P\}$. If $P$ has an extreme point, and the LP has an optimal solution, then the LP has an optimal solution which is an extreme point in $P$.

Corollary:

Let $A\in R^{m\times n}$,$b,c\in R^n$, $P\equiv \{x\in R^n\mid Ax\le b\}$, $x\ge 0$, and consider the LP;$max\{c^{\top }x\mid x\in P\}$. If LP has an optimal solution, then the LP has an optimal solution which is an extreme point in $P$.

(proof)${\alpha }^{\ast }$を最適値,$O\subset H$を最適解とすると$O\equiv \{x\in P\mid ⟨c,x⟩={\alpha }^{\ast }\}$と表すことができる.閉半区間は閉集合かつ凸集合であるので,その有限個の共通部分である$P$を閉集合かつ凸集合である.また,最適解を持つことから$P$は空集合でないので端点を持つことと直線を持たないことの同値条件より$P$は直線を持たない.ゆえに,その部分集合である$O$も直線を持たない.再び端点を持つことと直線を持たないことの同値条件を用いることで$O$は端点を持つ.$O$の端点の任意に1つ選び$\overline{x}$とした時に$P$の端点となることを示す.$x_1,x_2\in P,\lambda \in [0,1]$が存在して$\overline{x}=\lambda x_1+(1-\lambda )x_2$と表せたとすると以下を満たす. $${\alpha }^{\ast }=⟨c,\overline{x}⟩=\lambda ⟨c,x_1⟩+(1-\lambda )⟨c,x_2⟩$$ $x_1,x_2\in O$とすると$\overline{x}$は$O$の端点であるので$\overline{x}=x_1$もしくは$\overline{x}=x_2$となり証明が終了するので$x_1\notin O$とする.この時,$⟨c,x_1⟩<{\alpha }^{\ast }$, $⟨c,x_2⟩\le {\alpha }^{\ast }$となるので等式を満たすには$\lambda =0$となるので$\overline{x}=x_2$が成立.ゆえに$\overline{x}$は端点となる.

Corollaryについては $x\ge 0$により,端点を持つことと直線を持たないことの同値条件より$P$は端点を持つので,上記の定理が使えて最適解を持つなら端点であることが分かる.

参考資料

1.4. 定式化

LP-problem in canonical form $$\begin{array}{cccc}& \underset{x\in R^n}{\text{minimize}}& & z=c^{T}x\\ & \text{subject to}& & Ax=b\\ & & & x\ge 0\end{array}$$ where $A\in R^{m\times n}$ with $m\le n$ and rank $m$.

1.5. 定義

• $S\equiv \{x\in R^n\mid Ax=b,x\ge 0\}$: feasible solutions to an LP problem

• rank$\left(A\right)=m$であるので,適切に並び変えることで$A=(B,N),B\in R^{m\times m},\text{rank}\left(B\right)=m$とすることができる. この時 $$A(x_B^T,0^T{)}^T=b\iff B{x}_B=b$$ となる$x=(x_B^T,0^T{)}^T$はbasicと呼ばれる.さらに$x\ge 0$を満たす時$x$はbasic feasible solutionと呼ばれる.また,$x_B$をbasis variables,$x_N$をnon-basic variablesと呼ぶ.

  $A$の並び替え方は${}_n{C}_m$あるので basic feasible solutionは最大でその個数分ある.

1.6. 定理

1.6.1. 定理2_3端点と一時従属の同値条件

Suppose that $A=[A_1,A_2]$ and there exists $x_2$ such that $A_2{x}_2=b,x_2>0$. Then, the columns of $A_2$ are linearly dependent if and only if $x=(0^T,x_2^T{)}^T$ is not an extreme point in $S$.

(proof)($\Rightarrow$)$A_2$が一次従属(linearly dependent)というのと$A_{2}c=0$を満たす$c\ne 0$が存在することは必要十分であるので,そのような$c$を1つ固定する.この時,任意の正の数$ϵ>0$に対して $$A_2(x_2+ϵc)=b{A}_2(x_2-ϵc)=b$$ が成立する.$x_2>0$であるので$ϵ$を十分小さくとれば,$x_2+ϵc,x_2-ϵc>0$とすることができ,さらに$x_2=\frac{1}{2}(x_2+ϵc)+\frac{1}{2}(x_2-ϵc)$が成立する.ゆえに, $$x=(0^T,x_2^T{)}^T=\frac{1}{2}(0^T,(x_2+ϵc{)}^T{)}^T+\frac{1}{2}(0^T,(x_2-ϵc{)}^T{)}^T$$ であるので$x$は端点(extreme point)ではない.

($\Leftarrow$)逆に$x$が端点でないとしたら$v,w\ge 0,0<\lambda <1,v\ne x,w\ne x$で$Av=b,Aw=b,x=\lambda v+(1-\lambda )w$を満たすものが存在する.この時, $$0=x_1=\lambda v_1+(1-\lambda )w_1$$ であるので,$v_1=w_1=0$となる.ゆえに $$A_2(x_2-v_2)=A_2{x}_2-A_2{v}_2=Ax-Av=0$$ であり$x_2-v_2\ne 0$であるので$A_2$はlinearly dependent

1.6.2. 端点はbasic_feasible_solution

(Proof)LPの実行可能解の端点を$x$とすると定理2_3より高々$m$個の要素が非ゼロ要素となり対応する列ベクトルは1次独立となる.この時,LPの$A$の列,$c,b$を並び替えることによって非ゼロ要素を$x_1,\dots ,x_s(0\le s\le m)$, $a_1,\dots ,a_s$が一次独立である.また以下より$A$のいくつかの列を追加することで$a_1,\dots ,a_s,a_{s+1},\dots ,a_m$が一次独立であるようにできるので,そのように並びかえた$A$を考える.この時$B=(a_1,\dots ,a_s,a_{s+1},\dots ,a_m),A=(B,N)$と表記すると $$A\left(\begin{array}{c}{x}_B\\ 0\end{array}\right)=b$$ を満たす$x_B$は$B\in R^{m\times m}$が可逆であることから一意に定まる.一方$x=(x_1,\dots ,x_s,\dots ,x_n{)}^T=(x_1,\dots ,x_s,0^T{)}^T$はLPの実行可能解であることから$Ax=b$を満たす.よって,$x_B=(x_1,\dots ,x_s,0^T{)}^T$.ゆえに$x$はbasic feasible solutionである.

1.7. 参考文献

メイン, リンク切れ用