楕円体法(ellipsoid method)とは、凸集合の点を探す問題や凸集合の上で凸関数を最小にする問題を、楕円体を縮めながら解く反復法で、中心が集合の外なら分離する超平面で、中心が集合の中なら劣勾配で楕円体を半分に切り、残した半楕円体を含む新しい楕円体で包み直す。$n\ge2$ 次元では 1 回ごとに体積が $e^{-1/(2(n+1))}$ 倍未満になるので、集合が半径 $r$ の球を含み半径 $R$ の球に含まれるなら、誤差は回数 $T$ について $(R/r)e^{-T/(2n(n+1))}$ に比例して減る。Shor と Yudin–Nemirovskii が凸最適化のために導き、Khachiyan はこれで線形計画問題が多項式時間で解けることを示した。
楕円体法(ellipsoid method)は、凸集合 $K\subset\mathbb R^n$ の点を探す問題や、$K$ の上で凸関数を最小にする問題を、楕円体を少しずつ縮めて解く反復法である。いま見ている楕円体の中心が $K$ の外なら、中心を通る超平面で $K$ を含む側の半分を残す。中心が $K$ の中なら、関数の劣勾配で「値が中心より小さくなりうる側」の半分を残す。残した半楕円体をそれを含む新しい楕円体で包み直すと、体積は毎回 $e^{-1/(2(n+1))}$ 倍未満になる(thm-ell-half)。体積が小さくなり続けるので、$K$ が半径 $r$ の球を含み半径 $R$ の球に含まれるなら、反復の回数は $n^2\log(R/r)$ の程度で済み、誤差は回数について指数的に減る(thm-ell-main)。
この方法は、凸関数の微分できない最適化の研究から Shor と Yudin–Nemirovskii が導き、Khachiyan がこれを使って 線形計画法 の問題が多項式時間で解けることを示した(GLS88 pp. 64–65)。実用の速さでは 単体法 や 内点法 に及ばないが、制約を 1 つずつ問い合わせる「分離オラクル」だけで動くので、制約が指数個ある問題や 半正定値計画 が多項式時間で解けることを示す理論の道具になる。
この記事では、半楕円体を包む楕円体の式と体積の比を証明し、それを使って実行可能な点を見つけるまでの回数と、凸関数の最小化の誤差の評価を証明する。
$n$ 次の実対称な 正定値行列 $A$ と $a\in\mathbb R^n$ について
$$
E(A,a):=\bigl\{x\in\mathbb R^n\bigm|(x-a)^\top A^{-1}(x-a)\le1\bigr\}
$$
を 楕円体 といい、$a$ をその 中心 という。
$A^{1/2}$ を $A$ の正定値な平方根とすると、$y=A^{-1/2}(x-a)$ の変換で $E(A,a)$ は単位球 $B:=\{y\mid\lvert y\rvert\le1\}$ に移る。すなわち $E(A,a)=a+A^{1/2}B$ である。これは単位球の 1 次変換の像なので、体積は
$$
\operatorname{vol}E(A,a)=\det A^{1/2}\cdot V_n=\sqrt{\det A}\,V_n\qquad(V_n:=\operatorname{vol}B)
$$
である(行列式 は 1 次変換による体積の倍率)。$A=R^2I$ なら $E(A,a)$ は中心 $a$、半径 $R$ の球 $B(a,R)$ である。また $g\in\mathbb R^n$ について、$x=a+A^{1/2}y$ と書くと $\langle g,x-a\rangle=\langle A^{1/2}g,y\rangle$ なので、Cauchy–Schwarzの不等式 から
$$
\max_{x\in E(A,a)}\langle g,x\rangle=\langle g,a\rangle+\sqrt{g^\top Ag}
$$
である。
$n\ge2$、$E=E(A,a)$ を楕円体、$g\in\mathbb R^n$、$g\ne0$ とし、
$$
b:=\frac{Ag}{\sqrt{g^\top Ag}},\qquad a':=a-\frac1{n+1}b,\qquad A':=\frac{n^2}{n^2-1}\Bigl(A-\frac2{n+1}bb^\top\Bigr)
$$
とおく。このとき $A'$ は正定値で、
$Q:=A^{1/2}$ とし、$u:=Qg/\lvert Qg\rvert$ とおく。$\lvert Qg\rvert^2=g^\top Ag$ なので $u$ は長さ $1$ で、$b=Q(Qg)/\lvert Qg\rvert=Qu$ である。
単位球の場合。 対称行列 $M:=\frac{n^2}{n^2-1}\bigl(I-\frac2{n+1}uu^\top\bigr)$ を考える。$M$ は $u$ を固有値 $\frac{n^2}{n^2-1}\cdot\frac{n-1}{n+1}=\frac{n^2}{(n+1)^2}$ の固有ベクトルにもち、$u$ に直交する部分空間の上では $\frac{n^2}{n^2-1}$ 倍である。どちらも正なので $M$ は正定値で、
$$
M^{-1}=\Bigl(\frac{n+1}n\Bigr)^2uu^\top+\frac{n^2-1}{n^2}\bigl(I-uu^\top\bigr)
$$
である。$\lvert y\rvert\le1$、$\langle u,y\rangle\le0$ をみたす $y$ をとり、$s:=\langle u,y\rangle\in[-1,0]$、$w:=y-su$ とおくと、$\lvert w\rvert^2=\lvert y\rvert^2-s^2\le1-s^2$ である。$y+\frac1{n+1}u=(s+\frac1{n+1})u+w$ なので
$$
\begin{aligned}
\Bigl(y+\tfrac{u}{n+1}\Bigr)^\top M^{-1}\Bigl(y+\tfrac{u}{n+1}\Bigr)&=\Bigl(\frac{n+1}n\Bigr)^2\Bigl(s+\frac1{n+1}\Bigr)^2+\frac{n^2-1}{n^2}\lvert w\rvert^2\\
&\le\frac{(n+1)^2s^2+2(n+1)s+1+(n^2-1)(1-s^2)}{n^2}=1+\frac{2(n+1)s(s+1)}{n^2}\le1
\end{aligned}
$$
である(最後は $-1\le s\le0$ から $s(s+1)\le0$)。よって $B\cap\{y\mid\langle u,y\rangle\le0\}\subset E(M,-\frac u{n+1})$ である。
一般の場合。 $x=a+Qy$ と書く。$x\in E$ は $\lvert y\rvert\le1$ と同値で、$\langle g,x-a\rangle=\langle Qg,y\rangle=\lvert Qg\rvert\langle u,y\rangle$ なので、$\langle g,x-a\rangle\le0$ は $\langle u,y\rangle\le0$ と同値である。また $x-a'=Q\bigl(y+\frac u{n+1}\bigr)$($a'=a-\frac1{n+1}Qu$)なので
$$
(x-a')^\top(QMQ)^{-1}(x-a')=\Bigl(y+\tfrac u{n+1}\Bigr)^\top M^{-1}\Bigl(y+\tfrac u{n+1}\Bigr)
$$
であり、$QMQ=\frac{n^2}{n^2-1}\bigl(A-\frac2{n+1}Qu(Qu)^\top\bigr)=A'$ である。$A'$ は正定値な $M$ と合同なので正定値で、前段から 1 を得る。
体積。 $\det A'=(\det Q)^2\det M=\det A\cdot\Bigl(\frac{n^2}{n^2-1}\Bigr)^{n-1}\frac{n^2}{(n+1)^2}$ なので、体積の式から 2 の等号を得る。$x\ne0$ で $1+x< e^x$ であることを $x=-\frac1{n+1}$ と $x=\frac1{n^2-1}$ に使うと
$$
\frac n{n+1}\Bigl(\frac{n^2}{n^2-1}\Bigr)^{(n-1)/2}< \exp\Bigl(-\frac1{n+1}+\frac{n-1}{2(n^2-1)}\Bigr)=\exp\Bigl(-\frac1{n+1}+\frac1{2(n+1)}\Bigr)=e^{-1/(2(n+1))}
$$
である。$\square$
新しい中心 $a'$ は、元の中心から、残す側の最も遠い点 $a-b$($\langle g,x\rangle$ を $E$ の上で最小にする点)へ向かって $\frac1{n+1}$ だけ進んだ点である。$E'$ は半楕円体を含む楕円体のうち体積が最小のものである(GLS88 p. 70 の式 (3.1.11)・(3.1.12))が、以下の議論で使うのは 1 の包含と 2 の体積の比だけである。GLS88 Lemma (3.1.34)(p. 77)は同じ比が $e^{-1/(2n)}$ 未満であることを示している。$n=2$ では比は $\frac4{3\sqrt3}\approx0.770$ である。$n=1$ では半分の区間はそれ自身が区間なので、体積(長さ)は毎回ちょうど半分になる。これは二分法である。
$K\subset\mathbb R^n$ を凸集合とする。点 $y\in\mathbb R^n$ を受け取り、$y\in K$ ならそう答え、$y\notin K$ なら
$$
\langle g,x-y\rangle\le0\qquad(\text{すべての }x\in K)
$$
をみたす $g\ne0$ を返す手続きを、$K$ の 分離オラクル という。
$K$ が閉凸集合なら、分離オラクルが返すべき $g$ はいつも存在する。$y\notin K$ に最も近い $K$ の点を $p$ とし $g:=y-p$ とおくと、最短点の性質 $\langle y-p,x-p\rangle\le0$($x\in K$)から $\langle g,x-y\rangle=\langle g,x-p\rangle-\lvert g\rvert^2< 0$ である。$K=\{x\mid Cx\le d\}$ のように不等式で与えられた集合なら、満たされていない不等式 $\langle c_i,y\rangle>d_i$ を 1 つ見つけて $g=c_i$ とすればよい。
以下、$n\ge2$ とする。$f\colon\mathbb R^n\to\mathbb R$ を凸関数とする(各点で 劣微分 は空でない)。
$K$ の分離オラクルと、$K\subset B(c_0,R)$ となる中心 $c_0$ と半径 $R$ を受け取る。$E_0:=E(R^2I,c_0)$ とし、$k=0,1,2,\dots$ について、$E_k=E(A_k,c_k)$ の中心 $c_k$ で次を行う。
$g_k=0$ なら劣勾配の不等式からすべての $y$ で $f(y)\ge f(c_k)$ なので、2 の停止は正しい。点を探すだけなら $f\equiv0$ とする。このとき中心が $K$ に入った最初の段で止まる。各段で残す半空間を $H_k:=\{x\mid\langle g_k,x-c_k\rangle\le0\}$ と書く。thm-ell-half の 1 により $E_k\cap H_k\subset E_{k+1}$ である。1 回の更新は、行列とベクトルの積と階数 1 の修正なので、$n^2$ の程度の四則演算と 1 回の平方根で済む。
$K$ を凸集合とし、ある点 $z$ について $B(z,r)\subset K\subset B(c_0,R)$($0< r\le R$)とする。$f\equiv0$ の楕円体法で、
$$
N:=\bigl\lceil2n(n+1)\log(R/r)\bigr\rceil
$$
とおくと、中心 $c_0,c_1,\dots,c_N$ のどれかは $K$ に入る。
$c_0,\dots,c_N$ がどれも $K$ に入らないと仮定する。このとき $N+1$ 回の切断はすべて実行可能性の切断で、$K\subset H_k$ である。$K\subset E_0$ から始めて、$K\subset E_k$ なら $K\subset E_k\cap H_k\subset E_{k+1}$ なので、帰納法により $K\subset E_{N+1}$ である。thm-ell-half の 2 を $N+1$ 回使うと
$$
r^nV_n\le\operatorname{vol}K\le\operatorname{vol}E_{N+1}< e^{-(N+1)/(2(n+1))}\operatorname{vol}E_0=e^{-(N+1)/(2(n+1))}R^nV_n
$$
である。対数をとると $N+1< 2n(n+1)\log(R/r)\le N$ となり、矛盾する。$\square$
$K$ をコンパクトな凸集合とし、ある点 $z$ について $B(z,r)\subset K\subset B(c_0,R)$($0< r\le R$)とする。$f^*:=\min_Kf$、$V:=\max_Kf-f^*$ とおく。$T\ge1$ について
$$
\varepsilon_T:=\frac Rr\,e^{-T/(2n(n+1))}
$$
とし、$\varepsilon_T< 1$ とする。楕円体法が $T$ 回の切断の前に止まらなければ、中心 $c_0,\dots,c_{T-1}$ のどれかは $K$ に入り、
$$
\min\bigl\{f(c_k)\bigm|0\le k\le T-1,\ c_k\in K\bigr\}-f^*\le\varepsilon_TV
$$
である。途中で止まれば、止まった中心は $K$ の上の $f$ の最小点である。
$f$ は連続で $K$ はコンパクトなので、$f^*=f(x^*)$ となる $x^*\in K$ がある。$\varepsilon_T< \varepsilon\le1$ となる $\varepsilon$ を任意にとり、
$$
K_\varepsilon:=x^*+\varepsilon(K-x^*)=\{(1-\varepsilon)x^*+\varepsilon y\mid y\in K\}
$$
とおく。$K$ は凸なので $K_\varepsilon\subset K$ で、$K_\varepsilon$ は半径 $\varepsilon r$ の球 $B\bigl((1-\varepsilon)x^*+\varepsilon z,\varepsilon r\bigr)$ を含む。よって
$$
\operatorname{vol}K_\varepsilon\ge\varepsilon^nr^nV_n>\varepsilon_T^nr^nV_n=R^ne^{-T/(2(n+1))}V_n>\operatorname{vol}E_T
$$
である(最後は thm-ell-half の 2 を $T$ 回使った)。したがって $K_\varepsilon\not\subset E_T$ で、$x\in K_\varepsilon$、$x\notin E_T$ となる点 $x$ がある。$x\in K\subset E_0$ なので、$x\in E_k$、$x\notin E_{k+1}$ となる $k\in\{0,\dots,T-1\}$ がある。$E_k\cap H_k\subset E_{k+1}$ なので $x\notin H_k$ である。
第 $k$ 段が実行可能性の切断なら $K\subset H_k$ で、$x\in K$ に反する。よって $c_k\in K$ で、第 $k$ 段は目的関数の切断であり、$x\notin H_k$ は $\langle g_k,x-c_k\rangle>0$ を意味する。劣勾配の不等式から
$$
f(x)\ge f(c_k)+\langle g_k,x-c_k\rangle>f(c_k)
$$
である。一方 $x=(1-\varepsilon)x^*+\varepsilon y$($y\in K$)と書けるので、$f$ の凸性から $f(x)\le(1-\varepsilon)f^*+\varepsilon f(y)\le f^*+\varepsilon V$ である。合わせて、$K$ に入る中心 $c_k$($k\le T-1$)で $f(c_k)< f^*+\varepsilon V$ となるものがある。$\varepsilon\in(\varepsilon_T,1]$ は任意で、候補の $k$ は有限個なので、$\min_kf(c_k)-f^*\le\varepsilon_TV$ である。
途中で止まった場合は、方法の定義の後の注意のとおりである。$\square$
thm-ell-main の仮定のもとで、$0< \delta< 1$ について、$T\ge2n(n+1)\log\frac R{r\delta}$ 回の切断の後の出力は $f(c)-f^*\le\delta V$ をみたす。
このとき $\varepsilon_T\le\frac Rr\cdot\frac{r\delta}R=\delta< 1$ である。$\square$
誤差は回数について指数的に減り、その速さは関数の形にも $V$ の大きさにもよらず、次元 $n$ と比 $R/r$ だけで決まる。一方、1 回で縮む割合が $1-\frac1{2n(n+1)}$ 程度なので、次元が大きいと遅い。誤差が回数の平方根に反比例する 劣勾配法 と比べると、少ない次元で高い精度が要る問題に向く。
線形計画法 の問題 $\max\{c^\top x\mid Ax\le b\}$($A,b,c$ は有理数)は、入力の大きさ(係数の 2 進の桁数の合計)の多項式の時間で解ける(Khachiyan、Kha80。GLS88 Theorem (6.4.12)、pp. 180–181)。上の定理をそのまま使うには、次の点を補う必要がある。
$K=[0,1]^2$、$f(x)=\lvert x_1-0.3\rvert+\lvert x_2-0.2\rvert$ とする。$K$ は半径 $r=\frac12$ の円板 $B((\frac12,\frac12),\frac12)$ を含み、半径 $R=\frac{\sqrt2}2$ の円板 $B((\frac12,\frac12),\frac{\sqrt2}2)$ に含まれる。$f^*=0$、$V=f(1,1)=1.5$ である。分離オラクルは満たされない程度が最も大きい辺の外向きの法線を返し、劣勾配は各成分の符号($0$ では $+1$)とする。$n=2$ なので $\varepsilon_T=\sqrt2\,e^{-T/12}$ である。
| $T$ | 最良値 $\min f(c_k)$ | 保証 $\varepsilon_TV$ |
|---|---|---|
| $12$ | $0.0103$ | $0.780$ |
| $24$ | $0.00062$ | $0.287$ |
| $36$ | $0.00051$ | $0.106$ |
| $48$ | $0.00021$ | $0.0389$ |
| $60$ | $0.000033$ | $0.0143$ |
(数値計算による値。)最良値は保証よりずっと小さいが、減り方は一様でない。中心での $f$ の値は段ごとに単調には減らず、最良値は中心が最小点の近くに来た段でだけ更新されるからである(この例では $60$ 段まで中心はすべて $K$ に入り、$c_3=(\frac49,0)$ は辺の上にある)。1 回の切断で面積は $\frac4{3\sqrt3}\approx0.770$ 倍になる。
各行は 1 つの条件だけを外している($n=2$)。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| $K$ が半径 $r>0$ の球を含むこと | $K=\{(t,0)\mid\lvert t\rvert\le\frac12\}$(線分)、$E_0=B((0,\frac{\sqrt2}4),1)$、オラクルは $g=(0,\operatorname{sign}c_{k,2})$ | 有限の回数で中心が $K$ に入ること(thm-ell-feasible。中心は一度も $K$ に入らない) |
| $K\subset B(c_0,R)$ | $K=B((11,0),1)$、$c_0=0$、$R=1$、$r=1$ | thm-ell-feasible($N=0$ だが $c_0\notin K$) |
| $f$ の凸性 | $K$ も $E_0$ も単位円板、$f(x)=-\lvert x\rvert^2$ | thm-ell-main($c_0=0$ で勾配が $0$ なので止まるが、$f(0)-f^*=1=V$) |
1 行目:$c_k=(0,c_{k,2})$ で $c_{k,2}\ne0$ なら $c_k\notin K$ で、$g=(0,\operatorname{sign}c_{k,2})$ について $K$ の点 $x$ は $\langle g,x-c_k\rangle=-\lvert c_{k,2}\rvert< 0$ をみたすので、オラクルとして正しい。$A_k$ が対角行列で $g=\pm e_2$ なら $b=\pm\sqrt{(A_k)_{22}}\,e_2$ で、$A_{k+1}=\mathrm{diag}\bigl(\frac43(A_k)_{11},\frac49(A_k)_{22}\bigr)$、$c_{k+1}=c_k\mp\frac13\sqrt{(A_k)_{22}}\,e_2$ である。$(A_0)_{22}=1$ から $\sqrt{(A_k)_{22}}=(\frac23)^k$ は有理数で、第 1 座標は $0$ のまま、第 2 座標は $\frac{\sqrt2}4$ に有理数を足したものなので $0$ にならない。$K$ は内点をもたず、どんな $r>0$ の円板も含まない。2 行目:$N=\lceil12\log1\rceil=0$ で、定理は $c_0\in K$ を主張するが $c_0=0\notin K$ である。$K\not\subset B(0,1)$ である。3 行目:$f$ の勾配は $-2x$ で、$c_0=0$ で $0$ なので方法は止まる。$f^*=-1$、$\max_Kf=0$ で、$\varepsilon_T< 1$ となる $T$ でも誤差は $V$ に等しい。$-\lvert x\rvert^2$ は凸でない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する