内点法

同義語:interior-point methodinterior point method

概要

内点法(interior-point method)とは、不等式の制約をもつ最適化問題を、境界で発散する対数障壁を目的関数に足した最小化を重み $t$ を増やしながら Newton 法で繰り返し、実行可能領域の内部を通る点列で解く方法である。標準形の線形計画問題 $\min c^{\mathsf T}x$($Ax=b$、$x\ge0$)では、主問題と双対問題がともに狭義実行可能なら各 $t>0$ に障壁つきの最小点 $x(t)$ がただ 1 つあり、そこから双対問題の実行可能解が得られて双対ギャップは変数の数 $n$ を $t$ で割った $n/t$ に等しい。強凸で Hesse 行列が Lipschitz 連続な関数の Newton 法は最小点の近くで 2 次収束し、全体の Newton 反復の回数は $\sqrt n$ に比例する評価をもつ。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 線形計画法, 凸関数, Newton法

内点法(interior-point method)は、不等式の制約をもつ最適化問題を、実行可能領域の 内部 を通る点列で解く方法の総称である。単体法 が実行可能領域の頂点を辺に沿って渡り歩くのに対し、内点法は境界に近づくと $+\infty$ に発散する 障壁関数 を目的関数に足し、その重みを少しずつ小さくしながら、制約のない(または等式制約だけの)最小化を Newton法 で繰り返す。最小点の軌跡を 中心パス という。
線形計画問題では、中心パスの上の点から双対問題の実行可能解が同時に得られ、両者の目的関数の値の差(双対ギャップ)が障壁の重みに比例して小さくなる。この性質により、止めた時点での誤差が分かる。中心化の Newton 法は、各段で収束が速い領域から始められるように重みを増やせば、少ない反復で済む。線形計画を多項式時間で解く算法の基礎である。
この記事では標準形の線形計画問題について、中心パスの存在と一意性、双対ギャップの公式を証明し、Newton 法の局所 2 次収束を証明する。全体の反復回数が変数の個数の平方根に比例する評価は主張として述べる。制約が非線形の場合の障壁法の精度の評価は 非線形計画法 にある。

定義と使える条件

$A\in\mathbb{R}^{m\times n}$、$b\in\mathbb{R}^m$、$c\in\mathbb{R}^n$ とし、標準形 の線形計画問題(主問題)とその双対問題を
$$ \text{(P)}\quad\min\ c^{\mathsf T}x\ \ \text{条件 }Ax=b,\ x\ge0,\qquad\text{(D)}\quad\max\ b^{\mathsf T}y\ \ \text{条件 }A^{\mathsf T}y+s=c,\ s\ge0 $$
とする(線形計画法 の双対問題)。$p^\ast$ を (P) の最適値とする。ベクトルの不等式は成分ごとの不等式、$x>0$ は全ての成分が正であることを表す。

対数障壁と中心パス

$t>0$ に対し、$F^\circ=\{x\in\mathbb{R}^n\mid Ax=b,\ x>0\}$ の上の関数
$$ B_t(x)=t\,c^{\mathsf T}x-\sum_{i=1}^n\log x_i $$
を 対数障壁つきの目的関数 という。$B_t$ の $F^\circ$ での最小点を $x(t)$ と書き、$\{x(t)\mid t>0\}$ を 中心パス、$x(t)$ を 中心点 という。$x(t)$ を求める最小化を 中心化 という。

$-\log x_i$ は $x_i\to0$ で $+\infty$ に発散するので、最小点は境界から離れた内部にある。$t$ が小さいうちは障壁が勝って領域の「中心」に近く、$t$ が大きくなると $c^{\mathsf T}x$ の項が勝って最適解に近づく。
この記事の結論を使える条件をまとめる。

  1. 主問題の狭義実行可能性:$Ax=b$、$x>0$ を満たす $x$ がある($F^\circ\ne\emptyset$)。
  2. 双対問題の狭義実行可能性:$A^{\mathsf T}y+s=c$、$s>0$ を満たす $(y,s)$ がある。
  3. $A$ の行が 1 次独立(階数 $m$):双対変数 $y$ の一意性に使う。
  4. Newton 法の局所理論:目的関数が 2 回連続微分可能で、強凸(Hesse 行列 $\succeq\kappa I$、$\kappa>0$)、Hesse 行列が Lipschitz 連続であり、初期値が最小点に十分近い(thm-ipm-newton)。
    条件 1・2 のどちらかが欠けると中心パスは存在しない(節「使える条件と反例」)。条件 2 が必要なことは、prf-ipm-path の 2 が条件 2 を使わずに「障壁つきの最小点があれば双対問題の狭義実行可能解ができる」ことを示している点から分かる。

主定理:中心パスと双対ギャップ

中心パスの存在と双対ギャップ

条件 1・2・3 を仮定する。

  1. 各 $t>0$ について $B_t$ は $F^\circ$ でただ 1 つの最小点 $x(t)$ をもつ。
  2. $s(t)_i=\dfrac1{t\,x(t)_i}$ とおくと、$A^{\mathsf T}y+s(t)=c$ を満たす $y=y(t)$ がただ 1 つあり、$(y(t),s(t))$ は (D) の狭義実行可能解である。
  3. 双対ギャップは
    $$ c^{\mathsf T}x(t)-b^{\mathsf T}y(t)=\frac nt $$
    で、$c^{\mathsf T}x(t)-p^\ast\le\dfrac nt$、$p^\ast-b^{\mathsf T}y(t)\le\dfrac nt$ である。
  4. $t\to\infty$ のとき $x(t)$ は有界で、その集積点はいずれも (P) の最適解である。
双対の内点で障壁を下から抑える

条件 2 の点を $(\bar y,\bar s)$ とする。
1. 存在と一意性。 $x\in F^\circ$ について $c^{\mathsf T}x=(A^{\mathsf T}\bar y+\bar s)^{\mathsf T}x=b^{\mathsf T}\bar y+\bar s^{\mathsf T}x$ なので
$$ B_t(x)=t\,b^{\mathsf T}\bar y+\sum_{i=1}^n\bigl(t\bar s_ix_i-\log x_i\bigr) $$
である。1 変数の関数 $\phi_i(u)=t\bar s_iu-\log u$($u>0$)は $u=1/(t\bar s_i)$ で最小値 $1+\log(t\bar s_i)$ をとり、$u\to0$ でも $u\to\infty$ でも $+\infty$ に発散する。$x^0\in F^\circ$ を 1 つとり、$K=\{x\in F^\circ\mid B_t(x)\le B_t(x^0)\}$ とおく。$x\in K$ なら、各 $i$ について $\phi_i(x_i)$ は $B_t(x^0)-t\,b^{\mathsf T}\bar y$ からほかの $\phi_j$ の最小値を引いた定数以下なので、$x_i$ はある区間 $[\varepsilon,M]$($\varepsilon>0$)に入る。よって $K$ は $\mathbb{R}^n$ の有界閉集合で、連続な $B_t$ は $K$ で最小値をとり、それが $F^\circ$ での最小値である。$-\log$ は狭義凸なので $B_t$ は $F^\circ$ で狭義凸で、最小点は 1 つである。
2. 双対の点。 $x=x(t)$ は内部の点なので、$Ah=0$ を満たす任意の $h$ について $\tau\mapsto B_t(x+\tau h)$ は $\tau=0$ の近くで定義され、$\tau=0$ で最小である。よって $\nabla B_t(x)^{\mathsf T}h=0$ で、$\nabla B_t(x)=tc-(1/x_i)_i$ は $\ker A$ の直交補空間、すなわち $A^{\mathsf T}$ の値域に入る:$tc-(1/x_i)_i=A^{\mathsf T}w$。$y=w/t$ とおくと $A^{\mathsf T}y+s(t)=c$ で、$s(t)>0$ である。$A$ の行が 1 次独立なので $A^{\mathsf T}$ は単射で、$y$ は一意である。
3. ギャップ。 $Ax=b$ と $A^{\mathsf T}y=c-s$ から
$$ c^{\mathsf T}x-b^{\mathsf T}y=c^{\mathsf T}x-(Ax)^{\mathsf T}y=x^{\mathsf T}(c-A^{\mathsf T}y)=x^{\mathsf T}s=\sum_{i=1}^nx_i\cdot\frac1{t\,x_i}=\frac nt $$
である。(P) の任意の実行可能解 $x'$ について、同じ計算で $c^{\mathsf T}x'-b^{\mathsf T}y=x'^{\mathsf T}s\ge0$ である(弱双対性)。よって $b^{\mathsf T}y\le p^\ast\le c^{\mathsf T}x$ で、2 つの不等式を得る。
4. 極限。 $t\ge1$ なら 3 から $c^{\mathsf T}x(t)\le p^\ast+n$ で、1 の式から $\bar s^{\mathsf T}x(t)=c^{\mathsf T}x(t)-b^{\mathsf T}\bar y\le p^\ast+n-b^{\mathsf T}\bar y$ である。$\bar s>0$、$x(t)>0$ なので $x(t)$ の各成分は有界である。集積点 $x^\ast$ は $Ax^\ast=b$、$x^\ast\ge0$ を満たし、3 から $c^{\mathsf T}x^\ast=p^\ast$ である。$\square$

2 の条件 $x_is_i=\frac1t$ は、最適性の 相補性条件 $x_is_i=0$(線形計画法 の定理「相補性条件」)を $\frac1t$ にゆるめたものである。$x(t)$ と $(y(t),s(t))$ の組を 主双対の中心点 という。止める時点を決めるには、双対ギャップ $\frac nt$ が許容誤差 $\varepsilon$ より小さくなればよい。
図: 左は x1+x2≤4、-x1+x2≤2、x1≤3、x≥0 の五角形の上で -x1-2x2 を最小にする問題の中心パス。解析的中心(約 (1.32, 0.98))から出て、t=1、10、100 の点を通り、最適な頂点 (1,3) に近づく。右は 2 変数の例題で、双対ギャップ 2/t と目的関数の誤差を t に対して両対数で描いたもの。どちらも傾き -1 の直線に近く、誤差はギャップより小さい。 図: 左は x1+x2≤4、-x1+x2≤2、x1≤3、x≥0 の五角形の上で -x1-2x2 を最小にする問題の中心パス。解析的中心(約 (1.32, 0.98))から出て、t=1、10、100 の点を通り、最適な頂点 (1,3) に近づく。右は 2 変数の例題で、双対ギャップ 2/t と目的関数の誤差を t に対して両対数で描いたもの。どちらも傾き -1 の直線に近く、誤差はギャップより小さい。

Newton 法による中心化

中心化は等式制約 $Ax=b$ つきの凸関数の最小化で、Newton 法で解く。$x\in F^\circ$ で $B_t$ を 2 次の Taylor 多項式で近似し、$A\Delta x=0$ の下で最小にすると、Newton 方向 $\Delta x$ は
$$ \begin{pmatrix}X^{-2}&A^{\mathsf T}\\A&0\end{pmatrix}\begin{pmatrix}\Delta x\\w\end{pmatrix}=\begin{pmatrix}-(tc-X^{-1}\mathbf{1})\\0\end{pmatrix} $$
の解である。$X=\operatorname{diag}(x_1,\dots,x_n)$、$\mathbf{1}=(1,\dots,1)^{\mathsf T}$ で、$X^{-2}$ は $B_t$ の Hesse 行列である。$\lambda^2=\Delta x^{\mathsf T}X^{-2}\Delta x$ を Newton 減少量 の 2 乗といい、$\frac12\lambda^2$ は 2 次の近似で見込める目的関数の減少量である(BV04 §10.2、p. 527)。収束の速さは次の局所理論で分かる。等式制約は、$\ker A$ の基底を列にもつ行列 $F$ と $x=\hat x+Fz$ の置き換えで制約のない問題に直せるので、ここでは制約のない場合を述べる。

Newton 法の局所 2 次収束

$S\subset\mathbb{R}^n$ を凸な開集合、$f:S\to\mathbb{R}$ を 2 回連続微分可能とし、定数 $\kappa,L>0$ について、全ての $x,z\in S$ で
$$ \nabla^2f(x)\succeq\kappa I,\qquad\lvert\nabla^2f(x)-\nabla^2f(z)\rvert_{\mathrm{op}}\le L\lvert x-z\rvert $$
とする($\lvert x\rvert$ は Euclid ノルム、$\lvert M\rvert_{\mathrm{op}}$ は行列の作用素ノルム)。$x\in S$、$x^+=x-\nabla^2f(x)^{-1}\nabla f(x)$ で、線分 $[x,x^+]$ が $S$ に入るなら
$$ \lvert\nabla f(x^+)\rvert\le\frac L{2\kappa^2}\lvert\nabla f(x)\rvert^2 $$
である。したがって、Newton 法の点列 $x_0,x_1,\dots$ が線分ごと $S$ に留まり、$q=\frac L{2\kappa^2}\lvert\nabla f(x_0)\rvert<1$ なら、$\lvert\nabla f(x_k)\rvert\le\frac{2\kappa^2}Lq^{2^k}$ である。

積分形の Taylor の公式

$\Delta=x^+-x=-\nabla^2f(x)^{-1}\nabla f(x)$ とおく。$\nabla f(x)+\nabla^2f(x)\Delta=0$ なので、微分積分学の基本定理 を $\tau\mapsto\nabla f(x+\tau\Delta)$($0\le\tau\le1$、線分は $S$ に入る)に当てると
$$ \nabla f(x^+)=\nabla f(x)+\int_0^1\nabla^2f(x+\tau\Delta)\Delta\,d\tau=\int_0^1\bigl(\nabla^2f(x+\tau\Delta)-\nabla^2f(x)\bigr)\Delta\,d\tau $$
である。Lipschitz 条件から被積分関数の長さは $L\tau\lvert\Delta\rvert^2$ 以下で、積分すると $\lvert\nabla f(x^+)\rvert\le\frac L2\lvert\Delta\rvert^2$ である。$\nabla^2f(x)\succeq\kappa I$ から $\nabla^2f(x)^{-1}$ の作用素ノルムは $\frac1\kappa$ 以下なので $\lvert\Delta\rvert\le\frac1\kappa\lvert\nabla f(x)\rvert$ で、主張の不等式を得る。
$g_k=\frac L{2\kappa^2}\lvert\nabla f(x_k)\rvert$ とおくと $g_{k+1}\le g_k^2$ で、$g_0=q$ から帰納法で $g_k\le q^{2^k}$ である。$\square$

強凸性から、最小点 $x^\ast$ との距離は $\lvert x_k-x^\ast\rvert\le\frac1\kappa\lvert\nabla f(x_k)\rvert$ で抑えられる。$q^{2^k}$ は正しい桁数が 1 回ごとに約 2 倍になることを表す。この評価は BV04 §9.5.3(pp. 488–489)の 2 次収束の段階に当たる。遠くの初期値からは、直線探索で歩幅を縮める 減衰 Newton 法 で近づく。
障壁法では、前の中心点 $x(t)$ を次の $t'=\mu t$ の中心化の初期値に使う。$\mu$ が 1 に近ければ $x(t)$ は $x(t')$ に近く、Newton 法は少ない反復で済む。

反復回数の評価

標準形の線形計画問題で条件 1・2・3 を仮定する(このとき (P) の実行可能解で $c^{\mathsf T}x\le\alpha$ を満たすものの集合は有界である)。$t$ を $\mu=1+\frac1{\sqrt n}$ 倍ずつ増やす障壁法(直線探索つきの Newton 法で中心化する)は、最初の中心化のあと、双対ギャップを $\frac n{t_0}$ から $\varepsilon$ まで減らすのに
$$ O\Bigl(\sqrt n\,\log\frac n{t_0\varepsilon}\Bigr) $$
回の Newton 反復で足りる。$O$ の定数は直線探索の定数と中心化の許容誤差だけにより、問題の係数 $A,b,c$ にはよらない。

証明の所在

この記事では証明しない。$B_t$ が 自己整合 関数(どの直線に制限しても $\lvert g'''\rvert\le2(g'')^{3/2}$ を満たす凸関数、BV04 §9.6.1、pp. 497–498)であることを使う評価で、BV04 §11.5(仮定は p. 586、評価の式 (11.29) は p. 591)にある。有界性は prf-ipm-path の 4 と同じ議論による。障壁法が 1980 年代に再び注目されたのは、Karmarkar(1984)による線形計画問題の多項式時間の射影的な算法との近い関係が指摘されたことによる(BV04 第 11 章の文献の注、p. 621)。

公式の表

量式使える条件根拠
障壁つきの目的関数$B_t(x)=t\,c^{\mathsf T}x-\sum_i\log x_i$$Ax=b$、$x>0$def-ipm-central
中心点の条件$Ax=b$、$A^{\mathsf T}y+s=c$、$x_is_i=\frac1t$、$x,s>0$条件 1〜3thm-ipm-path
双対ギャップ$c^{\mathsf T}x(t)-b^{\mathsf T}y(t)=\frac nt$同上thm-ipm-path
誤差の上界$c^{\mathsf T}x(t)-p^\ast\le\frac nt$同上thm-ipm-path
Newton 方向$X^{-2}\Delta x+A^{\mathsf T}w=-(tc-X^{-1}\mathbf{1})$、$A\Delta x=0$$x\in F^\circ$節「Newton 法による中心化」
双対変数の推定$y\approx-\frac wt$(中心点で等号)同上prf-ipm-path の 2
2 次収束$\lvert\nabla f(x^+)\rvert\le\frac L{2\kappa^2}\lvert\nabla f(x)\rvert^2$強凸、Hesse 行列が Lipschitz、線分が $S$ に入るthm-ipm-newton
外側の反復の回数$\bigl\lceil\log(n/(t_0\varepsilon))/\log\mu\bigr\rceil$$t$ を $\mu$ 倍ずつ増やす双対ギャップの式
全体の反復回数$O(\sqrt n\log(n/(t_0\varepsilon)))$$\mu=1+\frac1{\sqrt n}$thm-ipm-complexity(証明しない)

外側の反復の回数は、$k$ 回目の $t$ が $\mu^kt_0$ で、$\frac n{\mu^kt_0}\le\varepsilon$ となる最小の $k$ を数えたものである(最初の中心化を除く)。

計算の手順

障壁法(BV04 Algorithm 11.1、p. 569)の手順である。

  1. 狭義実行可能な初期点を作る。 $Ax=b$、$x>0$ の点 $x$ を求める。見つからなければ、補助の変数を足した問題(第 1 段の問題)を同じ方法で解く。
  2. 定数を決める。 $t_0>0$、$\mu>1$(実用では $10$ から $100$ 程度)、許容誤差 $\varepsilon$ と、中心化の許容誤差 $\varepsilon_{\mathrm{nt}}$ を決める。
  3. 中心化する。 現在の $x$ から Newton 方向を解き、歩幅 $\alpha$ を $x+\alpha\Delta x>0$ となる範囲で、$B_t$ が十分減るまで半分ずつ縮める(直線探索)。$\frac12\lambda^2\le\varepsilon_{\mathrm{nt}}$ になったら止める。
  4. 止める判定。 $\frac nt<\varepsilon$ なら $x$ と $y=-\frac wt$ を返して止める。
  5. $t$ を増やす。 $t\leftarrow\mu t$ として 3 に戻る。
    状況起こること対処
    $\mu$ が大きい外側の反復は少ないが、中心化 1 回の Newton 反復が増える$\mu=10$〜$100$ がふつうよく働く
    $\mu$ が 1 に近い中心化は 1〜2 回で済むが、外側の反復が増えるthm-ipm-complexity の $\mu=1+\frac1{\sqrt n}$ は理論の評価のための値
    歩幅 $1$ で $x$ の成分が負になる定義域から出る3 の歩幅の制限(ex-ipm-newton-1d)
    $t$ が非常に大きいHesse 行列 $X^{-2}$ の条件数が大きくなる$\varepsilon$ を必要以上に小さくしない

例題

1 変数の中心化

$f(x)=x-\log x$($x>0$)を最小にする。これは問題「$x$ を $x\ge0$ の下で最小にする」の $t=1$ の中心化で、最小点は $x=1$ である。
使う公式:Newton 法 $x^+=x-f'(x)/f''(x)$、thm-ipm-newton。
答え:Newton 法は $x^+=2x-x^2$ で、誤差 $e=1-x$ は $e^+=e^2$ を満たす。$x_0=\frac12$ から $\frac34,\frac{15}{16},\frac{255}{256},\frac{65535}{65536}\approx0.9999847$ で、誤差は $0.5,0.25,0.0625,0.0039,1.5\times10^{-5}$ である。$S=(\frac12,\frac32)$ では $\kappa=\frac49$、$L=16$ で、$x_0=1.02$ なら $q\approx0.794<1$ となり定理が当てはまる。

途中の計算を開く

$f'(x)=1-\frac1x$、$f''(x)=\frac1{x^2}$ なので $x^+=x-(1-\frac1x)x^2=2x-x^2$、$1-x^+=(1-x)^2$。$S$ で $f''\ge\frac1{(3/2)^2}=\frac49$、$\lvert f'''\rvert=\frac2{x^3}\le\frac2{(1/2)^3}=16$。$x_0=1.02$ で $\lvert f'(x_0)\rvert=\frac{0.02}{1.02}\approx0.0196$、$q=\frac{16}{2(4/9)^2}\times0.0196\approx0.794$。実際の $\lvert f'(x_k)\rvert$ は $4.0\times10^{-4}$、$1.6\times10^{-7}$、$2.6\times10^{-14}$ で、評価 $\frac{2\kappa^2}Lq^{2^k}$ の $0.0156$、$0.0098$、$0.0039$ よりずっと小さい。

2 変数の中心パス

$\min\ x_1+2x_2$、条件 $x_1+x_2=1$、$x\ge0$($n=2$、$p^\ast=1$)の中心パスを求める。
使う公式:thm-ipm-path。
答え:
$$ x_1(t)=\frac{t-2+\sqrt{t^2+4}}{2t},\quad x_2(t)=1-x_1(t),\quad y(t)=1-\frac1{t\,x_1(t)} $$

$t$$x_1(t)$$y(t)$双対ギャップ$c^{\mathsf T}x(t)-p^\ast$
$1$$0.618034$$-0.618034$$2$$0.381966$
$10$$0.909902$$0.890098$$0.2$$0.090098$
$100$$0.990100$$0.989900$$0.02$$0.009900$
途中の計算を開く

$x_1=u$、$x_2=1-u$ とおくと $B_t=t(2-u)-\log u-\log(1-u)$ で、$B_t'=-t-\frac1u+\frac1{1-u}=0$ から $tu^2+(2-t)u-1=0$。$(0,1)$ の根が上の式である。双対は $\max y$、条件 $y+s_1=1$、$y+s_2=2$ で、$s_1=\frac1{tu}$ から $y=1-\frac1{tu}$。このとき $s_2=2-y=1+\frac1{tu}$ が $\frac1{t(1-u)}$ と一致することは 2 次方程式と同値である。ギャップは $(2-u)-y=1-u+\frac1{tu}$ で、2 次方程式を使うと $\frac2t$ になる。

五角形の上の障壁法

$\min\ -x_1-2x_2$、条件 $x_1+x_2\le4$、$-x_1+x_2\le2$、$x_1\le3$、$x\ge0$ を、余裕の変数 3 個を足した標準形($n=5$)にして、$t_0=1$、$\mu=10$、$\varepsilon=10^{-6}$、初期点 $(x_1,x_2)=(1,1)$ で障壁法を走らせる。中心化は $\frac12\lambda^2\le10^{-12}$ で止め、直線探索は歩幅を半分ずつにする。
答え:最適解は頂点 $(1,3)$、$p^\ast=-7$ である。外側の反復は 8 回、Newton 反復は合計 49 回(1 回の中心化で 6〜7 回)であった。

$t$$(x_1,x_2)$$c^{\mathsf T}x$双対ギャップ
$1$$(1.42117,\,2.01795)$$-5.45707$$5$
$10$$(1.06820,\,2.86680)$$-6.80179$$0.5$
$100$$(1.00669,\,2.98666)$$-6.98001$$0.05$
$10^7$$(1.00000,\,3.00000)$$-6.9999998$$5\times10^{-7}$

中心パスは図の左の曲線である。$t\to0$ の極限は、障壁だけを最小にする 解析的中心 $(1.3207,\,0.9830)$ である。

使える条件と反例

各行は、thm-ipm-path か thm-ipm-newton の仮定を 1 つだけ外す。

外す仮定反例成り立たなくなること
主問題の狭義実行可能性$\min x_2$、条件 $x_1=0$、$x\ge0$($A=(1\ 0)$)。双対は $s=(-y,1)$ で $y<0$ なら狭義実行可能$x>0$ の実行可能解がなく、$B_t$ の定義域が空。最適値 $0$ はあるが中心パスはない
双対問題の狭義実行可能性$\min 0$、条件 $x_1-x_2=0$、$x\ge0$。$x=(1,1)$ は狭義実行可能。双対は $s=(-y,y)$ で両方は正にならない$B_t(u,u)=-2\log u\to-\infty$($u\to\infty$)で最小点がない。最適値 $0$ はある
$A$ の行の 1 次独立性ex-ipm-path の制約を 2 回書く:$A=\begin{pmatrix}1&1\\1&1\end{pmatrix}$、$b=(1,1)$$x(t)$ は同じだが、$y_1+y_2$ しか決まらず $y(t)$ が一意でない
強凸性($\kappa>0$)$f(x)=x^4$最小点 $0$ で $f''=0$。Newton 法は $x^+=\frac23x$ で 1 次収束にとどまる($1,0.667,0.444,\dots$)
初期値が近いこと($q<1$)$f(x)=x-\log x$、$x_0=2.5$歩幅 $1$ の Newton 法は $x_1=-1.25$ で定義域の外に出る

よくある誤り

誤り正しくはなぜ
中心化を毎回最後まで正確に解く中心化は粗くてよく、前の中心点から始める精度はギャップ $\frac nt$ で決まり、中心化の誤差は次の $t$ で直される
歩幅 $1$ の Newton 法をそのまま使う歩幅を $x>0$ と十分な減少で制限する反例の表の最後の行
止める判定に $x$ の変化だけを使う双対ギャップ $\frac nt$(または $x^{\mathsf T}s$)で止めるギャップは誤差の上界を与える(thm-ipm-path の 3)
内点法の解を頂点だとみなす中心パスの点は内部にあり、頂点の解が欲しければ丸めるか単体法で仕上げるex-ipm-barrier の $x$ は表のどの $t$ でも $x_1>1$
双対ギャップを $\frac mt$($m$ は制約式の数)とする標準形では $\frac nt$($n$ は変数の数=非負制約の数)ギャップは障壁の項の数で決まる

補足

主双対内点法と一般の凸最適化

実用の算法の多くは、中心点の条件 $Ax=b$、$A^{\mathsf T}y+s=c$、$x_is_i=\frac1t$ の 3 つを $(x,y,s)$ について同時に Newton 法で解き、中心化を 1 歩で打ち切る 主双対内点法 である(BV04 §11.7、p. 609)。障壁 $-\sum\log x_i$ の代わりに $-\sum\log(-f_i(x))$ を使えば、凸な不等式制約の問題に同じ枠組みが使え、精度は $\frac{(\text{制約の数})}t$ で抑えられる(非線形計画法 の定理「障壁法の精度」)。半正定値計画では $-\log\det X$ を障壁にする。

文献

BV04 §9.5(Newton 法、pp. 484–496)、§10.2(等式制約つきの Newton 法、pp. 525–531)、第 11 章(障壁法と中心パス、p. 561 から。文献の注は p. 621)。

関連項目

参考文献

[1]
Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004, §9.5.3(pp. 488–489)、§9.6.1(pp. 497–498)、§10.2(p. 527)、§11.2.2(pp. 564–566)、Algorithm 11.1(p. 569)、§11.5(pp. 585–592、式 (11.29) は p. 591)、§11.7(p. 609)、第 11 章の文献の注(p. 621)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する