内点法(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$ に比例する評価をもつ。
内点法(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・2・3 を仮定する。
条件 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 の直線に近く、誤差はギャップより小さい。
中心化は等式制約 $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$ の置き換えで制約のない問題に直せるので、ここでは制約のない場合を述べる。
$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}$ である。
$\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〜3 | thm-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)の手順である。
| 状況 | 起こること | 対処 |
|---|---|---|
| $\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$ を必要以上に小さくしない |
$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$ よりずっと小さい。
$\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$ は変数の数=非負制約の数) | ギャップは障壁の項の数で決まる |
BV04 §9.5(Newton 法、pp. 484–496)、§10.2(等式制約つきの Newton 法、pp. 525–531)、第 11 章(障壁法と中心パス、p. 561 から。文献の注は p. 621)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する