barrier cone が凸錐であること - Ex2.38(a)

職場の先輩に「君は賢いね．でも賢いという印象だけだと必ずしもプラスにはならないよ．頼りになるって思ってもらうことを目指すといいよ」と言われました．

確かに，「賢いね」というのは褒めてるとは限らない感じがしますね．嫌味っぽいというか，若干僻みっぽい感じがあってもおかしくない．

とりあえず頼りになるブログを目指しましょうかね！

さて今回も Boyd, Vandenberghe『Convex Optimization』を読んでいきます．

Convex Optimization (English Edition)

書影を得るためにAmazonのリンクを貼っていますが，この本は著者によりPDFが無償で公開されています．興味のある方は是非読んでみてください．

今回やってくのは演習2.38の(a)です．

問題文

The barrier cone of a set $C$ is defined as the set of all vectors $y$ such that $y^ T x$ is bounded above over $x \in C$.
In other words, a nonzero vector $y$ is in the barrier cone if and only if it is the normal vector of a halfspace $\{ x \mid y^ T x \leq α \}$ that contains $C$.　
Verify that the barrier cone is a convex cone (with no assumptions on $C$).
Ex 2.38(a)

問題の背景

集合から凸錐を構成せよというシリーズの問題のひとつです．

barrier cone というものを定義しまして，それが凸錐(convex cone)であることを示せと言っています．

barrier cone の日本語訳はちょっと，わかりませんでした．

回答

定義について

何か記号が必要ですね．

集合 $C$ の barrier cone を取り敢えず $b(C)$ と書くことにします．

さてこの問題ですが，barrier cone の定義がわかりにくいですね．

問題文を素直に読むと

(1) $y \neq 0$ and $y \in b(C)$

(2) ある $α \in \mathbb{R}$ が存在して $C \subseteq \{ x \mid y^ Tx \leq α \}$

の二つが同値だと言っているように見えます．

$α$ は問題文では明示的に量化されていないので，推測なんですけど．

うーん，$y$ が nonzero という仮定は実質的な意味がないんですね．

半空間を定義する法線ベクトルがゼロであっては困るから，ゼロでないとわざわざ断っているのだと思いますが，それなら半空間という言葉を避ければいい気がします．

まあ $y^ T x$ が有界ならいいわけですから，当然 $0 \in b(C)$ だとは思うんですけど．ちょっとわかりにくい．

まだ問題があります．

インターネットで barrier cone の定義を調べると $b(C)$ は双対錐 $C^ *$ の部分集合だとはっきり書いてあります．

つまり

$$ b(C) = \left\{ y \in C^* \mid \sup_{x \in C} y^T x < \infty \right\} $$

だと主張しています．

$$ b(C) = \left\{ y \in C^* \mid \exists α \forall x \in C \quad y^T x \leq α \right\} $$

と書いても構いませんが．

元の問題文の定義だと $b(C) \subseteq C^*$ であることが見づらいので，これはあまり良くない書き方ですね．

誤植でしょうか．

問いへの回答

定義がはっきりすれば，解くのは難しくありません．

ノートを貼ってしまいます．

この記事で $b(C)$ と書いているのに，ノートでは $\mathrm{Bar} \ C$ と書いていますが，気にしないでください．

これで証明ができました．

あとがき

この本，意外と定義の書き方が雑ですね．

この本以外の凸最適化の本を持っていないので，正直かなり心にきます．