交互方向乗数法

同義語:ADMMalternating direction method of multipliers

概要

交互方向乗数法(alternating direction method of multipliers, ADMM)とは、2 つの変数に分かれた凸関数の和 $f(x)+g(z)$ を 1 次の等式 $Ax+Bz=c$ の条件のもとで最小化するため、条件を乗数と 2 次の罰金で目的関数に繰り込んだ拡張 Lagrange 関数を $x$、$z$ の順に交互に最小化し、乗数を条件の残差の分だけ動かす反復法である。各段では片方の変数だけの易しい問題を解けばよく、LASSO などの罰金つきの最小二乗や分散計算に使う。$f$ と $g$ が凸で、条件なしの Lagrange 関数に鞍点があり、各段の最小化に解があれば、条件の残差は 0 に近づき、目的関数の値は最適値に近づく。

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

前提知識: Lagrange双対性, 凸関数, 近接勾配法

LASSO の目的関数 $\frac12\|Ax-b\|^2+\mu\|x\|_1$ は、変数を 2 つに複製して
$$ \text{最小化 }\ \frac12\|Ax-b\|^2+\mu\|z\|_1\qquad\text{条件 }\ x-z=0 $$
と書き直せる。こうすると、$x$ だけの問題(連立 1 次方程式)と $z$ だけの問題(軟しきい値)はそれぞれ易しい。難しいのは条件 $x=z$ で 2 つが結びついていることだけである。
交互方向乗数法(ADMM)は、このように「目的関数は 2 つの変数の和に分かれ、1 次の等式の条件だけが両者を結ぶ」問題を解く反復法である。条件を乗数と 2 次の罰金で目的関数に繰り込み(拡張 Lagrange 関数)、それを $x$ について最小化し、次に $z$ について最小化し、最後に乗数を条件の残差の分だけ動かす。2 つの最小化を同時にではなく交互に行うので、各段で一方の変数だけの易しい問題を解けばよい。
この記事では、目的関数の 2 つの項が凸で、条件なしの Lagrange 関数に鞍点があり、各段の最小化に解があれば、条件の残差が $0$ に近づき目的関数の値が最適値に近づくこと(主定理)を証明する。2 次関数の場合には収束の速さを明示的に計算する。

定義と使える条件

以下、$\|\cdot\|$ は Euclid ノルム、$a\cdot b$ は内積、$M^{\mathsf T}$ は転置とする。関数 $f\colon\mathbb{R}^n\to(-\infty,+\infty]$ は $+\infty$ の値を許し、凸で、少なくとも 1 点で有限の値をとるとき 真凸 という。

問題と拡張 Lagrange 関数

$f\colon\mathbb{R}^n\to(-\infty,+\infty]$、$g\colon\mathbb{R}^m\to(-\infty,+\infty]$ を真凸関数、$A\in\mathbb{R}^{p\times n}$、$B\in\mathbb{R}^{p\times m}$、$c\in\mathbb{R}^p$ とし、問題
$$ \text{(P)}\qquad\text{最小化 }\ f(x)+g(z)\qquad\text{条件 }\ Ax+Bz=c $$
を考える。その最適値(下限)を $p^*$ と書く。$y\in\mathbb{R}^p$(乗数)と $\rho\ge0$ について
$$ L_\rho(x,z,y):=f(x)+g(z)+y\cdot(Ax+Bz-c)+\frac\rho2\|Ax+Bz-c\|^2 $$
を 拡張 Lagrange 関数 という。$L_0$ は条件なしの Lagrange 関数である。

交互方向乗数法

$\rho>0$、初期値 $z^0\in\mathbb{R}^m$、$y^0\in\mathbb{R}^p$ について、$k=0,1,2,\dots$ で
$$ \begin{aligned} x^{k+1}&\in\operatorname*{arg\,min}_xL_\rho(x,z^k,y^k),\\ z^{k+1}&\in\operatorname*{arg\,min}_zL_\rho(x^{k+1},z,y^k),\\ y^{k+1}&:=y^k+\rho\,(Ax^{k+1}+Bz^{k+1}-c) \end{aligned} $$
とする方法を 交互方向乗数法(alternating direction method of multipliers, ADMM)という。$r^{k}:=Ax^{k}+Bz^{k}-c$ を 主残差、$s^{k+1}:=\rho A^{\mathsf T}B(z^{k+1}-z^k)$ を 双対残差 という。

$u:=y/\rho$ とおくと $y\cdot r+\frac\rho2\|r\|^2=\frac\rho2\|r+u\|^2-\frac\rho2\|u\|^2$ なので、反復は次の 尺度を変えた形 と同じである:
$$ x^{k+1}\in\operatorname*{arg\,min}_x\Bigl(f(x)+\frac\rho2\|Ax+Bz^k-c+u^k\|^2\Bigr),\quad z^{k+1}\in\operatorname*{arg\,min}_z\Bigl(g(z)+\frac\rho2\|Ax^{k+1}+Bz-c+u^k\|^2\Bigr),\quad u^{k+1}:=u^k+r^{k+1}. $$
$A=I$、$B=-I$、$c=0$ のとき、$z$ の段は $g$ の 近接勾配法 の定義「近接写像」で $z^{k+1}=\operatorname{prox}_{g/\rho}(x^{k+1}+u^k)$ と書ける。$x$ の段も同様に $f$ の近接写像である。
$x$ と $z$ を同時に最小化して $y$ を動かす方法は 乗数法(拡張 Lagrange 法、非線形計画法 の節「拡張 Lagrange 法」)である。交互方向乗数法は、その同時の最小化を $x$ と $z$ の 1 回ずつの最小化に置きかえたものと見なせる。
この記事の評価を使う条件をまとめる。

  1. 凸性:$f$、$g$ は真凸関数である。
  2. 鞍点:$L_0$ に鞍点がある。すなわち $(x^*,z^*,y^*)$ で、すべての $x,z,y$ について
    $$ L_0(x^*,z^*,y)\le L_0(x^*,z^*,y^*)\le L_0(x,z,y^*). $$
  3. 部分問題の解:各段の 2 つの最小化に最小点がある(一意でなくてよい)。
  4. $\rho>0$。
    条件 2 の鞍点では $L_0(x^*,z^*,y^*)$ は有限である(右の不等式の右辺を有限にとれ、左の不等式から $f(x^*),g(z^*)< +\infty$)。左の不等式は $y$ の 1 次式 $y\cdot(Ax^*+Bz^*-c)$ が上に有界であることを言うので $Ax^*+Bz^*=c$ である。すると条件を満たす $(x,z)$ について $f(x)+g(z)=L_0(x,z,y^*)\ge L_0(x^*,z^*,y^*)=f(x^*)+g(z^*)$ なので、$(x^*,z^*)$ は (P) の最適解で $p^*=f(x^*)+g(z^*)$ である。$f,g$ が全空間で有限な凸関数で (P) に最適解があれば、条件が 1 次の等式だけなので、Lagrange双対性 の定理「強双対性(Slater 条件)」と定理「鞍点定理」を変数 $(x,z)$ の問題に当てて鞍点が得られる。
    条件 3 は、$f,g$ が下半連続で $A$、$B$ が単射なら成り立つ。$A$ や $B$ が単射でないと、$f,g$ が下半連続でも成り立たないことがある(節「使える条件と反例」)。

公式の表

量式意味根拠
主残差$r^{k+1}=Ax^{k+1}+Bz^{k+1}-c$条件からのずれ定義
双対残差$s^{k+1}=\rho A^{\mathsf T}B(z^{k+1}-z^k)$$x$ の最適性からのずれprop-admm-optimality
$z$ の最適性$z^{k+1}$ は $g(z)+y^{k+1}\cdot Bz$ を最小にする毎回成り立つprop-admm-optimality
リアプノフ関数$V^k=\frac1\rho\|y^k-y^*\|^2+\rho\|B(z^k-z^*)\|^2$$k\ge1$ で単調に減るthm-admm-convergence
収束$r^k\to0$、$f(x^k)+g(z^k)\to p^*$条件 1〜4 のもとthm-admm-convergence
2 次関数の例の速さ誤差は毎回 $\frac{1+\rho^2}{(1+\rho)^2}$ 倍$\rho=1$ で最小の $\frac12$prop-admm-quadratic
止める判定$\|r^k\|\le\varepsilon_{\mathrm{pri}}$ かつ $\|s^k\|\le\varepsilon_{\mathrm{dual}}$両方 $0$ なら鞍点prop-admm-optimality

主定理と証明

各段の最適性

微分できる項の 1 次化

$\varphi\colon\mathbb{R}^n\to(-\infty,+\infty]$ を真凸関数、$h\colon\mathbb{R}^n\to\mathbb{R}$ を微分可能な凸関数とし、$\bar x$ が $\varphi+h$ の最小点とする。このとき $\bar x$ は $\varphi(x)+\nabla h(\bar x)\cdot x$ の最小点でもある。

$\varphi+h$ は有限の値をとるので $\varphi(\bar x)< +\infty$ である。$\varphi(x)< +\infty$ となる $x$ と $0< t< 1$ について、$\bar x+t(x-\bar x)$ での値を比べ、$\varphi$ の凸性を使うと
$$ 0\le\varphi(\bar x+t(x-\bar x))-\varphi(\bar x)+h(\bar x+t(x-\bar x))-h(\bar x)\le t\bigl(\varphi(x)-\varphi(\bar x)\bigr)+h(\bar x+t(x-\bar x))-h(\bar x) $$
である。$t$ で割って $t\downarrow0$ とすると $0\le\varphi(x)-\varphi(\bar x)+\nabla h(\bar x)\cdot(x-\bar x)$ を得る。$\varphi(x)=+\infty$ の $x$ では明らかである。$\square$

各段の最適性と残差

条件 1・3・4 のもとで、各 $k\ge0$ について次が成り立つ。

  1. $z^{k+1}$ は $g(z)+y^{k+1}\cdot Bz$ の最小点である。
  2. $x^{k+1}$ は $f(x)+\bigl(y^{k+1}-\rho B(z^{k+1}-z^k)\bigr)\cdot Ax$ の最小点である。
    とくに $r^{k+1}=0$ かつ $s^{k+1}=0$ なら、$(x^{k+1},z^{k+1},y^{k+1})$ は $L_0$ の鞍点である。

$L_\rho(x^{k+1},z,y^k)$ を $g(z)+h(z)$、$h(z):=y^k\cdot(Ax^{k+1}+Bz-c)+\frac\rho2\|Ax^{k+1}+Bz-c\|^2$ と分けると、$\nabla h(z^{k+1})=B^{\mathsf T}(y^k+\rho r^{k+1})=B^{\mathsf T}y^{k+1}$ なので、lem-admm-linear から 1 を得る。同様に $L_\rho(x,z^k,y^k)$ の $x$ について微分できる部分の勾配は、$x^{k+1}$ で
$$ A^{\mathsf T}\bigl(y^k+\rho(Ax^{k+1}+Bz^k-c)\bigr)=A^{\mathsf T}\bigl(y^k+\rho r^{k+1}-\rho B(z^{k+1}-z^k)\bigr)=A^{\mathsf T}\bigl(y^{k+1}-\rho B(z^{k+1}-z^k)\bigr) $$
なので 2 を得る。
最後の主張:$s^{k+1}=0$ なら $\rho B(z^{k+1}-z^k)\cdot Ax=s^{k+1}\cdot x=0$ なので、2 から $x^{k+1}$ は $f(x)+y^{k+1}\cdot Ax$ の最小点である。1 と合わせると、$(x^{k+1},z^{k+1})$ は $L_0(x,z,y^{k+1})=f(x)+y^{k+1}\cdot Ax+g(z)+y^{k+1}\cdot Bz-y^{k+1}\cdot c$ の最小点で、鞍点の右の不等式が成り立つ。$r^{k+1}=0$ なら $L_0(x^{k+1},z^{k+1},y)$ は $y$ によらないので、左の不等式も等号で成り立つ。$\square$

$y^{k+1}$ は $z$ の段の最適性をいつも満たすように更新されている。$x$ の段の最適性からのずれが双対残差 $s^{k+1}$ であり、条件のずれが主残差 $r^{k+1}$ である。

主定理:残差と目的関数の値の収束

交互方向乗数法の収束

条件 1〜4 を仮定し、$(x^*,z^*,y^*)$ を $L_0$ の鞍点とする。$p^k:=f(x^k)+g(z^k)$、$V^k:=\frac1\rho\|y^k-y^*\|^2+\rho\|B(z^k-z^*)\|^2$ とおくと、$k\ge1$ について
$$ V^{k+1}\le V^k-\rho\|r^{k+1}\|^2-\rho\|B(z^{k+1}-z^k)\|^2 $$
が成り立つ。その結果、$k\to\infty$ で $r^k\to0$、$s^k\to0$、$p^k\to p^*$ であり、$y^k$ と $Bz^k$ は有界である。

2 つの評価を足してリアプノフ関数の減少を出す

$r:=r^{k+1}$、$\delta:=B(z^{k+1}-z^k)$、$d_k:=B(z^k-z^*)$、$e_k:=y^k-y^*$ とおく。鞍点では $Ax^*+Bz^*=c$、$p^*=f(x^*)+g(z^*)$ である(節「定義と使える条件」)。
下からの評価:鞍点の右の不等式で $(x,z)=(x^{k+1},z^{k+1})$ とおくと $p^*\le p^{k+1}+y^*\cdot r$ である。
上からの評価:prop-admm-optimality の 2 と 1 で、$x^{k+1}$ と $x^*$、$z^{k+1}$ と $z^*$ を比べると
$$ f(x^{k+1})+(y^{k+1}-\rho\delta)\cdot Ax^{k+1}\le f(x^*)+(y^{k+1}-\rho\delta)\cdot Ax^*,\qquad g(z^{k+1})+y^{k+1}\cdot Bz^{k+1}\le g(z^*)+y^{k+1}\cdot Bz^* $$
である。足し合わせ、$A(x^{k+1}-x^*)+B(z^{k+1}-z^*)=r$、すなわち $A(x^{k+1}-x^*)=r-d_{k+1}$ を使うと
$$ p^{k+1}-p^*\le-y^{k+1}\cdot r+\rho\,\delta\cdot(r-d_{k+1}) $$
である。
リアプノフ関数:2 つの評価を足して 2 倍すると
$$ 2e_{k+1}\cdot r-2\rho\,\delta\cdot r+2\rho\,\delta\cdot d_{k+1}\le0 $$
である。$e_{k+1}=e_k+\rho r$ から $\frac1\rho\bigl(\|e_{k+1}\|^2-\|e_k\|^2\bigr)=2e_k\cdot r+\rho\|r\|^2$ なので、$2e_{k+1}\cdot r=\frac1\rho\bigl(\|e_{k+1}\|^2-\|e_k\|^2\bigr)+\rho\|r\|^2$ である。また $\delta=d_{k+1}-d_k$ から $2\delta\cdot d_{k+1}=\|d_{k+1}\|^2-\|d_k\|^2+\|\delta\|^2$ である。代入して整理すると
$$ V^{k+1}-V^k+\rho\|r-\delta\|^2\le0 $$
を得る。
交差項の符号:$k\ge1$ では $z^k$ も prop-admm-optimality の 1 により $g(z)+y^k\cdot Bz$ の最小点である。$z^{k+1}$ と $z^k$ を互いに比べた 2 つの不等式
$$ g(z^{k+1})+y^{k+1}\cdot Bz^{k+1}\le g(z^k)+y^{k+1}\cdot Bz^k,\qquad g(z^k)+y^k\cdot Bz^k\le g(z^{k+1})+y^k\cdot Bz^{k+1} $$
を足すと $(y^{k+1}-y^k)\cdot\delta\le0$、すなわち $\rho\,r\cdot\delta\le0$ である。よって $\|r-\delta\|^2\ge\|r\|^2+\|\delta\|^2$ で、主張の不等式を得る。
結論:$V^k\ge0$ は $k\ge1$ で減少するので有界で、$y^k$ と $Bz^k$ は有界である。不等式を $k=1,2,\dots$ について足すと $\rho\sum_k(\|r^{k+1}\|^2+\|\delta\|^2)\le V^1$ なので、$r^k\to0$ と $B(z^{k+1}-z^k)\to0$、したがって $s^k\to0$ である。下からの評価の右辺 $y^*\cdot r^{k+1}$ と、上からの評価の右辺 $-y^{k+1}\cdot r^{k+1}+\rho\,\delta\cdot(r^{k+1}-d_{k+1})$ は、有界な列と $0$ に近づく列の内積なので $0$ に近づく。よって $p^k\to p^*$ である。$\square$

さらに $y^k$ は双対問題の最適解に収束することが知られている(BPCPE11 §3.2.1、p. 17。この記事では証明しない)。一方、$x^k$ と $z^k$ そのものは最適解に収束するとは限らない。定理が保証するのは「条件をほぼ満たし、値がほぼ最適」な点である。収束の速さは一般には遅く、高い精度を得るには多くの反復が要るが、中程度の精度には数十回で達することが多い(同書 §3.2.2)。

2 次関数の場合の速さ

2 次関数の場合の 1 次収束

$a,b\in\mathbb{R}$、$f(x)=\frac12(x-a)^2$、$g(z)=\frac12(z-b)^2$ とし、条件 $x-z=0$ のもとで最小化する($A=1$、$B=-1$、$c=0$)。尺度を変えた形の交互方向乗数法の誤差 $\varepsilon^k:=(z^k-z^*,\,u^k-u^*)$($z^*=\frac{a+b}2$、$u^*=\frac{a-b}{2\rho}$)は
$$ \varepsilon^{k+1}=\frac1{(1+\rho)^2}\begin{pmatrix}\rho^2&\rho\\\rho&1\end{pmatrix}\varepsilon^k $$
を満たし、$k\ge1$ で $\varepsilon^{k+1}=q\,\varepsilon^k$、$q:=\dfrac{1+\rho^2}{(1+\rho)^2}$ である。$q$ は $\rho=1$ で最小値 $\frac12$ をとる。

証明を開く

各段は 1 変数の 2 次関数の最小化で、$x^{k+1}=\frac{a+\rho(z^k-u^k)}{1+\rho}$、$z^{k+1}=\frac{b+\rho(x^{k+1}+u^k)}{1+\rho}$、$u^{k+1}=u^k+x^{k+1}-z^{k+1}$ である。$(z^*,u^*)$ はこの写像の不動点である($x=z=z^*$ で、$x$ の式から $\rho u^*=a-z^*$)。誤差は定数項が消えて 1 次写像で写り、代入して計算すると係数は$$z^{k+1}-z^*=\tfrac{\rho^2(z^k-z^*)+\rho(u^k-u^*)}{(1+\rho)^2},\qquad u^{k+1}-u^*=\tfrac{\rho(z^k-z^*)+(u^k-u^*)}{(1+\rho)^2}$$である。行列は $\frac1{(1+\rho)^2}ww^{\mathsf T}$、$w=(\rho,1)$ の形で、$k\ge1$ の誤差 $\varepsilon^k$ は $w$ の定数倍である。$ww^{\mathsf T}w=\|w\|^2w=(1+\rho^2)w$ なので $\varepsilon^{k+1}=q\varepsilon^k$ である。$q$ は $\rho>0$ で $1-\frac{2\rho}{(1+\rho)^2}$ と書け、$\frac{2\rho}{(1+\rho)^2}$ は $\rho=1$ で最大値 $\frac12$ をとる(相加相乗平均)。$\square$

$\rho$ を大きくしても小さくしても速さは落ちる。罰金 $\rho$ が大きすぎると $x$ と $z$ が互いに縛られて動きにくくなり、小さすぎると乗数の更新が遅くなる。$\rho$ の選び方は、主残差と双対残差の大きさを見て反復の途中で調節することが多い。

計算の手順

  1. 分ける:目的関数を 2 つの項 $f(x)+g(z)$ に分け、両者を結ぶ条件を $Ax+Bz=c$ の形に書く。典型は「$f$ はなめらかな損失、$g$ は罰金や集合の指示関数、条件は $x-z=0$」である。
  2. 部分問題を閉じた形にする:$x$ の段と $z$ の段がそれぞれ連立 1 次方程式・近接写像・射影で解けることを確かめる。$f=\frac12\|Ax-b\|^2$、条件 $x-z=0$ なら $x$ の段は $(A^{\mathsf T}A+\rho I)x=A^{\mathsf T}b+\rho(z^k-u^k)$ で、係数行列は反復によらないので 1 度だけ分解しておけばよい。
  3. $\rho$ と初期値を決める:$\rho=1$ から始め、$z^0=0$、$u^0=0$ とすることが多い。
  4. 反復する:尺度を変えた形の 3 つの式を順に計算する。
  5. 止める:主残差 $\|r^k\|$ と双対残差 $\|s^k\|$ がともに許容誤差以下になったら止める(prop-admm-optimality)。反復の上限も置く。

例題

1 変数の 2 次関数

$f(x)=\frac12(x-3)^2$、$g(z)=\frac12(z-1)^2$、条件 $x-z=0$、$\rho=1$、$z^0=u^0=0$。
使う公式:prop-admm-quadratic。
答え:最適解 $x^*=z^*=2$、$u^*=1$($y^*=1$)。$(x^k,z^k,u^k)$ は $(1.5,1.25,0.25)$、$(2,1.625,0.625)$、$(2,1.8125,0.8125)$ と進み、$k\ge2$ で $x^k=2$、$z^k=2-0.375\cdot2^{-(k-2)}$。$k=20$ で $z^{20}\approx1.9999986$。$\rho=\frac12$ と $\rho=2$ では誤差は毎回 $\frac59$ 倍、$\rho=4$ では $\frac{17}{25}$ 倍になる。

1 ノルムで罰した最小二乗

近接勾配法 の例題と同じ $A=\begin{pmatrix}1&1\\1&0.5\end{pmatrix}$、$b=(3,1)$、$\mu=0.5$ について、$f(x)=\frac12\|Ax-b\|^2$、$g(z)=0.5\|z\|_1$、条件 $x-z=0$ とし、$z^0=u^0=0$ から解く。
使う公式:手順 2、近接勾配法 の命題「1 ノルムの近接写像(軟しきい値)」、thm-admm-convergence。
答え:$\rho=1$ では $x^1=(0.833333,\,1)$、$z^1=(0.333333,\,0.5)$、$x^2=z^2=(0.75,\,1.055556)$。$z^k$ の第 1 成分は $k=16$ で $0$ になり、$\|z^k-x^*\|$ と $\|r^k\|$ がともに $10^{-6}$ 以下になるのは $k=45$($x^*=(0,2.4)$)。乗数は $y^k\to(0.4,\,0.5)$ で、これは $-\nabla f(x^*)$ に等しい。同じ判定で $\rho=0.5$ なら $k=38$、$\rho=2$ なら $k=53$。

途中の計算を開く

$x$ の段は $(A^{\mathsf T}A+\rho I)x=A^{\mathsf T}b+\rho(z-u)$、$A^{\mathsf T}A=\begin{pmatrix}2&1.5\\1.5&1.25\end{pmatrix}$、$A^{\mathsf T}b=(4,3.5)$。$\rho=1$、$z=u=0$ で $\begin{pmatrix}3&1.5\\1.5&2.25\end{pmatrix}x=(4,3.5)$ を解いて $x^1=(\frac56,1)$。$z$ の段は $x^1+u^0$ をしきい値 $\mu/\rho=0.5$ で縮めて $(\frac13,0.5)$。$u^1=x^1-z^1=(0.5,0.5)$。乗数の極限:prop-admm-optimality の 1 は $0\in\partial g(z^*)-y^*$(条件 $x-z=0$ で $B=-I$)を、2 は $\nabla f(x^*)+y^*=0$ を表す。

図: 例題「1 ノルムで罰した最小二乗」で、罰金の係数 ρ が 0.5、1、2 の場合について、左は z_k と最小点の距離、右は主残差と双対残差の長さの和を片対数で描いたもの。どの ρ でも最初の 30 回ほどはゆっくり減り、その後は振動しながらほぼ直線的に減る。ρ = 2 がいちばん遅い。 図: 例題「1 ノルムで罰した最小二乗」で、罰金の係数 ρ が 0.5、1、2 の場合について、左は z_k と最小点の距離、右は主残差と双対残差の長さの和を片対数で描いたもの。どの ρ でも最初の 30 回ほどはゆっくり減り、その後は振動しながらほぼ直線的に減る。ρ = 2 がいちばん遅い。

単体への射影

$a=(0.8,0.6,-0.4)$ に最も近い単体 $\{x\in\mathbb{R}^3\mid x_j\ge0,\ x_1+x_2+x_3=1\}$ の点を求める。$f(x)=\frac12\|x-a\|^2+I_H(x)$($H$ は平面 $x_1+x_2+x_3=1$)、$g=I_{\mathbb{R}^3_{\ge0}}$、条件 $x-z=0$、$\rho=1$、$z^0=u^0=0$。
使う公式:手順 2、thm-admm-convergence。
答え:$x^*=(0.6,\,0.4,\,0)$。$z^1=(0.566667,\,0.466667,\,0)$、$k=10$ で $\|z^k-x^*\|\approx1.5\times10^{-3}$、$k=20$ で $1.5\times10^{-6}$ と、ほぼ毎回 $\frac12$ 倍で減る。

途中の計算を開く

$x$ の段は $\frac12\|x-a\|^2+\frac\rho2\|x-z+u\|^2$ の $H$ 上の最小点で、$w=\frac{a+\rho(z-u)}{1+\rho}$ を $H$ に直交射影した $w-\frac{w_1+w_2+w_3-1}3(1,1,1)$。$z$ の段は $x+u$ の負の成分を $0$ にする。$x^*$ の確認:$\tau=0.2$ として $\max\{a_j-\tau,0\}=(0.6,0.4,0)$ の和が $1$ で、これが単体への射影の KKT 条件(KKT条件)を満たす。

使える条件と反例

thm-admm-convergence の条件のうち 1 つだけを外した例を挙げる。

外す条件反例成り立たなくなること
鞍点(実行可能性)$x,z\in\mathbb{R}$、$f=g=0$、条件 $x+z=0$ と $x+z=1$($A=B=(1,1)^{\mathsf T}$、$c=(0,1)$)、$\rho=1$、$z^0=0$、$u^0=0$$r^k=(0.5,-0.5)$ のままで $0$ に近づかず、$u^k=k(0.5,-0.5)$ は有界でない
$f$ の凸性$f=I_{\{-1,1\}}$、$g(z)=\frac12(z-1)^2$、条件 $x-z=0$、$\rho=4$、$z^0=-1$、$u^0=0$$(x^k,z^k,u^k)\to(-1,-1,-0.5)$。$r^k\to0$ だが $p^k\to2\ne p^*=0$
部分問題の解$f(x_1,x_2)=x_1^2/x_2$($x_2>0$)、$f(0,0)=0$、それ以外 $+\infty$。$g(z)=\frac12z^2$、条件 $x_1-z=0$、$\rho=1$、$z^0=1$、$u^0=0$$f,g$ は下半連続な真凸関数で鞍点 $(0,0,0,0)$ もあるが、第 1 回の $x$ の段に最小点がない
表の反例の確かめ
確認を開く

1 行目:$x$ の段は $\|(x+z^k)(1,1)-c+u^k\|^2$ の最小化で $x+z^k=\frac12(1-u^k_1-u^k_2)$。$z$ の段も同じ和を与えるので $z^{k+1}=z^k=0$。$u^0_1+u^0_2=0$ なので和 $\frac12$、$r=(0.5,-0.5)$ で、$u$ の成分の和は $0$ のまま保たれる。2 行目:$f$ は凸でないが、$(x,z,y)=(1,1,0)$ は鞍点である($L_0(x,z,0)=I_{\{-1,1\}}(x)+\frac12(z-1)^2\ge0=L_0(1,1,y)$)。部分問題にも最小点がある。$x$ の段は $z^k-u^k$ に近い方の $\pm1$、$z$ の段は $z=\frac{1+4(x+u)}5$。$x=-1$ のままで $z^k\to-1$、$u^k\to-0.5$(不動点は $\frac{1+4(-1+u)}5=-1$ から $u=-0.5$ で、$z-u=-0.5$ に近いのは $-1$)。$\rho=1,2$ では同じ初期値から最適解に収束する。$\rho=3$ では第 2 回の $x$ の段で $z^1-u^1=0$ となり $\pm1$ がともに最小点になるので、どちらを選ぶかで行き先が変わる。3 行目:$f(x)=\sup\{\alpha x_1+\beta x_2\mid\beta+\alpha^2/4\le0\}$ と書けるので下半連続な凸関数である。最適解は $x=(0,t)$($t\ge0$)、$z=0$ で $p^*=0$、$y^*=0$ で鞍点になる。$x$ の段は $\frac{x_1^2}{x_2}+\frac12(x_1-1)^2$ の最小化で、下限 $0$ には $x_1=1$、$x_2\to\infty$ でしか近づけない。

よくある誤り

誤り正しくはなぜ
$x$ と $z$ の最適解への収束を期待する保証されるのは残差と値の収束thm-admm-convergence の後の注意
主残差だけで止める双対残差も小さいことを確かめるprop-admm-optimality
$\rho$ を大きくすれば速いと考える速さは $\rho$ に単調でないprop-admm-quadratic、例題「1 ノルムで罰した最小二乗」
変数を 3 つ以上に分けても主定理が使えると考える主定理は 2 つの変数の場合の定理証明の交差項の符号は 2 つの変数の構造を使う
凸でない問題でも最適解に近づくと考える不動点が最適でないことがある反例の表の 2 行目

補足

  • 別の見方:交互方向乗数法は、単調作用素の零点を求める Douglas–Rachford 分割法の特別な場合であり、さらに近接点法の特別な場合でもあることが知られている(BPCPE11 §3.5、pp. 23–24 の文献案内。この記事では証明しない)。
  • 分散計算:$f=\sum_if_i$ を多数の計算機に分け、各計算機の変数 $x_i$ と共通の変数 $z$ を条件 $x_i-z=0$ で結ぶと、$x$ の段は計算機ごとに独立に解ける(合意の形)。
  • 関連:条件が $x-z=0$ で $f$ が微分できるときは 近接勾配法 も使える。乗数の動かし方は Lagrange双対性 の例「双対上昇法による分解」と同じ形で、罰金の項が収束を安定させている。

関連項目

参考文献

[1]
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Foundations and Trends in Machine Learning, 2011, §3.1(pp. 13–15)、§3.2.1(p. 17)、§3.2.2(p. 17)、§3.5(pp. 23–24)、Appendix A(pp. 106–110)

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