next up previous
: 双対定理 : 内点法 : はじめに


歪対称問題

$ n$次の歪対称行列$ \vec{M}$と非負のベクトル$ \vec{q}$が与えられているとき, これらに対応する歪対称問題は,

(SP)$\displaystyle \quad \min \{ \vec{q}^T \vec{\xi}: \vec{M} \vec{\xi} +\vec{q} \geq \vec{0}, \vec{\xi} \geq \vec{0} \}$ (2)

によって定義される. ただし, ベクトル$ \vec{\xi}$はベクトル$ \vec{q}$と同じ次元のベクトルである.

$ \vec{q} \geq \vec{0}$かつ $ \vec{\xi} \geq \vec{0}$から, (2)において $ \vec{q}^T \vec{\xi} \geq 0$であるが, $ \vec{\xi}=\vec{0}$とおくと $ \vec{q}^T \vec{\xi}=0$となる. すなわち, $ \vec{\xi}=\vec{0}$は(SP)のひとつの最適解である. 一方, 一般に(2)は零ベクトル以外の最適解を持ち, それらの解が内点法において重要な役割を果たす.

本節では歪対称問題の性質について述べる.

まず, (2)の制約条件を満たす領域を$ {\cal SP}$ とおく. すなわち,

$\displaystyle {\cal SP}=\left \{ \vec{\xi} \in \mathbb{R}^n: \vec{\xi} \geq \vec{0}, \vec{M} \vec{\xi} +\vec{q}\geq \vec{0} \right \} \ $ (3)

である. また, (2)の制約条件を等号抜きで満たす点(内点)を $ {\cal SP}^{+}$とおく. すなわち,

$\displaystyle {\cal SP}^{+}=\left \{ \vec{\xi} \in \mathbb{R}^n: \vec{\xi} > \vec{0}, \vec{M} \vec{\xi}+\vec{q} > \vec{0} \right \}$ (4)

である.

歪対称問題の最適解は $ \vec{q}^T \vec{\xi}=0$を満たす点の集合であるが, この集合を $ {\cal SP}^{\ast}$とおく. すなわち,

$\displaystyle {\cal SP}^{\ast}=\left \{ \vec{\xi} \in {\cal SP}: \vec{q}^T \vec{\xi} =0 \right \}$ (5)

である. $ {\cal SP}^{\ast}$は零ベクトルを含むことを注意しておく. さらに,

$\displaystyle \vec{s}(\vec{\xi}) = \vec{M} \vec{\xi} + \vec{q}$ (6)

と定義する. 記号の簡単のため, 曖昧さが生じる余地がないときには, $ \vec{s}(\vec{\xi})$を単に$ \vec{s}$と書くことがある. また, $ \vec{\xi}^{0}$などに対応して (6)が取る値を, $ \vec{s}^{0}$などと書くことがある. すなわち, $ \vec{s}^{0}=\vec{M}\vec{\xi}^{0}+\vec{q}$である.

最初に, いくつか技術的な補題を準備しておく.

補題 1 $ \vec{M}$$ n$次の歪対称行列であるとき, 任意の$ n$次のベクトル$ \vec{\xi}$に 対し, $ \vec{\xi}^T \vec{M} \vec{\xi} = 0$となる.

[証明] $ \vec{M}^T=-\vec{M}$だから,

$\displaystyle \vec{\xi}^T\vec{M} \vec{\xi}=(\vec{\xi}^T\vec{M} \vec{\xi})^T
=\vec{\xi}^T \vec{M}^T \vec{\xi} = \vec{\xi}^T (-\vec{M}) \vec{\xi}
$

となる. ゆえに $ \vec{\xi}^T \vec{M} \vec{\xi} = 0$である. ///

補題 2 $ \vec{q}^T \vec{\xi}= \vec{\xi}^T\vec{s}( \vec{\xi})$が成り立つ.

[証明] (6)より, $ \vec{\xi}^T \vec{s}(\vec{\xi})=\vec{\xi}^T \vec{M}\vec{\xi} +\vec{\xi}^T \vec{q}$である. よって, 補題1により, $ \vec{q}^T \vec{\xi}= \vec{\xi}^T\vec{s}( \vec{\xi})$となる. ///

補題 3 任意の$ \vec{\xi}$, $ \vec{\eta}$に対し, $ (\vec{\xi}-\vec{\eta})^T(\vec{s}(\vec{\xi})-\vec{s}(\vec{\eta}))=0$が成り立つ.

[証明] (6)より, $ \vec{s}(\vec{\xi})-\vec{s}(\vec{\eta})=\vec{M}(\vec{\xi}-\vec{\eta})$ である. したがって, 補題1より, $ (\vec{\xi}-\vec{\eta})^T(\vec{s}(\vec{\xi})-\vec{s}(\vec{\eta}))=0$となる. ///

補題 4 $ \vec{\xi}$および $ \vec{\eta}$がともに歪対称問題の最適解であるための 必要十分条件は, $ \vec{\xi}^T \vec{s}(\vec{\eta})=\vec{\eta}^T \vec{s}(\vec{\xi} )=0$となることである.

[証明] 補題3より, 任意の$ \vec{\xi}$, $ \vec{\eta}$に対し, 等式

$\displaystyle \vec{\xi}^T \vec{s}(\vec{\xi} )+\vec{\eta}^T \vec{s}(\vec{\eta} )=\vec{\xi}^T \vec{s}(\vec{\eta} )+\vec{\eta}^T \vec{s}(\vec{\xi} )$ (7)

が成り立つ. (7)を利用して補題を示そう. 補題2により, $ \vec{\xi}$, $ \vec{\eta}$がともに最適解であるための必要十分条件は, $ \vec{\xi}^T \vec{s}(\vec{\xi} )=\vec{\eta}^T \vec{s}(\vec{\eta} )=0$となることである. ところで, $ \vec{\xi}$ $ \vec{\eta}$は最適解だから, $ \vec{\xi} \geq \vec{0}$, $ \vec{\eta} \geq \vec{0}$, $ \vec{s}(\vec{\xi}) \geq \vec{0}$, $ \vec{s}(\vec{\eta}) \geq \vec{0}$である. したがって, (7)より

\begin{displaymath}
\begin{split}
\vec{\xi}^T \vec{s}(\vec{\xi} )=\vec{\eta}^T \...
...s}(\vec{\eta} )=\vec{\eta}^T \vec{s}(\vec{\xi} )=0
\end{split}\end{displaymath}

となる. ///

補題 5 $ \vec{s}=\vec{M}\vec{\xi}+\vec{q}$, $ \vec{\xi}>\vec{0}$, $ \vec{s} > \vec{0}$のとき, $ \vec{\Xi}=\mathop {\rm diag}(\vec{\xi})$, $ S=\mathop {\rm diag}(\vec{s})$とすると, 行列 $ \vec{M}\vec{\Xi}+\vec{S}$は正則である.

[証明] $ \vec{\xi}>\vec{0}$, $ \vec{s} > \vec{0}$より, $ \vec{\Xi}$および$ \vec{S}$は正則である. よって, もし $ \vec{\Xi} \vec{M}\vec{\Xi} + \vec{S}\vec{\Xi}$が正則であれば, これに正則行列 $ \vec{\Xi}^{-1}$を右から乗じた結果得られる $ \vec{\Xi} \vec{M} + \vec{S}$も正則となる. ところで, 任意のベクトル $ \vec{\eta}\neq \vec{0}$に対し, $ \vec{M}$が歪対称行列であることから,

$\displaystyle \vec{\eta}^T(\vec{\Xi} \vec{M}\vec{\Xi} + \vec{S}\vec{\Xi})\vec{\...
...ec{\eta}^T \vec{S}\vec{\Xi}\vec{\eta}
=\vec{\eta}^T \vec{S}\vec{\Xi}\vec{\eta}
$

となる. ところで, 行列 $ \vec{S}\vec{\Xi}$の対角要素は $ \vec{s}\vec{\xi}$の成分であり, $ \vec{s}\vec{\xi}> \vec{0}$だから, $ \vec{S}\vec{\Xi}$は正定対称行列である. したがって, $ \vec{\eta}^T \vec{S}\vec{\Xi}\vec{\eta} >0$ である. ゆえに $ \forall \vec{\eta} \neq \vec{0}$, $ \vec{\eta}^T(\vec{\Xi} \vec{M}\vec{\Xi} + \vec{S}\vec{\Xi})\vec{\eta} \ne 0$ であり, したがって行列 $ \vec{\Xi} \vec{M}\vec{\Xi} + \vec{S}\vec{\Xi}$は正則である. ///

補題 6 関数 $ f(\vec{x})$が2階連続微分可能で, $ \vec{\nabla}^2 f$が正定値なら, $ f$は狭義凸関数である.

[証明] Taylorの定理により, ある $ \theta \in [0,1]$に対し,

$\displaystyle f(\vec{x}+\vec{h})=f(\vec{x}) +(\vec{\nabla} f(\vec{x}))\vec{h} +\vec{h}^T (\vec{\nabla}^2 f(\vec{x}+\theta \vec{h}) )\vec{h}$ (8)

となる. 仮定より, $ \vec{\nabla}^2 f$は正定値だったから, $ \vec{x}_2 \neq \vec{x}_1$なら, (8)において $ \vec{x}=\vec{x}_1$, $ \vec{h}=\vec{x}_2-\vec{x}_1$とおくと,

$\displaystyle f(\vec{x}_2) > f(\vec{x}_1)+(\vec{\nabla}f(\vec{x}_1))(\vec{x}_2-\vec{x}_1)$ (9)

が成り立つ. $ t \in (0,1)$とし, (9)において $ \vec{x}_2=\vec{x}$, $ \vec{x}_1=t \vec{x}+(1-t)\vec{y}$とすると, $ \vec{x}_2-\vec{x}_1=(1-t)(\vec{x}-\vec{y})$より,

$\displaystyle f(\vec{x}) > f(\vec{x}_1)+(1-t)(\vec{\nabla}f(\vec{x}_1))(\vec{x}-\vec{y})$ (10)

となる. 一方, (9)において $ \vec{x}_2=\vec{y}$, $ \vec{x}_1=t \vec{x}+(1-t)\vec{y}$とすると, $ \vec{x}_2-\vec{x}_1=t(\vec{y}-\vec{x})$より,

$\displaystyle f(\vec{y}) > f(\vec{x}_1)+t(\vec{\nabla}f(\vec{x}_1))(\vec{y}-\vec{x})$ (11)

(10)の両辺に$ t$を, (11)の両辺に$ (1-t)$を乗じてから 足し合わせ, $ \vec{x}_1=t \vec{x}+(1-t)\vec{y}$を代入すると,

$\displaystyle t f(\vec{x}) + (1-t) f(\vec{y}) > f(t \vec{x}+(1-t)\vec{y})$ (12)

となる. これが証明すべき不等式であった. ///

本節では, これ以降で, 中心パスと強相補解と呼ばれる解を定義してから その存在を証明するのだが, そのためは, 以下で述べる 対数障壁関数と呼ばれる関数が必要となる.

定義 7 (対数障壁関数) 集合 $ {\cal SP}^{+}$が空でないとき, $ {\cal SP}^{+}$において

\begin{displaymath}\begin{split}f_{\mu}(\vec{\xi})&=\sum_{i=1}^n \psi \left ( \f...
...ec{\xi})}{\mu} -1 \right ) \ \psi(t)&=t-\log (1+t) \end{split}\end{displaymath} (13)

によって定義される関数 $ f_{\mu}$を対数障壁関数と呼ぶ.

関数$ \psi (t)$の形状を図1に示す.

図 1: 関数$ \psi (t)$の形状
\includegraphics[scale=1]{lbf.eps}

$ f_{\mu}$が一定値$ K$以下となる $ {\cal SP}^{+}$の点の集合を $ {\cal L}_K$とおく. すなわち, $ {\cal L}_K=\left \{ \vec{\xi} \in {\cal SP}^{+}: f_{\mu}(\vec{\xi} ) \leq K \right \}$ である.

対数障壁関数に関するいくつかの補題を述べよう.

補題 8 $ \psi (t)$は非負の狭義凸関数であり, $ t=0$において最小値0を取る. また, $ t \rightarrow -1$ $ t\rightarrow \infty$の極限で無限大となる.

[証明] $ d^2 \psi /dt^2 = 1/(1+t)^2>0$だから, 補題6より, $ \psi$は狭義凸関数である. また, $ d \psi/dt=1-1/(1+t)$より, $ \psi$$ t=0$において唯一の極小値(すなわち最小値)を取る. この最小値は零である. $ t \rightarrow -1$としたとき, $ \log (1+t) \rightarrow -\infty$だから, $ \lim_{t \rightarrow -1} (t-\log(1+t) = \infty)$である. 一方, $ t=\log e^t$に注意すると,

$\displaystyle \lim_{t \rightarrow \infty} (t-\log (1+t))
=\lim_{t \rightarrow \infty} \log \frac{e^t}{1+t}
=\infty
$

である. ///

補題 9 対数障壁関数$ f_{\mu}$ $ \vec{\xi}>\vec{0}$, $ \vec{s} > \vec{0}$の範囲で狭義凸関数である.

[証明] (13)を整理すると

$\displaystyle f_{\mu}(\vec{\xi}) =\frac{\sum_{i=1}^{n}\xi_i s_i}{\mu} -\sum_{i=1}^{n}\log \xi_i s_i -n(1-\log \mu)$ (14)

となるが. ここで, $ \sum_{i=1}^{n}\xi_i s_i=\vec{\xi}^T\vec{s}=\vec{q}^T\vec{\xi}$に注意すると, (14)は

$\displaystyle f_{\mu}(\vec{\xi}) =\frac{\vec{q}^T\vec{\xi}}{\mu} -\sum_{i=1}^{n}\log \xi_i s_i -n(1-\log \mu)$ (15)

と書き直される. さて, ここで(15)の 第2項を $ (\vec{\xi},\vec{s})$の関数と見て,

$\displaystyle g(\vec{\xi},\vec{s})=-\sum_{i=1}^{n}\log \xi_i s_i$ (16)

とおくと,

$\displaystyle \vec{\nabla}^2 g = \mathop {\rm diag}(1/\xi_1^2,\ldots,1/\xi_n^2,1/s_1^2,\ldots,1/s_n^2)$ (17)

であるが, $ \vec{\xi}>\vec{0}$, $ \vec{s} > \vec{0}$であれば これは正定値である. よって, 補題6より, $ g(\vec{\xi}, \vec{s})$は狭義凸関数である.

さて, (16)の$ \vec{s}$ $ \vec{s}=\vec{M}\vec{\xi}+\vec{q}$ を代入した関数を

$\displaystyle h(\vec{\xi})=g(\vec{\xi},\vec{M}\vec{\xi}+\vec{q})$ (18)

とする. $ \vec{\xi}^{\sharp}> \vec{0}$, $ \vec{\xi}^{\natural} > \vec{0}$を適当に取り, $ \vec{s}^{\sharp}=\vec{M}\vec{\xi}^{\sharp}+\vec{q}$, $ \vec{s}^{\natural}=\vec{M}\vec{\xi}^{\natural}+\vec{q}$ とおく. $ t \in (0,1)$に対し, $ \vec{\xi}=t \vec{\xi}^{\sharp}+(1-t)\vec{\xi}^{\natural}$, $ \vec{s}=t \vec{s}^{\sharp}+(1-t)\vec{s}^{\natural}$ とすると, $ \vec{s}=\vec{M}\vec{\xi}+\vec{q}$であり, したがって $ g(\vec{\xi},\vec{s})=h(\vec{\xi})$である. 一方, $ g$が狭義凸関数であったことから,

\begin{displaymath}\begin{split}h(\vec{\xi}) &=h(t \vec{\xi}^{\sharp}+(1-t)\vec{...
... h(\vec{\xi}^{\sharp})+ (1-t) h(\vec{\xi}^{\sharp}) \end{split}\end{displaymath} (19)

である. よって$ h$は狭義凸関数である.

さて, (18)を使って(15)を書き直すと

$\displaystyle f_{\mu}(\vec{\xi}) =\frac{\vec{q}^T\vec{\xi}}{\mu} +h(\vec{\xi}) -n(1-\log \mu)$ (20)

となる. (20)の第1項は線形だから,

$\displaystyle \vec{q}^T\left ( t \vec{\xi}^{\sharp}+(1-t)\vec{\xi^{\natural}}\right ) = t \vec{q}^T \vec{\xi}^{\sharp}+(1-t)\vec{q}^T \vec{\xi^{\natural}}$ (21)

である. また, (20)の第3項は定数である. したがって, (19)と(21)を合わせると,

$\displaystyle f_{\mu}\left ( t\vec{\xi}^{\sharp}+(1-t)\vec{\xi}^{\natural} \right ) < t f_{\mu}(\vec{\xi}^{\sharp})+(1-t)(\vec{\xi}^{\natural})$ (22)

となるから, $ f_{\mu}$は狭義凸関数である. ///

続いて, 内点法に理論的な根拠を与える重要な定理を述べる.

定理 10 $ \mu>0$を固定する. このとき, 以下の 1)から 5)は等価である.
1)
$ {\cal SP}^{+}$は空集合でない.
2)
ある$ K \geq 0$に対し, $ {\cal L}_K$は空でない有界閉集合となる.
3)
$ f_{\mu}$は点 $ \vec{\xi}^{0}$において最小値を取り, この点で $ \vec{\xi}^{0} > \vec{0}$, $ \vec{s}^{0}> \vec{0}$が満たされる.
4)
$ \vec{\xi}$$ \vec{s}$に関する方程式

$\displaystyle \vec{M}\vec{\xi} +\vec{q}=\vec{s},\quad \vec{\xi} \vec{s}=\mu \vec{1}$ (23)

$ \vec{\xi} ,\vec{s} > \vec{0}$の範囲で解を持つ.
5)
任意の$ K>0$に対し, $ {\cal L}_K$は空でない有界閉集合となる.

[証明] これ以降で, まず1から4までが等価であることを示し, 続いて5から2が導けることと, 1から4までを使うと5が導けることを示す.

$ \Rightarrow$#enum:eq2#817> : $ \vec{\xi}^{0}\in {\cal SP}^{+}$を取り, 対応する$ f_{\mu}$の値を $ K=f_{\mu}(\vec{\xi}^{0})$とおく.

$\displaystyle {\cal L}_K=\left \{ \vec{\xi} :f_{\mu}(\vec{\xi} ) \leq K \right \}$ (24)

とする. $ {\cal L}_K$が空でない有界閉集合であることが 言えればよい. ところで, $ \vec{\xi}^{0} \in {\cal L}_K$より $ {\cal L}_K$は空ではない. $ {\cal L}_K$が有界であることを見よう. $ \vec{\xi} \in {\cal L}_K$とする. $ f_{\mu}(\vec{\xi} ) =\sum_{i=1}^n\psi(\xi_i s_i/\mu-1) \leq K$だから, それぞれの$ i$に対して, $ \psi(\xi_i s_i/\mu-1) \leq K$でなければならない. したがって, ある正数$ a,b$が存在して($ a < 1$),

$\displaystyle \xi_i s_i/\mu-1 \in [-a,b]$ (25)

となる(図1参照). ゆえに, 各$ i$に対し, $ \xi_i s_i \leq 1+ \mu b$であり, したがって $ \vec{\xi}^T\vec{s} \leq n\mu(1+b)$となる. 次に, 補題3より,

$\displaystyle \vec{\xi}^T\vec{s}^{0}+\vec{s}^T\vec{\xi}^{0} =(\vec{\xi}^{0})^T\vec{s}^{0} +\vec{\xi}^T\vec{s} \leq (\vec{\xi}^{0})^T\vec{s}^{0} + n \mu (1+b)$ (26)

であり, $ \vec{\xi} \geq \vec{0}$, $ \vec{s} \geq \vec{0}$, $ \vec{\xi}^{0} > \vec{0}$, $ \vec{s}^{0}> \vec{0}$から,

$\displaystyle \xi_i \leq \frac{(\vec{\xi}^{0})^T\vec{s}^{0} + n \mu (1+b)}{s_i^0}$ (27)

となる. 同様にして,

$\displaystyle s_i \leq \frac{(\vec{\xi}^0)^T\vec{s}^0 + n \mu (1+b)}{\xi_i^0}$ (28)

が示される. 一方, (25)から, $ \xi_i s_i \geq \mu (1-a)$である. したがって $ s_i \neq 0$であり,

$\displaystyle \xi_i \geq \frac{\mu(1-a)}{s_i}\geq \frac{\xi_i^0\mu(1-a)}{(\vec{\xi}^0)^T\vec{s}^0 + n \mu (1+b)}
$

となる. よって,

$\displaystyle \xi_i \in \left [ \frac{\xi_i^0\mu(1-a)}{(\vec{\xi}^0)^T\vec{s}^0 + n \mu (1+b)}, \frac{(\vec{\xi}^0)^T\vec{s}^0 + n \mu (1+b)}{s_i^0} \right ]$ (29)

となる. 同様に,

$\displaystyle s_i \geq \frac{\mu(1-a)}{\xi_i}\geq \frac{s_i^0\mu(1-a)}{(\vec{\xi}^0)^T\vec{s}^0 + n \mu (1+b)}
$

より,

$\displaystyle s_i \in \left [ \frac{s_i^0\mu(1-a)}{(\vec{\xi}^0)^T\vec{s}^0 + n \mu (1+b)}, \frac{(\vec{\xi}^0)^T\vec{s}^0 + n \mu (1+b)}{\xi_i^0} \right ]$ (30)

となる. (29)は $ {\cal L}_K$が有界であることを 意味する. また, $ f$は連続関数だから, $ {\cal L}_K$ $ {\cal SP}^{+}$の閉集合, すなわち $ \mathbb{R}^{n}$の閉集合と $ {\cal SP}^{+}$の交わりである. ところで, $ {\cal L}_K$は(29), (30)によって定まる2個の閉集合に 含まれるので, $ \mathbb{R}^{n}$の閉集合とこれら2個の閉集合の交わりに一致し, したがって $ \mathbb{R}^{n}$の閉集合である. 以上によって $ {\cal L}_K$が有界閉集合であることが示された.

$ \Rightarrow$#enum:eq3#938> : ある $ {\cal L}_K$が有界閉集合であると仮定する. $ f_{\mu}$は連続だから, $ {\cal L}_{K}$上で最小値を取る. この点を $ \vec{\xi}^0$とする. $ f_{\mu}(\vec{\xi}^0)$は有限だから, 各$ i$に対し, $ \xi^0_i s^0_i \neq 0$であり, したがって $ \vec{\xi}^0 > \vec{0}$, $ \vec{s}^0> \vec{0}$ となる.

$ \Rightarrow$#enum:eq4#951> : $ f_{\mu}$ $ \vec{\xi}^0$において最小値を取るものとする. すると, $ \partial f_{\mu}/ \partial \xi_i$ $ \vec{\xi}^0$において零となる.

$\displaystyle \frac{\partial f_{\mu}}{\partial \xi_j}
= \frac{s_j}{\mu}+\frac{...
...mu}\sum_{i=1}^n \xi_i m_{ij}
-\frac{1}{\xi_j}-\sum_{i=1}^n\frac{m_{ij}}{s_i},
$

より,

\begin{displaymath}
\begin{split}
\nabla f_\mu &=\frac{\vec{s}}{\mu}-\frac{1}{\...
...{1}{\mu}\vec{M}\vec{\xi} +\vec{M} \frac{1}{\vec{s}}
\end{split}\end{displaymath}

となる. よって, $ \vec{\xi}^0$において

$\displaystyle \frac{\vec{s}^0}{\mu}-\frac{1}{\vec{\xi}^0}=\vec{M}\left ( \frac{1}{\mu}\vec{\xi}^0-\frac{1}{\vec{s}^0} \right )
$

となる. この両辺に $ \left ((1/ \mu) \vec{\xi}^0- 1/ \vec{s}^0 \right )^T$を掛けると

$\displaystyle \left ( \frac{1}{\mu}\vec{\xi}^0-\frac{1}{\vec{s}^0} \right )^T\left ( \frac{\vec{s}^0}{\mu}-\frac{1}{\vec{\xi}^0} \right )=0
$

となり, したがって, $ \vec{\Xi}^0=\mathop {\rm diag}\vec{\xi}^0$, $ \vec{S}^0=\mathop {\rm diag}\vec{s}^0$ とすると,

$\displaystyle \left ( \frac{\vec{\xi}^0\vec{s}^0}{\mu}-\vec{1} \right )^T (\vec...
...} (\vec{S}^0)^{-1} \left ( \frac{\vec{\xi}^0 \vec{s}^0}{\mu}-\vec{1} \right )=0$ (31)

となる. $ \vec{\Xi}^0\vec{S}^0$は正定対称行列だから, $ \vec{\xi}^0$$ \vec{s}^0$が(31) を満たしているということは, $ (\vec{\xi}^0 \vec{s}^0)/\mu = \vec{1}$ であることを意味する.

$ \Rightarrow$#enum:eq1#1043> : % latex2html id marker 12946
$ (\ref{eq-Mx+q=s})$の解を $ (\vec{\xi},\vec{s})$とすると, $ \vec{s}=\vec{M}\vec{\xi}+\vec{q}$であり, かつ $ \vec{\xi} \vec{s}= \mu \vec{1}$より, $ \vec{\xi}>\vec{0}$, $ \vec{s} > \vec{0}$である. よって, $ \vec{\xi} \in {\cal SP}^{+}$であり, したがって $ {\cal SP}^{+}$は空でない.

$ \Rightarrow$#enum:eq2#1064> : 25の特別な場合だから明らか.

1 $ \sim$ $ \Rightarrow$ #enum:eq5#1069> : % latex2html id marker 12968
$ (\ref{eq-Mx+q=s})$の解 $ (\vec{\xi},\vec{s})$ $ f_{\mu}(\vec{\xi} )=0$を満たすから, 任意の$ K \geq 0$に対し, $ {\cal L}_K$は空でない. $ {\cal L}_K$が 有界閉集合となることは, 1 $ \Rightarrow$2の証明から明らか. ///

補題5を利用すると, (23)の解の一意性を示すことができる.

系 11 $ \mu>0$に対し, (23)の $ \vec{\xi}>\vec{0}$, $ \vec{s} > \vec{0}$を満たす解は一意的である.

[証明] 定理10により(32)が少なくともひとつ 解を持つことは保証されている. そこで, (23)が2個以上の解を持つと仮定して矛盾を導く. $ (\vec{\xi}^{\sharp},\vec{s}^{\sharp})$, $ (\vec{\xi}^{\natural},\vec{s}^{\natural})$を (23)の各成分が0より大きい解とする. このとき,(23)の第2式より, $ f_{\mu}(\vec{\xi}^{\sharp})=0$, $ f_{\mu}(\vec{\xi}^{\natural})=0$である. また, 補題8により, $ f_{\mu}$が負の値を取ることはない. ところで, $ t \in [0,1]$とし, $ \vec{\xi}=t \vec{\xi}^{\sharp}+(1-t)\vec{\xi}^{\natural}$, $ \vec{s}=t \vec{s}^{\sharp}+(1-t)\vec{s}^{\natural}$とおくと, $ \vec{s}=\vec{M}\vec{\xi}+\vec{q}$となる. すなわち, このようにして定められた $ (\vec{\xi},\vec{s})$は (23)の第1式を満たす. 一方, 補題9により, $ f_{\mu}$は狭義凸関数だったから,

\begin{displaymath}\begin{split}f_\mu(\vec{\xi}) &=f_\mu (t \vec{\xi}^{\sharp} +...
...sharp} ) + (1-t) f_\mu ( \vec{\xi}^{\natural} ) = 0 \end{split}\end{displaymath} (32)

でなければならない. (32)は$ f_{\mu}$が非負であることと矛盾する. ///

補題 12 集合 $ {\cal SP}^{+}$が空でないとき, 集合 $ {\cal SP}^{\ast}$は有界となる.

[証明] 適当な $ \vec{\xi}^0 \in {\cal SP}^{+}$を取る. また, $ \vec{\xi}^{\ast} \in {\cal SP}^{\ast}$とする. すると, $ \left ( \vec{\xi}^0-\vec{\xi}^{\ast} \right )^T\left ( \vec{s}^0-\vec{s}^{\ast} \right )=0$および $ (\vec{\xi}^{\ast})^T\vec{s}^{\ast}=0$より,

$\displaystyle (\vec{\xi}^0)^T\vec{s}^{\ast}+(\vec{\xi}^{\ast})^T(\vec{s}^0)=(\vec{\xi}^0)^T\vec{s}^0
$

であるが, $ \vec{\xi}^0 > \vec{0}$, $ \vec{s}^0> \vec{0}$, $ \vec{\xi}^{\ast} \geq \vec{0}$, および $ \vec{s}^{\ast} \geq \vec{0}$から,

$\displaystyle (\vec{\xi}^0)^T\vec{s}^{\ast} \leq (\vec{\xi}^0)^T\vec{s}^0, \quad (\vec{\xi}^{\ast})^T(\vec{s}^0) \leq (\vec{\xi}^0)^T\vec{s}^0
$

となる. よって,

$\displaystyle s^{\ast}_j \leq \frac{(\vec{\xi}^0)^T\vec{s}^0}{\xi^0_j}, \quad \xi^{\ast}_j \leq \frac{(\vec{\xi}^0)^T\vec{s}^0}{s^0_j}$ (33)

となり, したがって$ SP^{\ast}$は有界である. ///

$ {\cal SP}^{+}$が空でないとき, 任意の$ \mu>0$に対し, 系11より, (23)を満たす$ \vec{\xi}$が一意的に定まる. これを $ \vec{\xi} (\mu)$と書く. また, $ \vec{s}(\mu)=\vec{s}(\vec{\xi} (\mu))$と定義する. (23)より, $ \vec{\xi} (\mu)\vec{s}(\mu)=\mu \vec{1}$だから,

$\displaystyle \vec{q}^T\vec{\xi} (\mu)=\vec{s}(\mu)^T\vec{\xi} (\mu)=n\mu$ (34)

である. よって, $ \mu \rightarrow 0$とすると, 目的関数 $ \vec{q}^T\vec{\xi} (\mu)$の値は 単調に減少する.

定義 13 集合 $ \left \{ \vec{\xi} (\mu):\mu>0 \right \}$を中心パスと呼ぶ.

補題 14 集合 $ {\cal SP}^{+}$が空でないとき, $ \vec{\xi} (\mu)$$ \mu $の関数と見ると, これは連続かつ微分可能である.

[証明] 系11により, どのような$ \mu>0$に対しても(23)をみたす $ \vec{\xi}>\vec{0}$が唯一存在することはすでに保証されているので, 関数 $ \vec{\xi} (\mu)$が微分可能性であることのみ示せばよい. (23)の第2式の解は, $ f_i=s_i \xi_i - \mu$とし, $ \vec{f}=[f_1,\ldots,f_n]^T$とおくと, $ \vec{f}=\vec{0}$の解である. $ \vec{f}$は無限回連続微分可能だから, 陰関数定理により, $ \vec{\xi}$が微分可能であるためには, $ \partial \vec{f}/\partial \vec{\xi}$ が(23)のある解 $ (\vec{\xi},\mu)$の近傍で 正則であることがいえればよい.

$\displaystyle \frac{\partial f_i}{\partial \xi_i}= s_i+\xi_i m_{ii}, \quad
\frac{\partial f_i}{\partial \xi_k}= \xi_i m_{ik} (k \neq i)
$

により,

$\displaystyle \frac{\partial \vec{f}}{\partial \vec{\xi}}=\vec{\Xi} \vec{M} + \vec{S}$ (35)

であるが, 補題5より, 行列 $ \vec{\Xi} \vec{M} + \vec{S}$は正則である. ///

補題 15 集合 $ {\cal SP}^{+}$が空でないとき, 任意の$ \mu>0$に対し, $ \left ( \vec{\xi} (\mu),\vec{s}(\mu) \right )$は有界となる.

[証明] 適当な $ \vec{\xi}^0 \in {\cal SP}^{+}$を取る. このとき,

$\displaystyle \left ( \vec{\xi}^0-\vec{\xi} (\mu) \right )^T\left ( \vec{s}^0-\vec{s}(\mu) \right )=0
$

から,

\begin{displaymath}\begin{array}{ccl} s_j^0 \vec{\xi} _j(\mu) &\leq& (\vec{s}^0)...
...vec{\xi} (\mu)\ &=& (\vec{s}^0)^T\vec{\xi}^0+n \mu \end{array}\end{displaymath} (36)

となる. $ s_j^0 \neq 0$だから,

$\displaystyle \xi_j(\mu) \leq \frac{(\vec{s}^0)^T\vec{\xi}^0}{s^0_j}+ \frac{n \mu}{s_j^0}$ (37)

となり, $ \vec{\xi} (\mu)$の有界性が示された. $ \vec{s}(\mu)$の有界性も同様にして示される. ///

以上の準備のもとで, 強相補解と呼ばれる(SP)に対する特別な形の解 を定義し, 続いて実際に強相補解が存在することを示す.

定義 16 (SP)に対する $ \vec{\xi}^{\ast}+\vec{s}(\vec{\xi}^{\ast})> \vec{0}$を満たす最適解を, 強相補解と呼ぶ.

定理 17 集合 $ {\cal SP}^{+}$が空でなければ強相補解が存在する.

[証明] 正の値を取り0に収束する点列$ (\mu_k)$を取り, 各$ \mu_{k}$に対応する (23)の解を $ (\vec{\xi}_k,\vec{s}_k)$とする. 補題15により, 点列 $ (\vec{\xi}_k,\vec{s}_k)$は有界であり, 集積点を持つ. また, 点 $ (\vec{\xi}^{\ast},\vec{s}^{\ast})$が 点列 $ (\vec{\xi}_k,\vec{s}_k)$の集積点であれば, この点列は $ (\vec{\xi}^{\ast},\vec{s}^{\ast})$に収束する部分列 $ (\vec{\xi}_{k_j},\vec{s}_{k_j})$を持つ. 記法の簡単のため, $ (\mu_{k})$の部分列 $ (\mu_{k_j})$ を新たに$ (\mu_{k})$と取り直し, 各$ \mu_k$に対応する(23)の解を改めて $ (\vec{\xi}_k,\vec{s}_k)$とおく. このとき, $ (\mu_{k})$は零に収束する非負の点列であり, $ (\vec{\xi}_k,\vec{s}_k)$ $ (\vec{\xi}^{\ast},\vec{s}^{\ast})$に収束する. さて, $ (\vec{\xi}_k,\vec{s}_k)$は(23)の解だったから, $ \vec{\xi}_k > \vec{0}$, $ \vec{s}_k> \vec{0}$であり, よって, $ \vec{\xi}^{\ast} \geq \vec{0}$, $ \vec{s}^{\ast} \geq \vec{0}$である. また, $ \vec{\xi}_k^T \vec{s}_k=n \mu_k$で, $ \mu_k$が零に収束するから, $ (\vec{\xi}^{\ast})^T\vec{s}^{\ast}=0$となる. さらに, $ \vec{s}_k = \vec{M}\vec{\xi}_k+\vec{q}$より, さらに, $ \vec{s}^{\ast} = \vec{M}\vec{\xi}^{\ast}+\vec{q}$である. したがって, $ \vec{\xi}^{\ast}$は(SP)の最適解である. また, 補題3 $ \vec{\xi}_k^T \vec{s}_k=n \mu_k$から,

$\displaystyle \vec{\xi}_k^T \vec{s}^{\ast}+\vec{\xi}^{\ast T} \vec{s}_k = n \mu_k$ (38)

となる.

ここで, $ B=\{j:\xi^{\ast}_j >0 \}$, $ N=\{j:s^{\ast}_j >0\}$と定義する. また, ベクトル $ \vec{\xi}_k$, $ \vec{s}_k$の第$ i$成分を $ \xi_{ki}$, $ s_{ki}$と書く. $ \vec{\xi}^{\ast}\vec{s}^{\ast}=0$より, $ B \cap N= \emptyset$である. また, $ \vec{\xi}^{\ast}$ $ \vec{s}^{\ast}$はそれぞれ $ \vec{\xi}_k$$ \vec{s}_k$の極限だから, ある$ N$が存在し, すべての$ k>N$に対し, $ j \in B$なら $ \xi_{kj}>0$, $ j \in N$なら$ s_{kj}>0$となる. このような$ k$を取り, (38)の両辺を$ \mu_k$で割ると,

$\displaystyle \sum_{j \in N}\frac{\xi_{kj}s_j^{\ast}}{\mu_k} +\sum_{j \in B}\frac{\xi_j^{\ast}s_{kj}}{\mu_k}=n$ (39)

が得られる. (39)の各項に $ \mu_k=\xi_{kj}s_{kj}$を代入し, 続いて$ B$に関する和では$ \xi_{kj}$を消去し, $ N$に関する和では$ s_{kj}$を消去すると,

$\displaystyle \sum_{j \in N}\frac{s_j^{\ast}}{s_{kj}} +\sum_{j \in B}\frac{\xi_j^{\ast}}{\xi_{kj}}=n$ (40)

が得られる. ところで,

$\displaystyle \lim_{k \rightarrow \infty}\frac{s_j^{\ast}}{s_{kj}}=1, \quad
\lim_{k \rightarrow \infty}\frac{\xi_j^{\ast}}{\xi_{kj}}=1
$

だから, (40)により, $ B \cup N=\{1,\ldots,n\}$である. したがって, $ \xi_j^{\ast} =0$なら $ s_j^{\ast}>0$であり, $ s_j^{\ast} =0$なら $ \xi_j^{\ast}>0$である. 以上によって定理が示された. ///

さて, 定理17では 中心パス上に取った点列の極限から強相補解を求めたのであるが, 実はこの極限は一意的であることが示せる. これを証明する ために, 補題を準備する.

補題 18 $ n$個の変数 $ \vec{x}=[x_1,\ldots,n_n]^T$に関する最小化問題

$\displaystyle \min \left \{ \frac{1}{x_1}+\cdots+\frac{1}{x_n} : \vec{1}^T\vec{x} = n, \vec{x} > \vec{0} \right\}$ (41)

の唯一の解は $ \vec{x}=\vec{1}$である.

[証明] 議論の簡単のために, $ f(\vec{x})=1/x_1+\cdots + 1/x_n$とする. また,

\begin{displaymath}
\begin{split}
D &=\{ \vec{x}: \vec{1}^T\vec{x}=n, \vec{x} > ...
...=\{ \vec{x}+\varepsilon \vec{1}: \vec{x} \in D_0 \}
\end{split}\end{displaymath}

とする. ただし, $ \varepsilon$は正の定数である. 以下の議論では, $ D$, $ E$$ n-1$次元空間 $ \{\vec{x}: \vec{1}^T \vec{x}=n \}$ の部分集合とみなす.

$ E$$ f$の定義域$ D$に含まれる有界閉集合である. $ f$$ E$における連続関数であるから, 有限の最大値と最小値を取る. 一方, $ \vec{x} \in E$なら $ \forall i, x_i \geq \varepsilon$であり, したがって $ \vec{x} \in D\backslash E $なら $ \exists i, x_i \leq \varepsilon$, ゆえに, $ f > 1/\varepsilon$である. 一方, $ \vec{1} \in E$であり, $ f$ $ \vec{x}=\vec{1}$における値は $ n$であるので, $ \varepsilon > 0$ を十分小さく取れば, $ f$$ E$における最小値は$ D$における最小値 と考えてよい. また, このことから, $ f$$ E$の境界では最小とならない ことがわかる. よって, $ f$$ E$の内部で最小値を取る.

さて, Lagrange関数$ L$ $ L(\vec{x},\lambda)=f(\vec{x})+\lambda (\vec{1}^T\vec{x}-n)$ によって定義すると, $ f$が 定義域の内点で$ \vec{x}$で最小となるための必要条件は, $ \partial L/\partial \vec{x}=\vec{0}$, $ \partial f/\partial \lambda =0$ である. ところで, $ \partial L/\partial x_i = -1/x_i^2 + \lambda $であるから, $ x_i > 0$ と合わせて, $ \forall i, x_i = \sqrt{\lambda}$かつ $ \lambda > 0$となる. これを $ \partial L/\partial L=\vec{1}^T \vec{x}-n=0$に代入すると $ n \sqrt{\lambda} =n$, すなわち $ \sqrt{\lambda}=1$, したがって $ \forall i, x_i = 1$となる. さて, $ E$において$ f$が最小となる点が少なくとも1個あることは すでにわかっていて, さらに最小となる点の候補は $ \vec{x}=\vec{1}$のみであることから, 実際に$ f$ $ \vec{x}=\vec{1}$において最小値$ n$を取ることがわかる. ///

定理 19 中心パスは $ \mu \rightarrow 0$としたとき唯一の極限に収束する.

[証明] 定理17の証明で述べられた手順によって 得られる集積点が一意的であることをいえばよい. $ \widetilde{\mu}_k \rightarrow 0$, $ \widehat{\mu}_k \rightarrow 0$に対応する点列 $ (\widetilde{\vec{\xi}}_k, \widetilde{\vec{s}}_k)$, $ (\widehat{\vec{\xi}}_k, \widehat{\vec{s}}_k)$ から得られた極限をそれぞれ $ (\widetilde{\vec{\xi}}, \widetilde{\vec{s}})$ および $ (\widehat{\vec{\xi}}, \widehat{\vec{s}})$ とする. このとき, $ \widetilde{\vec{\xi}}^T\widetilde{\vec{s}}=0$, $ \widehat{\vec{\xi}}^T\widehat{\vec{s}}=0$である. 一方, $ (\widetilde{\vec{s}}-\widehat{\vec{s}})^T(\widetilde{\vec{\xi}}-\widehat{\vec{\xi}})$ だから,

$\displaystyle \widetilde{\vec{s}}^T\widehat{\vec{\xi}}+\widetilde{\vec{\xi}}^T\widehat{\vec{s}}=0$ (42)

である. さて, ここで $ \widetilde{B}=\{i: \widetilde{\xi}_i \neq 0\}$, $ \widetilde{N}=\{i: \widetilde{\xi}_i = 0\}$, $ \widehat{B}=\{i: \widehat{\xi}_i \neq 0\}$, $ \widehat{N}=\{i: \widehat{\xi}_i = 0\}$とおく. $ (\widetilde{\vec{\xi}}, \widetilde{\vec{s}})$ および $ (\widehat{\vec{\xi}}, \widehat{\vec{s}})$はともに強相補解であることに注意すると, (42)より, $ i \in \widetilde{B}$なら $ \widetilde{\xi}_i \neq 0$ゆえに $ \widehat{s}_i=0$, したがって $ \widehat{\xi}_i \neq 0$であり, ゆえに $ i \in \widehat{B}$である. 逆に, $ i \in \widehat{B}$なら, $ \widehat{\xi}_i \neq 0$ゆえに $ \widetilde{s}_i =0$, したがって $ \widetilde{\xi}_i \neq 0$, ゆえに $ i \in \widetilde{B}$である. 以上により, $ \widetilde{B}=\widehat{B}$, $ \widetilde{N}=\widehat{N}$である. 以下では, 記号の簡単のために $ B=\widetilde{B}=\widehat{B}$, $ N=\widetilde{N}=\widehat{N}$とおく.

さて, $ (\widetilde{\vec{s}}_{k}-\widehat{\vec{s}})^T(\widetilde{\vec{\xi}}_{k}-\widehat{\vec{\xi}})=0$ より,

$\displaystyle n \widetilde{\mu}_k=\widetilde{\vec{s}}_{k}^T\widehat{\vec{\xi}}+\widetilde{\vec{\xi}}_{k}^T\widehat{\vec{s}}$ (43)

であるが, $ \widetilde{\vec{\xi}}_k$, $ \widetilde{\vec{s}}_k$の第$ i$成分をそれぞれ $ \widetilde{\xi}_{ki}$, $ \widetilde{s}_{ki}$と書くと, (43)は

$\displaystyle \sum_{i \in B} \widehat{\xi}_i\widetilde{s}_{ki} + \sum_{i \in N} \widehat{s}_i\widetilde{\xi}_{ki} = n \widetilde{\mu}_k$ (44)

となる. $ \forall i, \widetilde{s}_{ki} \widetilde{\xi}_{ki}=\widetilde{\mu}_k$だから, (44)の左辺の和の各項を $ \widetilde{s}_{ki} \widetilde{\xi}_{ki}$で割ることにより,

$\displaystyle \sum_{i \in B} \frac{\widehat{\xi}_i}{\widetilde{\xi}_{ki}} + \sum_{i \in N} \frac{\widehat{s}_i}{\widetilde{s}_{ki}} = n$ (45)

となる. (45)において $ k \rightarrow \infty$とすると

$\displaystyle \sum_{i \in B} \frac{\widehat{\xi}_i}{\widetilde{\xi}_{i}} + \sum_{i \in N} \frac{\widehat{s}_i}{\widetilde{s}_{i}} = n$ (46)

が得られる. また, 同様の手順により,

$\displaystyle \sum_{i \in B} \frac{\widetilde{\xi}_i}{\widehat{\xi}_{i}} + \sum_{i \in N} \frac{\widetilde{s}_i}{\widehat{s}_{i}} = n$ (47)

も得られる.

さて, ここで $ x_i = \widehat{\xi}_i/\widetilde{\xi}_{i}   (i \in B)$, $ x_i = \widehat{s}_i/\widetilde{s}_{i}   (i \in N)$とおくと, $ \forall i, x_i > 0$であり, (46), (47)は

$\displaystyle \sum_{i=1}^{n} x_i = n, \quad \sum_{i=1}^{n} \frac{1}{x_i}=n$ (48)

と書ける. 補題18より, (48)が成り立つためには, $ \forall i, x_i = 1$でなければならない. ゆえに, $ \forall i(\widetilde{\xi}_i=\widehat{\xi}_i)$, $ \forall i(\widetilde{s}_i=\widehat{s}_i)$ であり, したがって $ \widetilde{\vec{\xi}}=\widehat{\vec{\xi}}$, $ \widetilde{\vec{s}}=\widehat{\vec{s}}$である. 以上によって集積点が一意的であることが示された. ///

中心パスの極限を解析的中心と呼ぶ. 定理19で示されたように, 解析的中心は一意的に定まる. これに対し, 強相補解は一意とは限らない.

例 20 2変数の歪対称問題

\begin{displaymath}\begin{split}&\min \left \{ \begin{bmatrix}1 \ 0\end{bmatrix...
...} \geq \begin{bmatrix}0 \ 0\end{bmatrix} \right \} \end{split}\end{displaymath} (49)

を考える.

(49)の制約条件は, $ 0 \leq \xi_1$, $ 0 \leq \xi_2 \leq 1$ と書き直される. 目的関数は$ \xi_1$なので, $ \xi_1=0$を満たす任意の点で目的関数は最小となる.

$ f_{\mu}(\vec{\xi})=1$なる等高線 が$ \mu=0.6$, $ 1,0$, $ 1,4$, $ 1.8$としたときに どのように変わるかを図2に示す. 図2より, $ f_{\mu }(\xi )=1$なる等高線 は $ (\xi_1,\xi_2)$空間における閉曲線を定め, $ \mu $が小さくなるにしたがってこの閉曲線が 全体的に左に移動してゆくことがわかる.

図 2: $ f_{\mu }(\xi )=1$を満たす等高線の$ \mu $に対する変化
\includegraphics{f_as_mu.eps}

$ 0 < \theta < 1$なる任意の$ \theta$に対し, $ \vec{x}=[0, \theta]^T$ とすると, $ \vec{x} \geq 0$, $ \vec{s}(\vec{\xi})=[1-\theta,0]^T \geq \vec{0}$で, $ \vec{\xi}^T\vec{s}(\vec{\xi})=0$, $ \vec{\xi}+\vec{s}(\vec{\xi})=[1-\theta,\theta]^T > \vec{0}$ となる. すなわち, このような $ (\vec{\xi},\vec{s}(\vec{\xi}))$は強相補解である.

(49)の中心パスを求めてみよう. $ \vec{\xi}\vec{s}(\vec{\xi})=\mu \vec{1}$を成分ごとに書き下すと,

$\displaystyle \xi_1(1-\xi_2)=\mu,   \xi_1 \xi_2 =\mu$ (50)

となる. (50)の第2式を第1式に代入することにより, $ \xi_1= 2 \mu$が得られる. これを(50)の第2式に代入すると, $ \xi_2=1/2$が得られる. すなわち, (49)の中心パスは

$\displaystyle (\xi_1,\xi_2)=(2 \mu, 1/2),   0 < \mu <\infty$ (51)

を満たす点の集合である. (51)から直ちに, (49)の解析的中心が $ (\xi_1,\xi_2)=(0, 1/2)$である ことがわかる.

(49)の制約条件を満たす領域, 中心パス, 解析的中心と強相補解を 図3に示す.

なお, この例では中心パスは直線であるが, これは偶然であって, ふつうは中心パスは直線にはならない.

図 3: 2次の歪対称問題の中心パスと強相補解
\includegraphics[scale=1]{cp.eps}


next up previous
: 双対定理 : 内点法 : はじめに
Shigeru HANBA 平成25年12月22日