5. 内点法 #

5.2. 小史 #

単体法は原理的に明快な側面をもち，且つその計算方法もそれほど難しい手続きを踏むものではない．このため単体法は線形最適化問題の実用的且つ効率的なアルゴリズムとして広く受け入れられてきた．事実，経験的には問題の制約条件数の \(1.5\) 倍から \(3\) 倍程度の反復回数によって計算を終えることができ，問題の規模の増大に対する単体法の計算量の増加は比較的穏やかである．

しかしながら線形最適化問題は多項式時間アルゴリズムではない．実務に当たっては単体法の急所を狙ったような問題に遭遇することは，そうそうあることではなく計算量が爆発的に増大することはないかもしれないが，万全を期するという点で単体法は弱いのである．

そのような背景で Leonid Genrikhovich Khachiyan による 1979 年の初めての多項式時間アルゴリズムである楕円体法を基礎として， 1984 年に Narendra Karmarkar は新しい多項式時間アルゴリズム 内点法 を提案した．内点法は大規模な問題を単体法よりも速く解くことが可能であることを示したのである．

今日では内点法は計算効率について単体法を凌ぐ方法との評価 ¹ ¹小規模であれば単体法が圧倒的に速い．また大規模であっても常に内点法が優位とは限らない．問題というものは時に複雑で数値実験というステップは重要であり続ける (だろう)．が定着し，実用的なソフトウェアが開発されている．そのためオリジナルの Karmarkar の方法とそれに触発されて生まれた多くの方法を総称して内点法と人々は現在よんでいる．

5.3. 内点法の分類 #

単体法は実行可能領域の境界を探索していく方法であったが，内点法は実行可能領域の内部を逐次探索して最適解に到達する方法である．この内部で生成される点列 (逐次探索の方法，最適解への近付き方) をどのように構築していくかで，内点法の分類が行われる．代表例を挙げよう．

²affine スケーリング法とも．affine 変換法は内点法に分類されるが，多項式時間アルゴリズムではない．Karmarkar の 1984 年の発表に先立つこと 1967 年に数学者の I.I.Dikin (ソ連) によって提案されていた．

affine 変換法 [8] ² ²affine スケーリング法とも．affine 変換法は内点法に分類されるが，多項式時間アルゴリズムではない．Karmarkar の 1984 年の発表に先立つこと 1967 年に数学者の I.I.Dikin (ソ連) によって提案されていた．
ポテンシャル減少法
パス追跡法
予測子・修正子法
対数障壁法

これらの方法は主問題，双対問題または両方を取り扱うかで記述のタイプが分かれ，それぞれ主内点法，双対内点法，主双対内点法とよぶ．

主双対最適性条件は内点法の一つであるパス追跡法を主双対内点法の枠組みで説明することができるので，これを基にして内点法についての説明を以下に行う．

5.4. パス追跡法 #

パス追跡法は中心パスという経路を追跡して終端に行き着いたとき，その終端が最適解を与える方法である．ここに中心パスは次の連立式の解曲線 \((\vec{x}(\mu),\vec{\omega}(\mu),\vec{s}(\mu))\) として定義される．

(1)#\[\begin{split}\left \{ \begin{array}{l} \operatorname{Diag}(\vec{x})\operatorname{Diag}(\vec{s})\vec{1} = \mu\vec{1} ~~ (\mu > 0), \\ A\vec{x} = \vec{b}, \\ A^T\vec{\omega} + \vec{s} = \vec{c}, \\ \vec{x} > \vec{0}, \\ \vec{s} > \vec{0} \end{array} \right.\end{split}\]

解曲線は \(\mu\) で目盛付される曲線であり，主双対最適性条件 (51) の対応からわかるように，\(\mu\rightarrow 0\) という極限で解曲線の終端としての最適解に到達する．ここで解曲線の各点をパラメータ \(\mu\) に対する中心という．

(1) では \(\vec{x},\vec{s}\) の非負条件がより厳しい正値条件となっている (それ故，第一式の意味するところである \(s_ix_i=0\) では要求できず正値となる)．

つまり境界が除かれており，この意味で内部の位置を指示していることから内点法の一種とされている．もっと言えば，パス追跡法は \(\mu\rightarrow 0\) に向かって単調に減少し収束する整数列

(2)#\[\mu^{(1)}, \mu^{(2)}, \ldots, \mu^{(k)}, \ldots, 0\]

の各 \(\mu^{(k)}\) に対する中心 \((\vec{x}(\mu^{(k)}),\vec{\omega}(\mu^{(k)}),\vec{s}(\mu^{(k)}))\) を逐次近似的に求めて最適解に迫ろうという方法である．但し近似解を求める際には正値条件が満たされているか注意する．

近似解に頼ろうとするのは \(\operatorname{Diag}(\vec{x})\operatorname{Diag}(\vec{s})\vec{1} = \mu\vec{1}\) が非線形方程式だからに他ならない．近似の方法は線形近似によって行う．ここに線形近似した \(1\) 次方程式を逐次解くことにより，解に収束する点列を生成する反復法を Newton 法という．具体的には次の手順を踏む．

\(k\) 回目の反復によって \(k\) 番目の中心 \((\vec{x}(\mu^{(k)}),\vec{\omega}(\mu^{(k)}),\vec{s}(\mu^{(k)}))\) が得られているとする．
\(k+1\) 番目の中心 \((\vec{x}(\mu^{(k+1)}),\vec{\omega}(\mu^{(k+1)}),\vec{s}(\mu^{(k+1)}))\) は，次で線形近似する．

(3)#\[\begin{split}\begin{bmatrix} \vec{x}(\mu^{(k+1)}) \\ \vec{\omega}(\mu^{(k+1)}) \\ \vec{s}(\mu^{(k+1)}) \end{bmatrix} = \begin{bmatrix} \vec{x}(\mu^{(k)}) + \alpha\Delta\vec{x} \\ \vec{\omega}(\mu^{(k)}) + \alpha\Delta\vec{\omega} \\ \vec{s}(\mu^{(k)}) + \alpha\Delta\vec{s} \end{bmatrix} ~~ (\alpha > 0)\end{split}\]

このとき近似の程度を担う因子 \(\alpha\) は \(k+1\) 番目での正値条件が満足されているように注意しなければならない．具体的な技術的なコメントは後のステップで述べる．
線形近似を行うために中心パスに沿った変化分 \((\Delta\vec{x},\Delta\vec{\omega},\Delta\vec{s})\) を求める．そのために (1) に対して，次を代入し変化分 \((\Delta\vec{x},\Delta\vec{\omega},\Delta\vec{s})\) を求める．

(4)#\[\begin{split}\begin{bmatrix} \vec{x} \\ \vec{\omega} \\ \vec{s} \end{bmatrix} = \begin{bmatrix} \vec{x}(\mu^{(k)}) + \Delta\vec{x} \\ \vec{\omega}(\mu^{(k)}) + \Delta\vec{\omega} \\ \vec{s}(\mu^{(k)}) + \Delta\vec{s} \end{bmatrix}\end{split}\]

解くべき式は解くべき変数について線形(二次の変化量は無視)なので，線形近似の枠内で厳密に且つ容易に解くことができる．
(1) を変化分 \((\Delta\vec{x},\Delta\vec{\omega},\Delta\vec{s})\) について解く．二次の変化量を無視すれば，代入によってまず次のように整理される．整理は左辺に方程式の変数，右辺に定数 \(\vec{p},\vec{q},\vec{r}\) がくるようにした．

(5)#\[\begin{split}\operatorname{Diag}[\vec{s}(\mu^{(k)})]\Delta\vec{x} + \operatorname{Diag}[\vec{x}(\mu^{(k)})]\Delta\vec{s} &= \vec{p}, \\ A\Delta\vec{x} &= \vec{q}, \\ A^T\Delta\vec{\omega} + \Delta\vec{s} &= \vec{r}\end{split}\]

ここで定数 \(\vec{p},\vec{q},\vec{r}\) は次のとおりである．

(6)#\[\begin{split}\vec{p} &= \mu^{(k)}\vec{1} - \operatorname{Diag}[\vec{x}(\mu^{(k)})]\operatorname{Diag}[\vec{s}(\mu^{(k)})]\vec{1}, \\ \vec{q} &= \vec{b} - A\vec{x}(\mu^{(k)}), \\ \vec{r} &= \vec{c} - A^T\vec{\omega}(\mu^{(k)}) - \vec{s}(\mu^{(k)})\end{split}\]

これを解くことは容易いことである．直ちに次の解を得る．

(7)#\[\begin{split}\Delta\vec{x} &= \operatorname{Diag}[\vec{s}(\mu^{(k)})]^{-1} (\vec{p} - \operatorname{Diag}[\vec{x}(\mu^{(k)})]\vec{r} + \operatorname{Diag}[\vec{x}(\mu^{(k)})] A^T \Delta\vec{\omega}), \\ \Delta\vec{s} &= \vec{r} - A^T \Delta\vec{\omega}, \\ \Delta\vec{\omega} &= (A\operatorname{Diag}[\vec{s}(\mu^{(k)})]^{-1}\operatorname{Diag}[\vec{x}(\mu^{(k)})]A^T)^{-1} \{\vec{q} - A\operatorname{Diag}[\vec{s}(\mu^{(k)})]^{-1}(\vec{p} - \operatorname{Diag}[\vec{x}(\mu^{(k)})]\vec{r})\}\end{split}\]

注釈

(3) に現れた \(\alpha\) についての技術的なコメントを述べる．経験的に \(\alpha\) は正値条件が満たされる範囲で十分大きい値に設定することが有効といわれている．

具体的にはまず最大値として次を求める．

(8)#\[\alpha_{\max} := \max \{ \alpha ~|~ \vec{x}(\mu^{(k)}) + \alpha\Delta\vec{x} \geq \vec{0} ,~ \vec{s}(\mu^{(k)}) + \alpha\Delta\vec{s} \geq \vec{0} \}\]

そしてこれを少しだけ縮めた次を採用すればよい．

(9)#\[\alpha = \gamma \alpha_{\max} ~~ (0<\gamma \lesssim 1)\]

ここで \(\gamma\) は十分に \(1\) に近い定数であり， \(\gamma=0.9999\) のように実務にあたって設定を行う．

以上によって，逐次，中心パスに沿った変化分 \((\Delta\vec{x},\Delta\vec{\omega},\Delta\vec{s})\) を求め，点列を辿っていくのがパス追跡法による内点法である．

内点法

目次

5. 内点法 #

5.1. 導入 #

5.2. 小史 #

5.3. 内点法の分類 #

5.4. パス追跡法 #

内点法

目次

5. 内点法#

5.1. 導入#

5.2. 小史#

5.3. 内点法の分類#

5.4. パス追跡法#

5. 内点法 #

5.1. 導入 #

5.2. 小史 #

5.3. 内点法の分類 #

5.4. パス追跡法 #