リプレゼンター定理

最終更新: 2017-09-16 13:27

定理の主張

ψ\psiX\mathcal{X}からヒルベルト空間への写像、f: RmRf\colon\ \mathbb{R}^{m} \to \mathbb{R}を任意の関数、R: R+RR \colon\ \mathbb{R}_{+} \to \mathbb{R}を単調非減少な関数とする。

このとき、

minw(f(w,ψ(x1),,w,ψ(xm))+R(w))\min_{\mathbf{w}} \left(f(\langle\mathbf{w}, \psi(\mathbf{x}_1)\rangle, \cdots, \langle\mathbf{w}, \psi(\mathbf{x}_m)\rangle) + R(||\mathbf{w}||) \right)

の最適解は、あるαRm\mathbf{\alpha} \in \mathbb{R}^mを用いてw=i=1mαiψ(xi)\mathbf{w} = \sum_{i=1}^{m} \alpha_i \psi(\mathbf{x}_i)という形で書くことができる。

証明

w\mathbf{w}^*を最適解とする。

このとき、全てのiiについてu,ψ(xi)=0\langle\mathbf{u}, \psi(\mathbf{x}_i)\rangle = 0を満たすu\mathbf{u}を用いて、

w=i=1mαiψ(xi)+u\mathbf{w}^* = \sum_{i=1}^{m} \alpha_i\psi(\mathbf{x}_i) + \mathbf{u}

と書くことができる。
w\mathbf{w}^*{ψ(xi)}\{\psi(\mathbf{x}_i)\}が張る部分空間内のベクトルとその直交補空間内のベクトルに分解したということ)

w=wu\mathbf{w}=\mathbf{w}^*-\mathbf{u}とする。

このとき、

w,ψ(xi)=wu,ψ(xi)=w,ψ(xi)u,ψ(xi)=w,ψ(xi)\begin{aligned} \langle\mathbf{w}, \psi(\mathbf{x}_i)\rangle &= \langle\mathbf{w}^{*}-\mathbf{u}, \psi(\mathbf{x}_i)\rangle \\ &= \langle\mathbf{w}^{*}, \psi(\mathbf{x}_i)\rangle - \langle\mathbf{u}, \psi(\mathbf{x}_i)\rangle\\ &= \langle\mathbf{w}^{*}, \psi(\mathbf{x}_i)\rangle \end{aligned}

より、

f(w,ψ(x1),,w,ψ(xm))=f(w,ψ(x1),,w,ψ(xm))f(\langle\mathbf{w}, \psi(\mathbf{x}_1)\rangle, \cdots, \langle\mathbf{w}, \psi(\mathbf{x}_m)\rangle) = f(\langle\mathbf{w}^{*}, \psi(\mathbf{x}_1)\rangle, \cdots, \langle\mathbf{w}^{*}, \psi(\mathbf{x}_m)\rangle)

が成り立つ。

また、

w2=wu2=(wu)T(wu)=wTwwTuuTw+uTu=w2+u2\begin{aligned} ||\mathbf{w}^*||^2 &= ||\mathbf{w} - \mathbf{u}||^2 \\ &= (\mathbf{w}-\mathbf{u})^{\mathrm{T}}(\mathbf{w}-\mathbf{u}) \\ &= \mathbf{w}^{\mathrm{T}}\mathbf{w} - \mathbf{w}^{\mathrm{T}}\mathbf{u} - \mathbf{u}^{\mathrm{T}}\mathbf{w} + \mathbf{u}^{\mathrm{T}}\mathbf{u} \\ &= ||\mathbf{w}||^2 + ||\mathbf{u}||^2 \end{aligned}

よって、ww||\mathbf{w}||^* \geq ||\mathbf{w}||
RRは単調非減少であるので、w\mathbf{w}^*が最適解であるためにはu=0||\mathbf{u}|| = 0しかあり得ない。

したがって、最適解は

w=i=1mαiψ(xi)\mathbf{w}^* = \sum_{i=1}^{m} \alpha_i\psi(\mathbf{x}_i)

という形で書けることが示された。