交互方向乗数法(alternating direction method of multipliers, ADMM)とは、2 つの変数に分かれた凸関数の和 $f(x)+g(z)$ を 1 次の等式 $Ax+Bz=c$ の条件のもとで最小化するため、条件を乗数と 2 次の罰金で目的関数に繰り込んだ拡張 Lagrange 関数を $x$、$z$ の順に交互に最小化し、乗数を条件の残差の分だけ動かす反復法である。各段では片方の変数だけの易しい問題を解けばよく、LASSO などの罰金つきの最小二乗や分散計算に使う。$f$ と $g$ が凸で、条件なしの Lagrange 関数に鞍点があり、各段の最小化に解があれば、条件の残差は 0 に近づき、目的関数の値は最適値に近づく。
前提知識: 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 点で有限の値をとるとき 真凸 という。
$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 回ずつの最小化に置きかえたものと見なせる。
この記事の評価を使う条件をまとめる。
| 量 | 式 | 意味 | 根拠 |
|---|---|---|---|
| 主残差 | $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 |
$\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$ について次が成り立つ。
$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$ は有界である。
$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)。
$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$ の選び方は、主残差と双対残差の大きさを見て反復の途中で調節することが多い。
$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}$ 倍になる。
近接勾配法 の例題と同じ $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 がいちばん遅い。
$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 行目 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する