楕円体法

同義語:ellipsoid methodellipsoid algorithm

概要

楕円体法(ellipsoid method)とは、凸集合の点を探す問題や凸集合の上で凸関数を最小にする問題を、楕円体を縮めながら解く反復法で、中心が集合の外なら分離する超平面で、中心が集合の中なら劣勾配で楕円体を半分に切り、残した半楕円体を含む新しい楕円体で包み直す。$n\ge2$ 次元では 1 回ごとに体積が $e^{-1/(2(n+1))}$ 倍未満になるので、集合が半径 $r$ の球を含み半径 $R$ の球に含まれるなら、誤差は回数 $T$ について $(R/r)e^{-T/(2n(n+1))}$ に比例して減る。Shor と Yudin–Nemirovskii が凸最適化のために導き、Khachiyan はこれで線形計画問題が多項式時間で解けることを示した。

$$\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}} $$

前提知識: 凸集合, 凸関数, 劣微分, 正定値行列, 行列式

楕円体法(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'$ は正定値で、

  1. 半楕円体 $E\cap\{x\mid\langle g,x-a\rangle\le0\}$ は $E':=E(A',a')$ に含まれる。
  2. 体積の比は
    $$ \frac{\operatorname{vol}E'}{\operatorname{vol}E}=\frac n{n+1}\Bigl(\frac{n^2}{n^2-1}\Bigr)^{(n-1)/2}< e^{-1/(2(n+1))} $$
    である。
単位球に移して確かめる

$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$ で次を行う。

  1. 実行可能性の切断:$c_k\notin K$ なら、オラクルの返す $g_k$ を使う。
  2. 目的関数の切断:$c_k\in K$ なら、劣勾配 $g_k\in\partial f(c_k)$ を 1 つ選ぶ。$g_k=0$ なら止まる($c_k$ は $f$ の最小点である)。
  3. $E_{k+1}:=E(A_{k+1},c_{k+1})$ を、thm-ell-half の式で $E_k$ と $g=g_k$ から作る。
    それまでに $K$ に入った中心のうち $f$ の値が最小のものを出力する。

$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)。上の定理をそのまま使うには、次の点を補う必要がある。

  • $R$ の上界:係数が整数の多面体の頂点は、入力の桁数の指数の大きさの球に入る(GLS88 Lemma (3.1.33)、p. 76。証明は Cramer の公式による)。よって $\log R$ は入力の大きさの多項式である。
  • $r$ の下界:内点をもつ(全次元の)係数が整数の多面体の体積は、入力の桁数で書ける下界をもつ(GLS88 Lemma (3.1.35)、p. 79)。内点をもたない場合は、多面体を含む超平面を見つけて次元を下げる(GLS88 Theorem (6.4.1) の証明、pp. 174–175)。
  • 丸め:$b$ の式の平方根で無理数が出るので、有限の桁で計算し、楕円体を少し大きくして誤差を吸収する(GLS88 §3.1、pp. 80–82 の考え方と §3.2 の解析)。
    この記事ではこれらの細部は扱わない。重要なのは、方法が使うのが分離オラクルだけで、不等式の本数 $m$ が反復の回数に入らないことである。制約が指数個あっても、満たされていない制約を多項式時間で 1 つ見つけられるなら、その問題は多項式時間で解ける(WS11 §4.3、p. 87)。さらに、適切な条件のもとで、多面体の上の最適化・分離・制約が満たされていないことの判定の 3 つの問題は、どれか 1 つが多項式時間で解ければ残りも解ける(GLS88 Theorem (6.4.9)、p. 179)。Lovászのθ関数 が多項式時間で計算できるのも、この枠組みによる。

例

正方形の上の最小化

$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$ は凸でない。

補足

  • 切断の変種:中心を通らない超平面で切る場合(中心より多く削る深い切断と、少なく削る浅い切断)や、中心に関して対称な 2 枚の平行な超平面ではさむ場合にも、残る部分を含む体積最小の楕円体の式が知られている(GLS88 §3.1、pp. 71–72)。
  • 由来:Shor(1970)の空間の伸縮を伴う勾配射影法を元に、Yudin–Nemirovskii(1976)が方法の概略を与え、今日の形での最初の明示は Shor(1977、Sho77)による(GLS88 p. 65)。凸関数の微分できない最適化の方法として生まれ、線形計画への応用はその後である。
  • 分離と最適化:thm-ell-main の証明が使うのは、各段の「中心が外ならそれを分ける超平面」と「中心が中なら値を下げうる側を示す半空間」だけである。目的関数が 1 次なら後者は $\{x\mid c^\top x\ge c^\top c_k\}$(最大化)で与えられ、これが分離から最適化を得る仕組みである。

関連項目

参考文献

[1]
Martin Grötschel; László Lovász; Alexander Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag(Algorithms and Combinatorics 2), 1988, 第 3 章の序(pp. 64–65)、§3.1:式 (3.1.11)・(3.1.12)(p. 70)、pp. 71–72、Lemma (3.1.33)(p. 76)、Lemma (3.1.34)(p. 77)、Lemma (3.1.35)(p. 79)、pp. 80–82、§3.2、Theorem (6.4.1)(pp. 174–175)、Theorem (6.4.9)(p. 179)、Theorem (6.4.12)(pp. 180–181)

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