Yuta Hayashibe

用語集

  • 目的関数

    • 最適化したい関数
    • 単に最適化といえば， 多くの場合最小化をさす

  • 凸計画問題

    • 目的関数の値が改善する方向に進んでいけば解にたどりつく
    • 比較的解きやすい問題で，その解法はある程度確立している

  • 凸集合

    • 集合内の任意の点を結ぶ線分がその集合自身からはみ出さない(=へこみがない)

  • 凸関数

    • 任意のx1,x2∈Rdx_1, x_2 \in R^d, 任意のt∈[0,1]t \in [0,1]に対して， f(tx1+(1−t)x2)≥tf(x1)+(1−t)f(x2)f(t x_1 + (1-t) x_2 ) \geq t f(x_1) + (1-t) f(x_2) が成立
    • スカラー値関数に対してのみ定義できる
    • 凸関数であるための1次の条件（必要十分条件）: 任意のx1,x2∈Rdx_1, x_2 \in R^dに対して，f(x2)−f(x1)≤δf(x1)δx(x2−x1)f(x_2) - f(x_1) \leq \frac{ \delta f(x_1)}{\delta x} (x_2 - x_1)
    • 凸関数であるための2次の条件（必要十分条件）
      • 1変数関数: 二階微分f′′f''がf′′≤0f'' \leq 0
      • 多変数関数: ヘッセ行列HxH_{\bold{x}}が半正定値または半負定値
      • 局所最適解は大域最適解

  • ヘッセ行列

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

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

    • 偏微分を取って0になる場合に極値を取るので，その中に最小解がある
    • 束縛条件がある場合はラグランジュの未定乗数法が使える

  • 数値解法

    • 目的関数を解析的に解けない時に用いる
    • 何らかの階を初期値として与えて，より良い解へ更新していく解法

  • 劣微分

    • 微分の概念を微分不可能な関数に対して拡張した考え方
    • 関数の微分は関数だが，劣微分は集合になる
      • 微分可能な点では，劣微分は微分の値のみを要素とする集合
      • 微分不可能な点x0x_0では，劣微分はf(x)−f(x0)≥c(x−x0)f(x) - f(x_0) \geq c (x - x_0) を満たす数ccの集合
    • 劣勾配: 劣微分の集合の個々要素を指す語
    • 例: f(x)=∣x∣f(x) = |x| では
      • x<0x<0なら劣微分は−1 {-1}
      • 微分不可能な点x=0x=0における劣微分は[−1,1][-1,1]
      • x>0x>0なら劣微分は1 {1}

参考文献