【備忘】Uniqueness of Solution In Linear Programming - DROで学位を取るまでの軌跡

本論文の概要
取り組む問題
内容
参考文献

本論文の概要

　本論文は与えられた線形計画問題の最適解がただ一つであるかどうかを確認する方法を示したものである。確認するにあたっては、最適解がただ一つであることの必要十分条件から導かれる線形計画問題を解けば良い。このブログでは主問題に焦点を絞っているが、論文では双対問題に対しても同値条件を考えている。主問題と双対問題の両方の同値条件を満たしていれば、問題を記述する全てのパラメータの十分小さい摂動に対して安定していると言える。

取り組む問題

線形計画問題

$\begin{eqnarray*} &\min_{x \in \mathbb{R}^{n}} p^{T}x \tag{1} \\ \text{s.t.} \quad &Ax = b \quad Cx \ge d \end{eqnarray*}$

双対問題

$\begin{eqnarray*} &\max_{u,v} b^{T}u + d^{T}v \tag{2} \\ \text{s.t.} \quad &A^{T}u + C^{T}v = p \quad v \ge 0 \end{eqnarray*}$

記法

　$x, p \in \mathbb{R}^{n} \quad b,u \in \mathbb{R}^{m} \quad d ,v \in \mathbb{R}^{k} \quad A \in \mathbb{R}^{m \times n} \quad C \in \mathbb{R}^{k \times n}$とする。
　次に添え字集合$J, K, L$を定義する。$x^{*}$を$(1)$の、$(u^{*}, v^{*})$の最適解とし、また$C_i$を行列$C$の$i$行目の行ベクトルとする。

$\begin{eqnarray*} J &=& \lbrace i \mid C_i x^{*} = d_i \rbrace \\ K &=& \lbrace i \mid v_i^{*} >0 \rbrace = \lbrace i \mid C_i x^{*} = d_i, v_i^{*} > 0 \rbrace \\ L &=& \lbrace i \mid C_i x^{*} = d_i, v_i^{*} = 0 \rbrace \end{eqnarray*}$

双対変数の定義域を考えると、$J = K \cup L$が成立する。

内容

定理１

定理

線形計画問題$(1)$が最適解$x^{*}$を唯一つ持つための必要十分条件は、$x^{*}$が最適化問題$(3)$の最適解となることである。$(3)$は、$(1)$のコスト関数に十分小さい大きさ$\epsilon > 0$で任意の方向$q \in \mathbb{R}^{n}$に摂動を加えた最適化問題である。

$\begin{eqnarray*} &\min_{x \in \mathbb{R}^{n}} (p + \epsilon q)^{T}x \tag{3} \\ \text{s.t.} \quad &Ax = b \quad Cx \ge d \end{eqnarray*}$

証明（方針）

　証明の詳細は割愛し、方針のみを述べる。$(1)$が最適解を唯一つしか持たないことの必要十分条件として、$(1), (2)$の制約条件を満たし、コスト関数を改善する実行可能解の係数倍が存在しないことが挙げられる。この必要十分条件を、過去の報告を用いて種々変形していくことで、題意を示すことができる。

定理2

線形計画問題$(1)$の最適解を$x^{*}$とする。次の命題は同値である：

$x^{*}$が唯一の最適解である。
$\forall q \in \mathbb{R}^{n}$に対して、$x^{*}$が$(3)$の最適解になるような$\epsilon > 0$が存在する。
次を満たす$x$は存在しない：$Ax = 0, \quad C_J x \ge 0, \quad p^{T} x \le 0, \quad x \neq 0.$
次を満たす$x$は存在しない：$Ax = 0, \quad C_K x = 0, \quad C_L x \geq 0, \quad x \neq 0.$
$[A^{T} \ C_K^{T} \ C_L^{T}]$の行は線形独立で、次を満たす$x$は存在しない：$Ax = 0, \quad C_K x = 0, \quad C_L x \geq 0.$
任意の$a, c, h \in \mathbb{R}$に対して、集合$\lbrace x | Ax = a, C_K x = c, C_L x \geq h \rbrace$は空か有界である。
任意の$q \in \mathbb{R}^{n}$に対して、次の線型方程式を満たす$\epsilon > 0$が存在する：$A^{T} u + C_J^{T} v_J = p + \epsilon q, \quad v_J \geq 0.$
任意の$s \in \mathbb{R}^{n}$に対して、次の線型方程式を満たす$(u, v_K, v_L)$が存在する：$A^{T} u + C_K^{T} v_K + C_L^{T} v_L = s, \quad v_L \geq 0.$
任意の$s \in \mathbb{R}^{n}$に対して、次の線型方程式を満たす$(u, v_K, v_L)$が存在する：$A^{T} u + C_K^{T} v_K + C_L^{T} v_L = s, \quad v_L > 0.$
$[A^{T} \ C_K^{T} \ C_L^{T}]$の行は線形独立で、次の線型方程式を満たす$(u, v_K, v_L)$が存在する：$A^{T} u + C_K^{T} v_K + C_L^{T} v_L = 0, \quad v_L > 0.$

証明

（1. ⇨ 2.の証明）
　定理１より成立する。

（1. ⇨ 7.の証明）
　定理１より、1.が成立するならば$x^{*}$は$(3)$の最適解である。$(3)$の双対問題や強双対問題を考えると、$A^{T}u + C^{T}v = p + \epsilon q \quad b^{T} u + d^{T} v = (p + \epsilon q) x^{*} \quad v \ge 0$が導かれ、このことから$v^{T}(C x^{*} - d) = 0$が得られる。$v_i \ge 0$であり、$i \notin J$に対して$v_i = 0$であるから、$C v^{*} = C_J v_J^{*}$となる。よって$A^{T}u + C^{T}_J v_J = p + \epsilon q$が成立する。

（7. ⇨ 4.の証明）
　4.の式を満たす$x$が存在するとして、背理法を用いて証明する。任意の$q$に対して7.が成立することから、$q = 0, -x$とする。それぞれを満たす$(u, v)= (u^{0}, v^{0}), (u^{*}, v^{*} )$に対して、$p = Au^{0} + C_J^{T} v_J^{0} = A u^{*} + C_J^{T} v_J^{*} - \epsilon x$が成立する。7.より$(u^{*}, v^{*} )$を$(2)$の最適解であるとして、この式を基に、$x$を両辺に掛け算すると、

$\begin{eqnarray*} 0 > - \epsilon x^{T} x &=& x^{T} A(u^{0} - u^{*} ) + x^{T} C_J^{T} (v_J^{0} - v_J^{*} ) \\ & = & (u_0 - u^{*} )^{T} A x + (v_J^{0} - v_J^{*} )^{T} C_J x \\ & = & (u_0 - u^{*} )^{T} A x + (v_K^{0} - v_K^{*} )^{T} C_K x + (v_L^{0})^{T} C_L x \\ & \ge & 0 \end{eqnarray*}$

が成立する。最後の不等式は、4.の仮定および$v^{*}_L = 0$を使用した。

（4. ⇨ 1.の証明）
　1.が成立しないとして、背理法を用いて証明する。$(1)$の異なる最適解を$x^{*},x^{**} $、$x^{*} \neq x^{**} $とする。$J$の添字集合に対応する最適解を$x^{**}$とすると、それぞれ共に$(1)$の最適解であるから、

$\begin{eqnarray*} p^{T}( x^{*} - x^{**} ) = 0 \\ A ( x^{*} - x^{**} ) = 0 \\ C_J ( x^{*} - x^{**} ) \ge 0 \end{eqnarray*}$

が成立する。$C_J ( x^{*} - x^{**} ) = (<{C_K}_i, x^{*} - x^{**} >, \cdots, <{C_K}_{|K|}, x^{*} - x^{**} >, <{C_L}_{i}, x^{*} - x^{**} >, \cdots, <{C_L}_{|L|}, x^{*} - x^{**} >)^{T} \ge 0$であり、4.が成立することから、$K$は非空であり、$\exists i \in K \quad \text{s.t.} \quad <{C_K}_{i}, x^{*} - x^{**} >0$となる。ここで、

$\begin{eqnarray*} 0 &=& p^{T}( x^{*} - x^{**} ) = (A u^{**} + C_J^{T} v_J^{**})( x^{*} - x^{**} ) \\ &=& {v_K^{**}}^{T} C_K ( x^{*} - x^{**} ) \\ &>& 0 \end{eqnarray*}$

となることから、4.から導かれる式に反する。よって、1.は成立する。

（4. ⇨ 5.の証明）
　対偶を考える。5.は「$[A^{T} \ C_K^{T} \ C_L^{T}]$が線型独立ならば、$Ax = 0, \quad C_K x = 0, \quad C_L x \geq 0.$を満たす$x$が存在する」であり、明らかに4.の否定「$Ax = 0, \quad C_K x = 0, \quad C_L x \geq 0.$を満たす$x$が存在する」は成立する。よって示された。

（5. ⇨ 10.の証明）
　Tucker's Theorem of the Alternativeより、10.を満たす$v_K \ge 0, v_L >0$が存在する。よって示された。

（10. ⇨ 9.の証明）
　10.より$[A^{T} \ C_K^{T} \ C_L^{T}]$のランクはその行数と一致し、非自明解$(u, v_K, v_L > 0)$を持つことから列数よりも小さい。また、その拡大係数行列のランクは行数と一致するため、$A^{T} u(s) + C_K^{T} v_K(s) + C_L^{T} v_L(s) = s$を満たす解$(u(s), v_K(s), v_L(s))$は存在する。
　ここで、十分大きい正数$\lambda$を用いると、$(u(s) + \lambda u, v_K(s) + \lambda v_K, v_L(s) + \lambda v_L >0)$は9.を満たす。よって示された。

（9. ⇨ 8.の証明） 　9.の解は明らかに8.を満たすため、成立する。

（8. ⇨ 4.の証明）
　　対偶を考え、4.が成立するとして、8.の式に$x^{T}$を左から掛け合わせる。

$\begin{eqnarray*} x^{T} s = (Ax)^T u + (C_K x)^{T} v_K + (C_L x)^T v_L = (C_L x)^T v_L \ge 0 \end{eqnarray*}$

　となる。ここで$s$は任意であるため、$s=-x(\neq 0)$とすると、上の式は成立しない。よって示された。

（8. ⇔ 6.の証明）
　6. が成立し有界ならば、$\forall s \in \mathbb{R}^{n}$に対して、それを定義域に持つ次の線形計画問題は最適解を持つ。

$\begin{eqnarray*} \min s^{T} x \quad \text{s.t.} \quad x \in \lbrace x | Ax = a, C_K x = c, C_L x \geq h \rbrace \end{eqnarray*}$

　これは次の双対問題が解を持つことと同値である。

$\begin{eqnarray*} \max_{u, v_K, v_L} a^{T} u + c^{T} v_K + h^{T} v_L \quad \text{s.t.} \quad A^{T} u + C_K^{T} v_K + C_L v_L, \quad v_L \ge 0 \end{eqnarray*}$

　つまり、この定義域である8.は解を持つ。
　（注意：原著では6.が空である場合を考えていない。空ならば、8.は非有界もしくは空となる思われる。)

（3. ⇔ 7.の証明）
　3. と同値な線形不等式系：

$\begin{eqnarray*} -sx > 0, \quad (C_J, -p^{T}) x \ge 0, \quad Ax =\boldsymbol{0}, \quad \forall s \in \mathbb{R}^n \end{eqnarray*}$

　が解$x$を持たないことは、Motzkin’s Theorem of the Alternativeより、

$\begin{eqnarray*} -s \eta + (C_J, -p^{T})^{T} (v_{J}, \epsilon) + A^{T}y = \boldsymbol{0}, \quad (v_{J}, \epsilon) \ge \boldsymbol{0}, \quad \eta >0 \end{eqnarray*}$

　が解を持つことと同値である。この式の順番を並び替え、$s = p+q$とすると

$\begin{eqnarray*} A^{T}y + C_J^{T} v_J = p(\eta + \epsilon) + \eta q, \quad (v_{J}, \epsilon) \ge \boldsymbol{0} \end{eqnarray*}$

　となり、両辺を$1+\epsilon, \eta$について変数変換するなど整理すれば7.の式と一致し、題意は示される。

解がただ一つであることの確認方法

　定理２の条件5.および10.が最も確認しやすく、以下にはそれぞれの条件を使った問題とその確認方法を示す。
（変数に定義のないものや、コスト関数の取り方に工夫の余地があると思われるので、以下は原文ママとする。）

（条件5.）
　$[A^{T} \ C_K^{T} \ C_L^{T}]$の行は線形独立である場合、次の最大化問題の最適値が$0$である。

$\begin{eqnarray*} \max e^{T} C_L x \\ \text{s.t.} \quad &Ax = 0 \quad C_K x = 0 \quad C_L x \ge 0 \end{eqnarray*}$

（条件10.）
　$[A^{T} \ C_K^{T} \ C_L^{T}]$の行は線形独立である場合、次の最大化問題は上に非有界である。

$\begin{eqnarray*} \max \delta \\ \text{s.t.} \quad &A^T u + C_K^{T} v_k + C_L^{T} v_L = 0, \quad v_L \ge e \delta \end{eqnarray*}$

参考文献

Mangasarian, Olvi. Uniqueness of solution in linear programming. University of Wisconsin-Madison Department of Computer Sciences, 1978.