凸性とその重要性

谷は1つ、答えも1つ

関数のグラフ上の任意の2点を結ぶ線分がグラフ上かその上側にあるとき、その関数は凸です：任意の $\theta\in[0,1]$ で $f(\theta\mathbf x+(1-\theta)\mathbf y)\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y)$。2回微分可能な関数には実用的な判定があり、ヘッセ行列がどこでも半正定値（固有値がすべて $\ge0$）であることが凸であるための必要十分条件です。凸関数の和、その正の定数倍、凸関数の最大は再び凸なので、小さな部品から大きな凸の目的関数を組み立てられます。

凸性は最適化を信頼できるものにします。局所最小はすべて大域最小で、勾配がゼロなら止めてよく、答えはソルバーの開始点に依存しません。関数が狭義凸なら最小化点は一意で、強凸（どの方向にも曲率が $\mu>0$ 以上）なら勾配降下法は先に見た幾何級数的な速さで収束します。凸でなければこれらは保証されず、ソルバーは最も深くない谷で止まるかもしれません。

金融での凸な目的関数には、ポートフォリオ分散 $\mathbf w^{T}\Sigma\mathbf w$（共分散行列は半正定値だから）、最小二乗の損失、$\ell_1$ ノルム $\lVert\mathbf w\rVert_1$、ウェイトの関数としての期待ショートフォール（CVaR）があります。バリュー・アット・リスク、非ゼロのウェイト数の上限、そのままのシャープレシオは凸ではありません。資産数より観測数が少ないときの標本共分散行列は半正定値ですが特異なので、分散は凸であっても狭義凸ではなく、多くのウェイトベクトルが最小値で並びます。

• ヘッセ行列の判定：どこでも固有値がすべて $\ge0$ なら凸、負の固有値が1つあれば凸ではありません。
• 利点：局所最小はすべて大域最小なので、開始点は関係ありません。
• 部品：凸関数の和、正の定数倍、最大は凸のままです。

ラボ：採点される内容

• 凸性のギャップ15点
• 凸性を壊す固有値15点
• 凸になるヘッセ行列はどれか15点
• 金融で凸な目的関数15点
• 勾配ゼロ10点
• 凸性の用語15点
• ソルバーが凸問題を好む理由15点