slope trick (3) slope trick の凸共役

スポンサーリンク

概要

凸関数の凸共役(Legendre-Fenchel 変換)とその性質について、軽くまとめます。さらに、slope trick による凸関数の取り扱いと組み合わせることで、slope trick の凸共役 という新たな凸関数の取り扱いを導出します。呼称はこの記事が初出で、どういう名前が流行るのかは現時点では不明。

凸関数の凸共役

定義

$f\colon \R\longrightarrow \R\cup\{\infty\}$ (ただし恒等的には $\infty$ ではない)とします。$f$ の 凸共役 $f^{\star}$ を次の式により定義します:

$$f^{\star}(p) := \sup_{x} (px {}-{} f(x))$$

$f$ から $f^{\star}$ を得る操作は、Legendre-Fenchel 変換 とも呼ばれます。$f^{\star}(p)$ を考えることは、図形的には $f$ のグラフの下側に来るような傾き $p$ の直線のうちなるべく $y$ 切片が大きいものを考えることに対応します。

Fenchel の双共役定理

次が成り立ちます。

  • $f^{\star}$ は凸関数である
  • $f$ が凸関数で、適当な条件を満たすならば、$f = (f^{\star})^{\star}$ が成り立つ
    • 「条件」についてはここでは省略しますが、以下に述べる、閉区間上の区分線形凸関数はこの条件を満たします

$f^{\star}$ の凸性は、$f^{\star}$ が線形関数(したがって凸関数)の $\sup$ であることから分かります。$f = (f^{\star})^{\star}$ については、$f \geq (f^{\star})^{\star}$ が定義から直接分かる自明な不等式です(確かめてみてください)。逆側の不等式は、図形的には凸関数のグラフがその 包絡線 全体から復元できることを意味しています。

極小畳み込み(infimal convolution / min plus convolution)

以下、$f,g$ などと書けば「適切な条件」を満たす凸関数だとします。

$f,g$ の 極小畳み込み $f \mathop{\Box} g$ を以下のように定義します:

$$\bigl(f\mathop{\Box} g\bigr)(x) = \inf_{y}\bigl(f(x-y)+g(y)\bigr)$$

凸共役との関係として、次が成り立ちます:

  • $\bigl(f\mathop{\Box} g\bigr)^{\star}(p) = f^{\star}(p) + g^{\star}(p)$
  • $\bigl(f + g\bigr)^{\star}(p) = (f^{\star} \mathop{\Box} g^{\star})(p)$

つまり、凸共役をとると、加法と畳み込みが入れ替わります

簡単に証明を述べます。凸共役の性質 $(f^{\star})^{\star} = f$ より上の式のみ示せばよいです。

$$\begin{align*}\bigl(f\mathop{\Box} g\bigr)^{\star}(p) &= \sup_x\bigl(px {}-{} f\mathop{\Box}g(x)\bigr) = \sup_{x,y}\bigl(px {}-{} f(x-y)-g(y)\bigr) \\&= \sup_{x,y}\bigl(\bigl(p(x-y)-f(x,y)\bigr) + \bigl(py-g(y)\bigr)\bigr) \\&= \sup_{x,y}\bigl(\bigl(px-f(x)\bigr)+\bigl(py-g(y)\bigr)\bigr) = f^{\star}(p)+g^{\star}(p)\end{align*}$$


区分線形凸関数の凸共役

slope trick (1) 解説編 で解説した形の区分線形凸関数 $f$ に対して、$f^{\star}$ もやはり区分線形凸になり、そのグラフには次のような関係があります。

  • $f$ が、$x = a$ の前後で傾き $b$ から傾き $c$ に変化するとき、$f^{\star}$ は $[b,c]$ 上で傾き $a$ である

$p\in [b,c]$ に対して、$f$ のグラフの下側にある傾き $p$ の直線を考えると、$x=a$ のところで $f$ と一致するような直線が $y$ 切片最大になるためです。上で述べた性質だけだと、$y$ 軸方向の平行移動分の自由度が残りますが、これと自明な性質 $f^{\star}(0) = -\min_f$ などを合わせれば $f^{\star}$ が確定できます。

slope trick の凸共役

slope trick (1) 解説編 では、次の性質を満たす区分線形凸関数に対して、いくつかの操作を高速化しました:

  • 傾きが、すべて絶対値の小さな整数である

本記事では、凸共役が slope trick で扱った関数になるような区分線形凸関数を考えます。つまり、次を満たす区分線形凸関数です。

  • 傾きの変化点の座標が、すべて絶対値の小さな整数である

以下、$f$ がこの性質を満たすとします。$f$ に対する操作を凸共役によって $f^{\star}$ に対する操作に取り換えることで、$f^{\star}$ に対する slope trick を用いて $f$ に対する操作を高速化することを slope trick の凸共役 と呼びましょう。

slope trick では、区分線形凸関数 $F$ を次のデータによって管理しました。

  • $F$ の最小値
  • 最小値の左側での傾きの変化点全体 $L$(priority queue で持つ)
  • 最小値の右側での傾きの変化点全体 $R$(priority queue で持つ)

したがって、slope trick の凸共役では、区分線形凸関数 $f$ を次のデータによって管理します。

  • $f(0)$
  • 各非負整数 $n$ に対する $[n,n+1]$ での傾きを並べた列 $(R_0, R_1, \ldots)$ (priority queue で持つ)
  • 各非負整数 $n$ に対する $[-(n+1),-n]$ での傾きを並べた列 $(L_0, L_1, \ldots)$ (priority queue で持つ)

可能な操作

高速化できる操作を確認しましょう。以下、$N$ と書けばその時点で保持している priority queue の要素数です。

$f(0)$ の取得:$O(1)$ 時間

$f(0)$ を管理するので当たり前です。

定数関数の加算:$O(1)$ 時間

$f(0)$ に加えるだけです。

$\min_{x}\bigl(f(x){}-{}px\bigr)$ の取得、特に $\min_xf(x)$ の取得:$O(N\log N)$ 時間

これは $-f^{\star}(p)$ の計算と等価です。slope trick (1) 解説編 より

$$f^{\star}(p) = {\min}_{f^{\star}} + \sum_{l\in L}(l-p)_+ + \sum_{r\in R}(p-r)_+$$

が成り立ち、$\min_{f^{\star}} = -f(0)$ なのでよいです。slope trick は最小値の取得が容易で $f(0)$ の計算は難しいですが、slope trick 凸共役では $f(0)$ の取得が容易で最小値の取得は難しいです。

平行移動 $f(x) \gets f(x\pm 1)$:$O(\log N)$ 時間

$f$ のグラフを直接考えてもよいですが、練習も兼ねて極小畳み込みと凸共役を利用します。

$$g(x) = \begin{cases}0 & (x=1) \\ \infty & (x\neq 1)\end{cases}$$

となる $g$ をとると、$f(x+1) = \bigl(f\mathop{\Box}g\bigr)(x)$ です。よって、凸共役にうつれば $g^{\star}$ を加算する操作ができればよいです。

$g^{\star}(p) = p$ が成り立ちます。したがって、$f^{\star}(p) \gets f^{\star}(p) + p$ という操作を考えればよいことになります。

  • $L$ の最大値を $L_0$ とする。これは操作の前後でともに $f^{\star}$ が最小な点である。
  • $f^{\star}$ の最小値に、$L_0$ を加算する。したがって、$f(0)$ に $L_0$ を加算する。
  • $L_0$ を $L$ から pop して、$R$ にうつす

とすればよいです。$f(x)\gets f(x-1)$ の場合には、凸共役に $-p$ を加えることを考えれば同様にできます。

座標変化の小さな平行移動については、これらを繰りかえせばよいです。座標の大きい平行移動は(slope trick では簡単だったのに対して)slope trick の凸共役では扱いにくいです。

$cx$, $c(x-0)_+$, $c(0-x)_+$ の加算:$O(1)$ 時間

これは凸共役をとらず $f$ のまま考えれば自明です。$R$ 全体に $c$ を加算したり、$L$ 全体に $-c$ を加算したりすればよいです。

平行移動と組み合わせれば、絶対値の小さい整数 $a$ に対して $c(x-a)_+$ などの加算ができます。また、これらを両方行えば、$c|x|$ の形の関数の加算が行えます。

slope trick では、大きな $c$ に対する $c|x|$ の加算などは扱えませんでしたが、slope trick の凸共役では $c$ が大きくても簡単です。

スライド最小値関数 $f(x) \gets \min_{y\in [x-b,x-a]}f(y)$:$O((|a|+|b|)\log N)$ 時間

極小畳み込みを用いて、計算方法を導出しましょう。

$$g(x) = \begin{cases}0 & (x\in [a,b])\\ \infty & (x\notin [a,b])\end{cases}$$

とすると、$f$ を $f\mathop{\Box} g$ にうつす操作が求めるものです。したがって、$f^{\star}$ に $g^{\star}$ を加える操作を考えます。

$g^{\star}$ は $x=0$ の前後で傾きが $a$ から $b$ に変化するような折れ線です。これは $ax + (b-a)(x-0)_+$ などと書けるので、$f^{\star}$ に対する slope trick の基本操作 $O(|a|+|b|)$ 回でこれが行えます。

問題例

タイトルとURLをコピーしました