凸錐
概要
凸錐（convex cone）とは、$\mathbb{R}^n$ の空でない部分集合 $K$ で、$x,y\in K$ と $s,t\ge0$ について $sx+ty\in K$ となるもの、すなわち和と $0$ 以上の実数倍で閉じた集合である。非負象限、2 次錐、半正定値対称行列の全体などが例である。有限個のベクトルが生成する錐は閉じていて、有限個の 1 次不等式 $Ax\le0$ で定まる錐と同じもの（Minkowski–Weyl の定理）であり、閉凸錐は双対錐 $K^*=\{y\mid x\cdot y\ge0\ (x\in K)\}$ を 2 回とると元に戻る。Farkas の補題、閉凸錐への射影と Moreau の分解を通して、線形計画法と凸最適化の双対性の土台になる。
平面の 2 つのベクトル $a,b$ について、$s,t\ge0$ を動かした $sa+tb$ の全体は、原点を頂点とする角の形の領域になる。この領域は、2 点を結ぶ線分を含み（凸）、点を $0$ 以上の実数倍しても外に出ない。このような集合を 凸錐（convex cone）という。$\mathbb{R}^n$ の $0$ 以上の成分をもつベクトルの全体、$\{(x,t)\mid\|x\|\le t\}$ の形の「アイスクリームの形の錐」、半正定値対称行列の全体などが例で、線形計画法・凸最適化の制約や、ベクトルの大小を比べる順序の土台として現れる。
凸錐は、部分空間の条件「和と実数倍で閉じる」の実数倍を $0$ 以上の倍に弱めたものと見られる。部分空間の直交補空間にあたるのが 双対錐で、閉じた凸錐は双対錐を 2 回とると元に戻る。この記事では、有限個のベクトルが生成する錐が閉じていること（錐の Carathéodory の定理から導く）、双対錐の双対、有限生成の錐と有限個の不等式で定まる錐が同じものであること（Minkowski–Weyl の定理）、閉凸錐への最短点の特徴づけと Moreau の分解を証明する。
定義
$\mathbb{R}^n$ の内積を $x\cdot y$、ノルムを $\|x\|=\sqrt{x\cdot x}$ と書く。
空でない $K\subset\mathbb{R}^n$ が 錐（cone）であるとは、$x\in K$ と $t\ge0$ について $tx\in K$ となることをいう。凸集合である錐を 凸錐（convex cone）という。
錐は $0=0\cdot x$ を含む。文献によっては $t>0$ の倍だけを課し、$0$ を含まない集合も凸錐と呼ぶ（rem-cc-conventions）。
空でない $K\subset\mathbb{R}^n$ について、次は同値である。
- $K$ は凸錐である。
- $x,y\in K$ なら $x+y\in K$ であり、$x\in K$、$t\ge0$ なら $tx\in K$ である。
- $K$ の有限個の点の $0$ 以上の係数の 1 次結合 $\sum_{i=1}^m\lambda_ix_i$（$\lambda_i\ge0$）はすべて $K$ に属する。
1 ⇒ 2：$x+y=2\bigl(\frac12x+\frac12y\bigr)$ で、括弧の中は凸性から $K$ に属する。2 ⇒ 3：各 $\lambda_ix_i$ が $K$ に属し、和も $K$ に属する（$m=0$ の空の和 $0$ も $K$ に属する）。3 ⇒ 1：$m=1$ の場合が錐であること、$m=2$、$\lambda_1+\lambda_2=1$ の場合が凸性である。$\square$
3 の形の和を $x_1,\dots,x_m$ の 錐結合（conic combination）という。
$S\subset\mathbb{R}^n$ の点の錐結合の全体を $\operatorname{cone}S$ と書き、$S$ が 生成する錐 という（$\operatorname{cone}\emptyset=\{0\}$）。有限集合が生成する錐を 有限生成の錐 という。行列 $A$ によって $\{x\in\mathbb{R}^n\mid Ax\le0\}$ と書ける集合を 多面錐（polyhedral cone）という。
$\operatorname{cone}S$ は錐結合の錐結合がまた錐結合であることから凸錐であり、prop-cc-char の 3 により $S$ を含むどの凸錐にも含まれる。したがって $S$ を含む最小の凸錐である。多面錐は原点を通る有限個の閉半空間 $\{a_i\cdot x\le0\}$ の共通部分で、凸錐である。
$K\subset\mathbb{R}^n$ について
$$
K^*:=\{y\in\mathbb{R}^n\mid\text{すべての }x\in K\text{ で }x\cdot y\ge0\}
$$
を $K$ の 双対錐（dual cone）、$K^\circ:=-K^*=\{w\mid\text{すべての }x\in K\text{ で }x\cdot w\le0\}$ を 極錐（polar cone）という。$K^{**}:=(K^*)^*$ と書く。
$y\in K^*$ は「$K$ が閉半空間 $\{x\mid x\cdot y\ge0\}$ に含まれる」ことである。双極定理 の極錐 $K^-$ はここでの $K^\circ$ にあたる。$K$ が錐なら、これは 双極定理 の極集合 $K^\circ$（内積が $1$ 以下という条件で定める）とも一致するが、錐でない集合では両者は異なる。
凸錐 $K$ が 尖っている（pointed）とは $K\cap(-K)=\{0\}$、つまり直線を含まないことをいう。閉じていて、尖っていて、内部が空でない凸錐を 固有錐（proper cone）という。凸錐 $K$ について、$y-x\in K$ のとき $x\le_Ky$ と書く。
$\le_K$ は反射的（$0\in K$）で推移的（$K+K\subset K$）であり、$K$ が尖っていれば反対称的になる（$x\le_Ky$ かつ $y\le_Kx$ なら $y-x\in K\cap(-K)$）。こうして尖った凸錐は $\mathbb{R}^n$ の半順序を与え、この半順序は和と $0$ 以上の倍と両立する（$x\le_Ky$ なら $x+z\le_Ky+z$、$tx\le_Kty$）。
例
- 非負象限 $\mathbb{R}^n_+:=\{x\mid x_i\ge0\ (i=1,\dots,n)\}$。単位ベクトル $e_1,\dots,e_n$ が生成する有限生成の錐であり、$-x_i\le0$ で定まる多面錐でもある。固有錐で、$\le_{\mathbb{R}^n_+}$ は成分ごとの大小である。
- 平面の角。$a,b\in\mathbb{R}^2$ が平行でないとき、$\operatorname{cone}\{a,b\}=\{sa+tb\mid s,t\ge0\}$ は $a$ と $b$ の間の角の領域である（点の存在範囲と凸結合 の「$s\ge0$、$t\ge0$」の領域）。
- 2 次錐（Lorentz 錐）$L:=\{(x,t)\in\mathbb{R}^{n}\times\mathbb{R}\mid\|x\|\le t\}$。$(x,t),(y,s)\in L$ なら $\|x+y\|\le\|x\|+\|y\|\le t+s$ なので和で閉じ、倍で閉じることは明らかである。$n\ge2$ では有限生成でない（ex-cc-lorentz-not-fg）。
- 半正定値錐。$n$ 次実対称行列の空間 $\mathrm{Sym}_n$ に内積 $\langle X,Y\rangle=\operatorname{tr}(XY)$ を入れる。半正定値行列の全体 $\mathrm{Sym}_n^+$ は、$q^{\mathsf T}(X+Y)q=q^{\mathsf T}Xq+q^{\mathsf T}Yq$ から凸錐である。$\mathrm{Sym}_n$ はこの内積で $\mathbb{R}^{n(n+1)/2}$ と同じに扱えるので、以下の定理はそのまま当てはまる（双対錐も $\mathrm{Sym}_n$ の中でとる）。
- 半空間と部分空間。$a\ne0$ について $\{x\mid a\cdot x\ge0\}$、および線形部分空間は閉凸錐である。$0$ でない部分空間と、$n\ge2$ のときの半空間は、直線を含むので尖っていない。
- 凸でない錐。座標軸の和集合 $\{x\mid x_1x_2=0\}\subset\mathbb{R}^2$ は錐だが凸ではない。
$n\ge2$ とする。要点：境界の点 $p_\theta$ を錐結合で表すと、使う生成元はどれも $p_\theta$ の正の倍に限られ、向きの異なる $p_\theta$ が無限個あるので、有限個の生成元では足りない。
詳しい確かめを開く
$L$ が $r_1,\dots,r_m$ で生成されるとすると、$r_j\ne0$ としてよい。$L$ の境界の点 $p_\theta:=(\cos\theta,\sin\theta,0,\dots,0,1)$ は、$L$ の $0$ でない 2 点の和 $p_\theta=u+v$ に書けるとき、$u,v$ はどちらも $p_\theta$ の正の倍である。実際、$u=(x,t)$、$v=(y,s)$ とすると $1=\|x+y\|\le\|x\|+\|y\|\le t+s=1$ の等号から $\|x\|=t$、$\|y\|=s$ で、$x,y$ は同じ向きである。よって $p_\theta=\sum_j\lambda_jr_j$（$\lambda_j>0$ の項だけ残す）のどの $r_j$ も $p_\theta$ の正の倍である（1 つの項と残りの項の和に分けて、項の数についての帰納法で示す。残りの和も $L$ に属する）。$\theta$ は無限個あり、向きの異なる $p_\theta$ には共通の $r_j$ がないので、$r_j$ が有限個であることに反する。
有限生成の錐は閉じている
凸集合 の定理「Carathéodoryの定理」（$\mathbb{R}^n$ の凸包の点は $n+1$ 個の点の凸結合で書ける）に対応して、錐では一次独立な点の錐結合で足りる。
$S\subset\mathbb{R}^n$ とする。$\operatorname{cone}S$ のどの点も、$S$ の一次独立な点（したがって高々 $n$ 個）の錐結合として書ける。
$x\in\operatorname{cone}S$ を、$S$ の相異なる点の錐結合 $x=\sum_{i=1}^m\lambda_ix_i$ のうち $m$ が最小のもので表す（$x=0$ なら $m=0$）。最小性からすべての $\lambda_i$ は正である。$x_1,\dots,x_m$ が一次従属だとすると、すべては $0$ でない $\mu_1,\dots,\mu_m$ で $\sum_i\mu_ix_i=0$ となるものがあり、符号を取り替えて $\mu_i>0$ となる $i$ があるとしてよい。
$$
\tau:=\min\Bigl\{\frac{\lambda_i}{\mu_i}\Bigm|\mu_i>0\Bigr\}>0,\qquad\lambda_i':=\lambda_i-\tau\mu_i
$$
とおくと、$\mu_i\le0$ なら $\lambda_i'\ge\lambda_i>0$、$\mu_i>0$ なら $\tau$ の定め方から $\lambda_i'\ge0$ で、最小値をとる $i$ では $\lambda_i'=0$ である。$\sum_i\lambda_i'x_i=x-\tau\sum_i\mu_ix_i=x$ なので、$x$ は $m-1$ 個以下の点の錐結合になり、$m$ の最小性に反する。よって $x_1,\dots,x_m$ は一次独立で、$m\le n$ である。$\square$
$a_1,\dots,a_m\in\mathbb{R}^n$ の生成する錐 $\operatorname{cone}\{a_1,\dots,a_m\}$ は $\mathbb{R}^n$ の閉集合である。
段 1（一次独立な場合）。$b_1,\dots,b_k$ が一次独立なら、$T(s):=\sum_{i=1}^ks_ib_i$ で定まる線形写像 $T\colon\mathbb{R}^k\to\mathbb{R}^n$ は単射である。単位球面 $\{\|s\|=1\}$ はコンパクトで、その上の連続関数 $\|T(s)\|$ は正の最小値 $c$ をとるので、$\|T(s)\|\ge c\|s\|$ がすべての $s$ で成り立つ。$s^{(j)}\in\mathbb{R}^k_+$ で $T(s^{(j)})\to y$ とすると、$\|s^{(j)}-s^{(l)}\|\le c^{-1}\|T(s^{(j)})-T(s^{(l)})\|$ から $(s^{(j)})$ は Cauchy 列であり、極限 $s$ は閉集合 $\mathbb{R}^k_+$ に属し、$y=T(s)$ である。よって $\operatorname{cone}\{b_1,\dots,b_k\}=T(\mathbb{R}^k_+)$ は閉じている。
段 2（一般の場合）。thm-cc-caratheodory により、$\operatorname{cone}\{a_1,\dots,a_m\}$ は、$\{a_1,\dots,a_m\}$ の一次独立な部分集合 $B$ にわたる $\operatorname{cone}B$ の和集合である。$B$ は有限個しかなく、段 1 により各 $\operatorname{cone}B$ は閉じているので、和集合も閉じている。$\square$
有限個という仮定は外せない。閉集合が生成する錐でも、生成系が無限なら閉じているとは限らない（ex-cc-counterexamples の 1）。
双対錐
$K,K_1,K_2\subset\mathbb{R}^n$ とする。
- $K^*$ は閉凸錐である。
- $K_1\subset K_2$ なら $K_2^*\subset K_1^*$ である。
- $K^*=(\operatorname{cone}K)^*=(\overline K)^*$ であり、$K\subset K^{**}$ である。
- 線形部分空間 $V$ について $V^*=V^\perp$ である。
- $(\mathbb{R}^n_+)^*=\mathbb{R}^n_+$、$L^*=L$、$(\mathrm{Sym}_n^+)^*=\mathrm{Sym}_n^+$ である（ex-cc-basic の記号）。
要点：1〜4 は定義から分かる。5 は、試すベクトルを $e_i$、$(0,1)$ と $(-y/\|y\|,1)$、$qq^{\mathsf T}$ にとって $K^*\subset K$ を示し、逆向きは Cauchy–Schwarz の不等式と固有分解による。
詳しい証明を開く
1：$K^*$ は閉半空間 $\{y\mid x\cdot y\ge0\}$（$x\in K$）の共通部分である（$K=\emptyset$ なら $K^*=\mathbb{R}^n$）。2 は定義から分かる。3：$y\in K^*$ なら、$y$ との内積は $K$ の点の錐結合でも $0$ 以上で、極限でも $0$ 以上なので、$K^*\subset(\operatorname{cone}K)^*$、$K^*\subset(\overline K)^*$ である。逆の包含は 2 から分かる。$x\in K$、$y\in K^*$ なら $x\cdot y\ge0$ なので $x\in K^{**}$ である。4：$v\in V$ なら $-v\in V$ なので、$y\in V^*$ は $v\cdot y\ge0$ と $-v\cdot y\ge0$ を満たす。
5：$\mathbb{R}^n_+$ は、$y\in(\mathbb{R}^n_+)^*$ を $e_i$ と内積をとれば $y_i\ge0$ で、逆は成分ごとの積の和から分かる。$L$：$(x,t),(y,s)\in L$ なら $x\cdot y+ts\ge-\|x\|\|y\|+ts\ge0$ なので $L\subset L^*$ である。逆に $(y,s)\in L^*$ なら、$(0,1)\in L$ との内積から $s\ge0$、$y\ne0$ のときは $(-y/\|y\|,1)\in L$ との内積から $s-\|y\|\ge0$ で、$(y,s)\in L$ である。$\mathrm{Sym}_n^+$：$Y$ が半正定値でなければ $q^{\mathsf T}Yq< 0$ となる $q$ があり、$X=qq^{\mathsf T}\in\mathrm{Sym}_n^+$ について $\operatorname{tr}(XY)=q^{\mathsf T}Yq< 0$ である。逆に $X,Y$ が半正定値なら、$X=\sum_i\lambda_iq_iq_i^{\mathsf T}$（$\lambda_i\ge0$、固有分解）と書けて $\operatorname{tr}(XY)=\sum_i\lambda_iq_i^{\mathsf T}Yq_i\ge0$ である。$\square$
5 のように $K^*=K$ となる錐を 自己双対 という。次の定理が双対錐の中心の性質である。
任意の $K\subset\mathbb{R}^n$ について $K^{**}=\overline{\operatorname{cone}K}$ である。とくに $K$ が閉凸錐なら $K^{**}=K$ である。
$C:=\overline{\operatorname{cone}K}$ とおく。prop-cc-dual-basic の 3 から $K\subset K^{**}$ で、$K^{**}$ は閉凸錐なので（同じ命題の 1）$C\subset K^{**}$ である。
逆に $x_0\notin C$ とする。$C$ は $0$ を含む閉凸集合（凸集合の閉包は凸）なので、凸包 の定理「点と閉凸集合の分離」の 1 により、$a\in\mathbb{R}^n$ と $b\in\mathbb{R}$ で、すべての $x\in C$ について $a\cdot x\le b< a\cdot x_0$ となるものがある。$0\in C$ から $b\ge0$ で、$a\cdot x_0>0$ である。$x\in C$ と $t>0$ について $tx\in C$ なので $ta\cdot x\le b$、すなわち $a\cdot x\le b/t$ で、$t\to\infty$ として $a\cdot x\le0$ を得る。よって $y:=-a$ は $C$ の上で $x\cdot y\ge0$ を満たし、$y\in C^*=K^*$ である（prop-cc-dual-basic の 3）。一方 $x_0\cdot y< 0$ なので $x_0\notin K^{**}$ である。$\square$
$K^*$ を $K^\circ=-K^*$ に読み替えると、これは 双極定理 の系「極錐の双極定理」と同じ主張である。部分空間 $V$ では prop-cc-dual-basic の 4 から $(V^\perp)^\perp=V$ となる。
Farkas の補題と Minkowski–Weyl の定理
thm-cc-closed と thm-cc-bidual を合わせると、有限生成の錐の外の点は、原点を通る超平面で錐から分けられる。
$a_1,\dots,a_m,b\in\mathbb{R}^n$ について、次のちょうど一方が成り立つ。
- $b\in\operatorname{cone}\{a_1,\dots,a_m\}$。
- すべての $i$ で $a_i\cdot y\ge0$、かつ $b\cdot y< 0$ となる $y\in\mathbb{R}^n$ がある。
有限集合 $S:=\{a_1,\dots,a_m\}$ について、2 は「$y\in S^*$ で $b\cdot y<0$ となるものがある」、すなわち $b\notin S^{**}$ ということである。thm-cc-bidual と thm-cc-closed により $S^{**}=\overline{\operatorname{cone}S}=\operatorname{cone}S$ なので、2 は 1 の否定と同値である。$\square$
$a_i$ を列とする行列 $A$ で書けば、1 は「$Ax=b$、$x\ge0$ に解がある」、2 は「$A^{\mathsf T}y\ge0$、$b\cdot y< 0$ に解がある」で、線形計画法 の系「等式と非負条件の形の Farkas の補題」と同じ主張である（そちらは Fourier–Motzkin の消去法から導いている）。
$K\subset\mathbb{R}^n$ について、$K$ が有限生成の錐であることと、$K$ が多面錐であることは同値である。
段 1（錐である多面体）。$K=\{x\mid Bx\le c\}$ が錐なら、$K=\{x\mid Bx\le0\}$ である。実際、$0\in K$ から $c\ge0$ なので $\{Bx\le0\}\subset K$ である。逆に $x\in K$ なら、すべての $t>0$ で $tBx\le c$ なので、$Bx\le c/t\to0$ である。
段 2（有限生成なら多面錐）。$K=\operatorname{cone}\{r_1,\dots,r_l\}$ とする。多面体 の定理「有限個の点の凸包は多面体」を 1 点 $0$ の凸包と $r_1,\dots,r_l$ に当てると、$K=\operatorname{conv}\{0\}+\operatorname{cone}\{r_1,\dots,r_l\}$ は有限個の 1 次不等式 $Bx\le c$ の解の全体である。$K$ は錐なので、段 1 により多面錐である。
段 3（多面錐なら有限生成）。$K=\{x\mid a_i\cdot x\le0\ (i=1,\dots,m)\}$ とすると、$K=\{-a_1,\dots,-a_m\}^*$ である。$D:=\operatorname{cone}\{-a_1,\dots,-a_m\}$ は有限生成なので、段 2 により $D=\{y\mid b_j\cdot y\le0\ (j=1,\dots,l)\}=\{-b_1,\dots,-b_l\}^*$ と書ける。prop-cc-dual-basic の 3、thm-cc-bidual、thm-cc-closed により
$$
K=\{-a_i\}_i^{\,*}=D^*=\bigl(\{-b_j\}_j^{\,*}\bigr)^*=\overline{\operatorname{cone}\{-b_1,\dots,-b_l\}}=\operatorname{cone}\{-b_1,\dots,-b_l\}
$$
である。$\square$
$\mathbb{R}^n_+$ はどちらの記述ももつ。ex-cc-lorentz-not-fg の 2 次錐はどちらでもない閉凸錐であり、有限個の半空間で切り出せない。
尖っていることと内部
$K\subset\mathbb{R}^n$ を閉凸錐とする。$K$ が尖っていることと、$K^*$ の内部が空でないことは同値である。したがって、$K$ が固有錐なら $K^*$ も固有錐である。
要点：$K^*$ の内部の点 $y$ では $K\setminus\{0\}$ の上で $y\cdot x>0$ となる。$K^*$ の内部が空なら $K^*$ はある超平面 $z^\perp$ に含まれ、$\pm z\in K^{**}=K$ となる。
詳しい証明を開く
$K^*$ の内部の点 $y$ をとる。$\varepsilon>0$ を、$\|u\|\le1$ なら $y-\varepsilon u\in K^*$ となるようにとる。$x\in K$、$x\ne0$ について $u=x/\|x\|$ とすると $(y-\varepsilon u)\cdot x\ge0$、すなわち $y\cdot x\ge\varepsilon\|x\|>0$ である。$x$ と $-x$ がともに $K$ に属すると $y\cdot x>0$ と $-y\cdot x>0$ が両立しないので、$K$ は尖っている。
逆に $K^*$ の内部が空だとする。$K^*$ が $\mathbb{R}^n$ の基底 $y_1,\dots,y_n$ を含むと、$K^*$ は開集合 $\{\sum_is_iy_i\mid s_i>0\}$（開集合 $\{s\mid s_i>0\}$ の可逆な線形写像による像）を含んでしまう。よって $K^*$ の張る部分空間は $\mathbb{R}^n$ でなく、それに直交する $z\ne0$ がある。$z\cdot y=0$ がすべての $y\in K^*$ で成り立つので $\pm z\in K^{**}=K$（thm-cc-bidual）で、$K$ は尖っていない。
最後の主張：$K$ が固有錐なら、$K^*$ は閉凸錐（prop-cc-dual-basic の 1）で、前半から内部が空でない。$K^*$ に前半を当てると、$(K^*)^*=K$ の内部が空でないことから $K^*$ は尖っている。$\square$
$\le_K$ は双対錐で書き直せる。$K$ が閉凸錐なら、thm-cc-bidual により
$$
x\le_Ky\iff\text{すべての }\lambda\in K^*\text{ で }\lambda\cdot x\le\lambda\cdot y
$$
である。$K=\mathrm{Sym}_n^+$ なら、これは「$X\le Y$（$Y-X$ が半正定値）$\iff$ すべての半正定値 $Z$ で $\operatorname{tr}(ZX)\le\operatorname{tr}(ZY)$」である。
閉凸錐への射影と Moreau の分解
閉凸集合 $C\ne\emptyset$ と点 $f$ について、$C$ の中で $f$ に最も近い点がただ 1 つあり、それを $P_Cf$ と書く。$C$ が錐のときは、この点が直交性で特徴づけられる。
$C\subset\mathbb{R}^n$ を空でない閉凸集合、$f\in\mathbb{R}^n$ とする。$\|f-u\|$ を最小にする $u\in C$ はただ 1 つあり、$u\in C$ がそれであることは、すべての $v\in C$ で $(f-u)\cdot(v-u)\le0$ となることと同値である。
要点：存在はコンパクト性から分かる。$\|f-v\|^2=\|f-u\|^2-2(f-u)\cdot(v-u)+\|v-u\|^2$ を、$v$ を $u$ と $v$ を結ぶ線分の点に替えて読む。
詳しい証明を開く
最小にする点があることは、凸包 の定理「点と閉凸集合の分離」の証明の段 1 と同じく、有界閉集合 $C\cap\{\|x-f\|\le\|c_0-f\|\}$（$c_0\in C$）の上の連続関数の最小値として分かる。$u$ が最小にする点なら、$v\in C$、$0< t\le1$ について $u+t(v-u)\in C$ なので $$\|f-u\|^2\le\|f-u-t(v-u)\|^2=\|f-u\|^2-2t(f-u)\cdot(v-u)+t^2\|v-u\|^2$$ であり、$\|f-u\|^2$ を引いて $t$ で割ると $2(f-u)\cdot(v-u)\le t\|v-u\|^2$、$t\to0$ として $(f-u)\cdot(v-u)\le0$ を得る。逆にこの不等式が成り立てば、すべての $v\in C$ で $$\|f-v\|^2=\|f-u\|^2-2(f-u)\cdot(v-u)+\|v-u\|^2\ge\|f-u\|^2+\|v-u\|^2$$ であり、$u$ は最小にする点で、$v\ne u$ では値が真に大きいので、最小にする点はただ 1 つである。$\square$
$K\subset\mathbb{R}^n$ を空でない閉凸錐、$f\in\mathbb{R}^n$ とする。$u=P_Kf$ であることは、次の 3 つが成り立つことと同値である。
$$
u\in K,\qquad\text{すべての }v\in K\text{ で }(f-u)\cdot v\le0,\qquad(f-u)\cdot u=0.
$$
すなわち $u=P_Kf$ は、$u\in K$、$f-u\in K^\circ$、$f-u\perp u$ で特徴づけられる。
lem-cc-nearest により、$u=P_Kf$ は「$u\in K$ かつ、すべての $v\in K$ で $(f-u)\cdot(v-u)\le0$」と同値である。これから 3 つの条件を導く。$v=0$ とすると $(f-u)\cdot u\ge0$、$v=2u\in K$ とすると $(f-u)\cdot u\le0$ なので、$(f-u)\cdot u=0$ である。すると一般の $v\in K$ で $(f-u)\cdot v=(f-u)\cdot(v-u)\le0$ である。逆に 3 つの条件が成り立てば、$(f-u)\cdot(v-u)=(f-u)\cdot v-(f-u)\cdot u\le0$ で、lem-cc-nearest の条件が成り立つ。$\square$
$K\subset\mathbb{R}^n$ を空でない閉凸錐とする。すべての $f\in\mathbb{R}^n$ について
$$
f=P_Kf+P_{K^\circ}f,\qquad P_Kf\cdot P_{K^\circ}f=0,\qquad\|f\|^2=\|P_Kf\|^2+\|P_{K^\circ}f\|^2
$$
が成り立つ。逆に $f=u+w$、$u\in K$、$w\in K^\circ$、$u\cdot w=0$ なら、$u=P_Kf$、$w=P_{K^\circ}f$ である。
$K^\circ=-K^*$ は空でない閉凸錐である（prop-cc-dual-basic の 1）。$u:=P_Kf$、$w:=f-u$ とおくと、thm-cc-projection により $w\in K^\circ$、$u\cdot w=0$ である。$w=P_{K^\circ}f$ を thm-cc-projection を $K^\circ$ に当てて確かめる。$w\in K^\circ$ であり、$z\in K^\circ$ について $(f-w)\cdot z=u\cdot z\le0$（$u\in K$ と極錐の定義）、$(f-w)\cdot w=u\cdot w=0$ である。ノルムの式は $u\perp w$ から出る。逆の主張：$u\in K$、$f-u=w\in K^\circ$、$(f-u)\cdot u=0$ なので thm-cc-projection により $u=P_Kf$ で、前半から $w=f-u=P_{K^\circ}f$ である。$\square$
- $K=\mathbb{R}^n_+$ では $K^\circ=-\mathbb{R}^n_+$ で、$P_Kf=f^+$（成分ごとに $\max(f_i,0)$）、$P_{K^\circ}f=-f^-$（$f^-$ は成分ごとの $\max(-f_i,0)$）である。$f=f^+-f^-$ と $f^+\cdot f^-=0$ が cor-cc-moreau の分解である。
- $K$ が部分空間 $V$ なら $K^\circ=V^\perp$ で、cor-cc-moreau は直交分解 $f=P_Vf+P_{V^\perp}f$ である（正射影と射影行列）。
lem-cc-nearest は実 Hilbert 空間の空でない閉凸集合でも成り立ち（最短点の存在にはコンパクト性の代わりに完備性を使う。Bre11 Theorem 5.2、p. 132）、そこから thm-cc-projection は上と同じ議論で実 Hilbert 空間の閉凸錐に広がる（Bre11 Exercise 5.7、p. 148）。
仮定を外すと成り立たなくなること
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 生成系が有限（thm-cc-closed） | 閉集合 $S=\{(1,t)\mid t\ge0\}\subset\mathbb{R}^2$ | $\operatorname{cone}S$ が閉じていない |
| $K$ が閉（thm-cc-bidual の後半） | $K=\{(s,t)\mid s>0,\ t\ge0\}\cup\{0\}$ | $K^{**}$ は閉じた第 1 象限で、$K$ と異なる |
| $K$ が凸（thm-cc-bidual の後半） | 座標軸の和集合 $\{x_1x_2=0\}$ | 閉じた錐だが $K^{**}=\mathbb{R}^2$ |
| $K$ が閉（thm-cc-projection） | 2 行目の $K$ と $f=(-1,1)$ | $K$ の中に $f$ に最も近い点がない |
どの行も、外す条件のほかは定理の仮定を満たしている。
4 つの確かめを開く
1. $\operatorname{cone}S=\{(s,t)\mid s>0,\ t\ge0\}\cup\{0\}$ である（$\lambda(1,t)=(\lambda,\lambda t)$ と、その和）。$(1/k,1)\in\operatorname{cone}S$ は $(0,1)\notin\operatorname{cone}S$ に収束する。$S$ は閉集合であり、閉じていないのは生成系が無限だからである。
2. $K$ は凸錐（1 の錐そのもの）で、閉じていない。prop-cc-dual-basic の 3 から $K^*=(\overline K)^*=(\mathbb{R}^2_+)^*=\mathbb{R}^2_+$ なので $K^{**}=\mathbb{R}^2_+\ne K$ である。
3. $K=\{x_1x_2=0\}$ は閉じた錐で、凸でない。$y\in K^*$ なら $(\pm1,0)$、$(0,\pm1)$ との内積から $y=0$ なので、$K^*=\{0\}$、$K^{**}=\mathbb{R}^2$ である。thm-cc-bidual の前半どおり、$\overline{\operatorname{cone}K}=\mathbb{R}^2$ である。
4. $f=(-1,1)$ と $K$ の点 $(s,t)$ の距離の 2 乗は $(s+1)^2+(t-1)^2>1$ で、$(s,t)=(1/k,1)$ で $1$ に近づくが、$1$ になるのは $K$ に属さない $(0,1)$ だけである。
補足
定義、錐結合、生成される錐、固有錐と $\le_K$ は BV04 §2.1.5（p. 25）と §2.4.1（p. 43）に、双対錐と自己双対の例（象限・半正定値錐）は §2.6.1（pp. 51–52）にある。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
