機械学習系の本には, SVMの例などで双対問題の導出の仕方は載っているが, なぜそのようにして良いのかについては触れられていない.
うまく説明されている本は, Convex OptimizationのDualiyの節である.
日本語は見当たらなかったため, ここに記す.

(LaTeXが重いので, 式が表示されるまでお待ち下さい)

Keywords: Lagrange, Dual Problem, Duality, Slater condition, KKT conditon

実際に最適化を体験してみたい方は凸最適化ソルバーCVXPYの紹介を参照.

ラグランジュ双対関数

理論のみを紹介する.
具体例などは, Convex OptimizationのDualiyを参照してください.

ラグランジアン

次の最小化問題を考える.

\begin{split}
\min_{x\in\mathbb{R}^n} &~ f_0(x)\\
\mathrm{s.t.} &~ f_i(x)\le 0,~ i=1,\ldots,m\\
              &~ h_i(x)=0, ~i=1,\ldots, p
\end{split}

実行可能領域は空でないとする
この最適化問題の最適値を$p^\star$と書く
凸性は特に仮定しない
主問題という

ラグランジアンは次のように定義される.

L(x, \lambda, \nu):=f_0(x)+\sum_{i=1}^m\lambda_i f_i(x)+\sum_{i=1}^p\nu_i h_i(x)

$\lambda_i, \nu_i$はラグランジュ未定乗数

ラグランジュ双対関数

ラグランジュ双対関数は次のように定義される.

\begin{split}
g(\lambda,\nu)&:=\inf_{x\in D} L(x, \lambda, \nu)\\
&=\inf_{x\in D} \left(f_0(x)+\sum_{i=1}^m\lambda_i f_i(x)+\sum_{i=1}^p\nu_i h_i(x)\right)
\end{split}

$D:=\bigcap_{i=0}^m \mathrm{dom}(f_i) \cap \bigcap_{i=1}^p \mathrm{dom}(h_i)$
双対関数は, $(\lambda,\nu)$のアフィン関数の各点でのinfになっているため, 必ずconcave(上に凸)となる (もとの問題が凸でなくても)

証明してみた:

\begin{split}
	 & g(t\lambda_a+(1-t)\lambda_b, t\nu_a+(1-t)\nu_b)\\
	=&\inf_{x\in\mathcal{D}}\left(tL(x,\lambda_a,\nu_a)+(1-t)L(x,\lambda_b,\nu_b)\right)\\
	\ge& t\inf_{x\in\mathcal{D}}L(x,\lambda_a,\nu_a)+(1-t)L(x,\lambda_b,\nu_b)\\
	=& tg(\lambda_a,\nu_a)+(1-t)g(\lambda_b,\nu_b)
\end{split}

最適値の下限

任意の$\lambda\ge0, \nu$に対して, 次が成り立つ.

g(\lambda,\nu)\le p^\star

証明:

$\tilde{x}$を実行可能解とする: $f_i(\tilde{x})\le 0, h_i(\tilde{x}) = 0$
$\lambda\ge 0$を仮定

このとき, $L(\tilde{x},\lambda,\nu)$の値は, $f_0(\tilde{x})$でおさえられる:

L(\tilde{x},\lambda,\nu)=f_0(\tilde{x})+\underbrace{\sum_{i=1}^{m}\lambda_if_i(\tilde{x})}_{\le0}+\underbrace{\sum_{i=1}^{p}\nu_ih_i(\tilde{x})}_{=0}\le f_0(\tilde{x})

ゆえに, $g(\lambda, \nu)$は$f_0(\tilde{x})$でおさえられる:

\therefore~g(\lambda, \nu)=\inf_{x\in\mathcal{D}}L(x,\lambda,\nu)\le L(\tilde{x},\lambda,\nu)\le f_0(\tilde{x})

任意の$\tilde{x}$に対して, $g(\lambda, \nu)\le f_0(\tilde{x})$が成り立つため, $g(\lambda, \nu)\le p^\star$が成り立つ.

結論: 双対関数の値は, 主問題の最適値を超えない

線形近似による解釈

元の主問題と等価な次の最小化問題を考える.

\min_{x}~f_0(x)+\sum_{i=1}^{m}I_-(f_i(x))+\sum_{i=1}^{p}I_0(h_i(x))

ただし, $I_{-},I_{0}$は指示関数:

I_-(u):=\begin{cases}
0&u\le 0\\
\infty& u>0
\end{cases},~~~
I_0(u):=\begin{cases}
0&u = 0\\
\infty& u\ne 0
\end{cases},

最小化するのが目的であるが, 指示関数は制約を満たさないと無限大になってしまう.
この指示関数は, 制約違反に対する不満度を表していると解釈できる.

ここで, $I_-(u)$を$\lambda_i u (\lambda_i\ge 0)$, $I_0(u)$を$\nu_iu$というように指示関数を近似する.

\min_{x}~L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^{m}\lambda_i f_i(x)+\sum_{i=1}^{p}\nu_i h_i(x)

これは制約違反をソフトに近似したものと考えられる
もちろん, 制約を違反するほど不満度は上昇するようになっている
- 不等式制約に関して, 違反しているとき$f_i(x)>0$であり, $\lambda_if_i(x)\ge0$
任意の$u$に関して, $\lambda_iu \le I_-(u)$と$\nu_iu \le I_0(u)$が成り立つため, 双対関数が元の主問題の下限を与えることがわかる

共役関数

$f$の共役関数$f^*$は次で定義される.

f^*(y)=\sup_{x\in\mathrm{dom} f}(y^\top x-f(x)).

共役関数と双対問題には密接な関係がある. (フェンシェル双対定理)
たとえば, 機械学習のよくある形

\min_{w\in\mathbb{R}^d} f(Xw)+g(w)

の双対問題は,

\max_{\alpha\in\mathbb{R}^n} -f^*(-\alpha)-g^*(X^\top\alpha)

というように共役関数を使って表現できる.
そのため, 凸共役を覚えておけば, 形式的に双対問題を導出できる.

証明は簡単で, ラグランジアン$L(w,z,\alpha)=f(z)+g(w)+\alpha^\top(z-Xw)$を考えて, 双対関数の定義にしたがって$w\in\mathbb{R}^d,z\in\mathbb{R}^n$に関して最小化するだけだ.
ちなみに, このとき最適解$w^\star,\alpha^\star$に関して

$$
w^\star \in \partial g^*(X^\top \alpha^\star),
\ \ \ \alpha^\star \in -\partial f(Xw^\star)
$$

が成立する (KKT条件).

ラグランジュ双対問題

双対関数から双対問題へ.

ラグランジュ双対問題

ここまでで, 双対関数が主問題の下限を与えることを示した.
自然な疑問は, 「ラグランジュ双対関数から得られる最も良い下限はどれくらいなのか?」ということだ.
最も良い下限は次の最大化問題を解くことで得られる.

\begin{split}
\max_{\lambda,\nu}~&g(\lambda,\nu)\\
\mathrm{s.t.} ~&\lambda\ge0
\end{split}

これは, ラグランジュ双対問題と呼ばれる
双対実行可能領域: $(\lambda,\nu)$に関して, $\lambda\ge0$かつ$g(\lambda,\nu)>-\infty$
$(\lambda^\star,\nu^\star)$: 双対問題の最適解
$d^\star$: 双対問題の最適値
双対問題は必ず凸最適化問題
- 目的関数が必ずconcaveで, 制約が凸であるため
- これは, 主問題が凸最適化でなくても成り立つ

弱双対性

d^\star\le p^\star

主問題の凸性にかかわらず, 成り立つ
この不等式は, $p^\star, d^\star$が発散しないときに成り立つ
$p^\star - d^\star$を双対ギャップという
- よく最適化アルゴリズムの停止条件に使われる
$p^\star$を求めることが難しいときに$d^\star$を求めることで, $p^\star$の下限を知ることができる
- 双対問題は必ず凸であるため, 多くの場合効率的に解ける

強双対性

d^\star=p^\star

主問題の最適値が双対問題の最適値と一致するという性質
強双対性は常には成り立たない

もし主問題が凸, すなわち:

\begin{split}
\min_{x\in\mathbb{R}^n} &~ f_0(x)\\
\mathrm{s.t.} &~ f_i(x)\le 0, ~i=1,\ldots,m\\
              &~ Ax=b
\end{split}

で$f_0,\ldots,f_m$が凸なら, たいていは(いつもではない)強双対性が成り立つ.

たとえば, SVMの最適化問題は凸であり, 強双対性が成り立つため, 主問題/双対問題のどちらを解いてもよい.

スレーター条件

次を満たすような$x\in\mathrm{relint}(D)$が存在することをいう.

f_i(x)<0,~i=1,\ldots,m,~~~Ax=b

主問題が凸でスレーター条件を満たすとき, 強双対性が成り立つ
スレーター条件は強双対性の十分条件である (必要十分ではない)

もし, $f_1,\ldots,f_k$がアフィンなら, より弱い条件が成り立てばよい:

f_i(x)\le 0,~i=1,\ldots,k,~~~f_i(x)<0,~i=k+1,\ldots,m,~~~Ax=b

言い換えれば, アフィンの不等式制約は等号を含んでもよい

補足: int(内部)とrelint(相対的内部)

$\mathrm{int}(S)$:

Sに含まれる最大開集合
Sから境界上の点を取り除いたもの

$\mathrm{relint}(S)$:

Sによって拘束される線形空間上で, Sから境界上の点を取り除いたもの.

intとrelintの違いのイメージとしては, まっすぐな下敷きのような平面を考えたとき, intは下敷きの平面ごと取り除いてしまい空集合になるのに対して, relintは下敷きの縁を削って残った部分.

Example1 $S=\lbrace(x_1,x_2)\mid 0\le x_1\le 1,x_2=0\rbrace$

\mathrm{int}(S)=\emptyset, \mathrm{relint}(S)=\{(x_1,x_2)\mid 0 < x_1 < 1,x_2=0\}, (\mathrm{aff}(S)=\{(x_1,x_2)\in\mathbb{R}^2\mid x_2=0\})

Example2 $S= \lbrace (x_1,x_2)\mid 0\le x_1\le 1,0\le x_2\le 1\rbrace$

\mathrm{int}(S)=\mathrm{relint}(S)=\{(x_1,x_2)\mid 0 < x_1 < 1,0<x_2<1\}, (\mathrm{aff}(S)=\{(x_1,x_2)\in\mathbb{R}^2\})

最適性条件

特に主問題の凸性を仮定しない.

相補性条件

特に, 強双対性条件を満たすと仮定すると,

\begin{split}
f_0(x^\star)&=g(\lambda^\star,\nu^\star)\\
&=\inf_{x\in D} \left(f_0(x)+\sum_{i=1}^m\lambda_i^\star f_i(x)+\sum_{i=1}^p\nu_i^\star h_i(x)\right)\\
&\le f_0(x^\star)+\sum_{i=1}^m\lambda_i^\star f_i(x^\star)+\sum_{i=1}^p\nu_i^\star h_i(x^\star)\\
&\le f_0(x^\star)
\end{split}

1行目: 強双対性
2行目: 双対関数の定義
3行目: $\inf$の定義
4行目: $\lambda_i^\star\ge0, f_i(x^\star)\le0, ~i=1,\ldots,m$と$h_i(x^\star)=0, ~i=1,\ldots,p$

1,3行目と3,4行目を考慮すると,

\sum_{i=1}^m\lambda_i^\star f_i(x^\star)=0.

和の各項は同符号であるため,

\lambda_i^\star f_i(x^\star)=0,~~~i=1,\ldots,m.

これを相補性条件という
- もし$\lambda_i^\star>0$なら, $f_i(x^\star)=0$
- もし$f_i(x^\star)<0$なら, $\lambda_i^\star=0$

KKT条件 (Karush-Kuhn-Tucker条件)

強双対性を仮定すると, $x^\star$は$L(x,\lambda^\star,\nu^\star)$を最小化するため, $x^\star$における勾配は0である:

\nabla f_0(x^\star)+\sum_{i=1}^m\lambda_i^\star \nabla f_i(x^\star)+\sum_{i=1}^p\nu_i^\star\nabla h_i(x^\star)=0

ゆえに, 最適解で成り立つ式を列挙すると:

$f_i(x^\star)\le 0,~i=1,\ldots,m$
$h_i(x^\star)= 0,~i=1,\ldots,p$
$\lambda_i\ge0,~i=1,\ldots,m$
$\lambda_i f_i(x^\star)= 0,~i=1,\ldots,m$
$\nabla f_0(x^\star)+\sum_{i=1}^m\lambda_i^\star \nabla f_i(x^\star)+\sum_{i=1}^p\nu_i^\star\nabla h_i(x^\star)=0$

これがいわゆるKKT条件である. (必要条件)
まとめると, 強双対性を満たすなら, 最適解において主変数と双対変数はKKT条件を満たさなければならない.

主問題が凸であるとき, KKT条件は十分条件にもなる.
つまり, ある点$\tilde{x},\tilde{\lambda}, \tilde{\nu}$がKKT条件を満たすなら, $\tilde{x}=x^\star, \tilde{\lambda}=\lambda^\star, \tilde{\nu}=\nu^\star$.
十分条件の証明:

\begin{split}
g(\tilde{\lambda},\tilde{\nu})&=L(\tilde{x},\tilde{\lambda},\tilde{\nu})\\
&= f_0(\tilde{x})+\sum_{i=1}^m\tilde{\lambda}_i f_i(\tilde{x})+\sum_{i=1}^p\tilde{\nu}_i h_i(\tilde{x})\\
&= f_0(\tilde{x})
\end{split}

1行目: $\tilde{x}$がKKT条件の最後の条件を満たすため
- 主問題が凸であるため, $L(x,\tilde{\lambda},\tilde{\nu})$は$x$に関して凸である ($\because\tilde{\lambda}_i\ge0$)
- $\therefore~L$を最小化する$x$は, 勾配が0である
2行目: ラグランジアンの定義
3行目: $\tilde{x}$がKKT条件の2つ目と4つ目を満たすため

この式は, 双対ギャップが0であることを意味するため, $\tilde{x},\tilde{\lambda}, \tilde{\nu}$は最適解である.

結論: スレーター条件を満たすとき, KKT条件は最適性の必要十分条件となる

まとめ

Convex Optimizationはわかりやすい
- 幾何的な解釈や鞍点解釈などの説明も載っているので興味のある方は読むよい
双対問題は, 主問題の指示関数の線形緩和から生まれる
双対問題は, 主問題の下限を最もよくおさえるための問題である
凸最適化問題なら大抵の場合, 主問題の最適値=双対問題の最適値
スレーター条件を満たすとき, KKT条件は最適性の必要十分条件となる