用語集

  • 目的関数
    • 最適化したい関数
    • 単に最適化といえば， 多くの場合最小化をさす
  • 凸計画問題
    • 目的関数の値が改善する方向に進んでいけば解にたどりつく
    • 比較的解きやすい問題で，その解法はある程度確立している
  • 凸集合
    • 集合内の任意の点を結ぶ線分がその集合自身からはみ出さない(=へこみがない)
  • 凸関数
    • 任意の$x_1, x_2 \in R^d$, 任意の$t \in [0,1]$に対して， $f(t x_1 + (1-t) x_2 ) \geq t f(x_1) + (1-t) f(x_2)$ が成立
    • スカラー値関数に対してのみ定義できる
    • 凸関数であるための1次の条件（必要十分条件）: 任意の$x_1, x_2 \in R^d$に対して，$f(x_2) - f(x_1) \leq \frac{ \delta f(x_1)}{\delta x} (x_2 - x_1)$
    • 凸関数であるための2次の条件（必要十分条件）
      • 1変数関数: 二階微分$f''$が$f'' \leq 0 $
      • 多変数関数: ヘッセ行列$H_{\bold{x}}$が半正定値または半負定値
      • 局所最適解は大域最適解

  • ヘッセ行列

    • 多変数関数について，色々な変数の組についての(2階)微分
    • 行列の$(i,j)$成分は$\frac{\delta^2 f(\bold{x})}{\delta x_i \delta x_j}$

  • 目的関数を解析的に解く場合

    • 偏微分を取って0になる場合に極値を取るので，その中に最小解がある
    • 束縛条件がある場合はラグランジュの未定乗数法が使える
  • 数値解法
    • 目的関数を解析的に解けない時に用いる
    • 何らかの階を初期値として与えて，より良い解へ更新していく解法
  • 劣微分
    • 微分の概念を微分不可能な関数に対して拡張した考え方
    • 関数の微分は関数だが，劣微分は集合になる
      • 微分可能な点では，劣微分は微分の値のみを要素とする集合
      • 微分不可能な点$x_0$では，劣微分は$f(x) - f(x_0) \geq c (x - x_0) $を満たす数$c$の集合
    • 劣勾配: 劣微分の集合の個々要素を指す語
    • 例: $f(x) = |x| $では
      • $x<0$なら劣微分は$ {-1}$
      • 微分不可能な点$x=0$における劣微分は$[-1,1]$
      • $x>0$なら劣微分は$ {1}$

参考文献